Take the 2-minute tour ×

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

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

Your Answer


