The Alon’s second eigenvalue conjecture is true

You need to know: Basic probability theory, random permutation, graph, d-regular graph, adjacency matrix of a graph, eigenvalue of a matrix, limits.

Background: For an even $d \geq 4$ , by random d-regular graph on n vertices we mean a graph formed from $d/2$ uniform, independent permutations on $\{1, . . . , n\}$ . For fixed d and fixed real $\epsilon>0$ , let $p_n$ be the probability that such a graph has the second largest eigenvalue of its adjacency matrix greater than $2 \sqrt{d-1} + \epsilon$ .

The Theorem: On 27th March 2002, Joel Friedman submitted to Memoirs of the AMS a monograph in which he proved that $\lim\limits_{n\to\infty} p_n = 0$ .

Short context: The adjacency matrix of any finite undirected graph G has only real eigenvalues, which can be written in non-increasing order $\lambda_1(G) \geq \lambda_2(G) \geq \dots \geq \lambda_n(G)$ . For d-regular G, $\lambda_1(G)=d$ . In 1986, Alon observed that graphs G with $\lambda_2(G)$ small have various nice properties, and conjectured that for any $\epsilon>0$ and any $d\geq 3$ , $\lambda_2(G) \leq 2 \sqrt{d-1} + \epsilon$ for “most” random d-regular graphs G. The constant $2 \sqrt{d-1}$ in this inequality is the best possible. This statement became known as Alon’s second eigenvalue conjecture. The Theorem, as stated above, resolves it for even d. In the same paper, Friedman also proved the conjecture for other models of random d-regular graph, including models for odd d.