Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have seen in many places the quote: "Random graphs are good expanders". The only prof I could find to this sentence is regarding b-partite graphs, for example the proof in here

I want to prove that the probability of a random graph being an expander goes to 1 as n (number of vertx) goes to infinity.

Can anyone address me to such a proof?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Take a look at this survey paper by Hoory, Linial and Wigderson.

Suppose that $G$ is a $d$ regular graph, and let $\lambda_{2}(G)$ be the second largest eigenvalue, so that $\lambda_1(G)=d$. Then Cheegers inequality for graphs states that $$\frac{d-\lambda_2(G)}{2}\leq h(G)\leq \sqrt{2d(d-\lambda_2(G)},$$ where $h(G)$ is the edge expansion constant. This means that the smaller $\lambda_2(G)$ is, the better the expander. Alon and Boppanna proved that for any $d$-regular graph, as the number of vertices $n\rightarrow\infty$, we have that $$\lambda_2(G)\geq 2\sqrt{d-1}\left(1-o(1)\right).$$ That is, $2\sqrt{d-1}$ is a lower bound for the second largest eigenvalue. Alon also conjectured that the random graph is in some sense the best possible expander, and that for the random graph, with probability going to $1$ as the number of vertices go to infinity, we have that $$\lambda_2(G)\leq 2\sqrt{d-1}+\epsilon.$$ This was proven by Joel Friedman in $2004$, and the $118$ page paper can be found here.

share|improve this answer
    
Thanks for your answer!What about non-regular graphs? can I prove it for such graphs also? –  user844541 Dec 26 '12 at 19:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.