3
$\begingroup$

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?

1 Answers 1

3

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.

  • 0
    Thanks for your answer!What about non-regular graphs? can I prove it for such graphs also?2012-12-26