A new proof of Friedman's second eigenvalue theorem and its extension to random lifts

By Charles Bordenave. Annales Scientifiques de l'Ecole Normale Supérieure, 2015

150 citations recorded by the source corpus.

It was conjectured by Alon and proved by Friedman that a random $d$-regular graph has nearly the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most $2\sqrt{d-1} +o(1)$ with probability tending to one as the size of the graph tends to infinity. We give a new proof of this statement. We also study related questions on random $n$-lifts of graphs and improve a recent result by Friedman and Kohler.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/cc7f798a8247303ad7e23bbda0329af4d7a1deb9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs (2018, methodology): “Similarly, for the stochastic block model, our main result is analogous to recent results on the eigenvalues of random n-lifts of base graphs; see [6, 10].”
Eigenvalues of random lifts and polynomials of random permutation matrices (2018, methodology): “Then, the proof of Theorem 17 follows a strategy similar to the new proof of Friedman’s Theorem in [7].”
The spectral gap of dense random regular graphs (2016, background): “h n → ∞, where λ(G) is the second largest (in absolute value) eigenvalue of the undirected d-regular random graph G on n vertices, uniformly distributed on the set of all simple d-regular graphs (see [7] for an alternative proof of Friedman’s theorem; see also [22] for a diﬀerent approach producing ”
Cutoff for non-negatively curved Markov chains (2021, background): “Note however, that unlike the product condition (2), verifying the Ramanujan property does require determining the relaxation time up to a o(1) term, a notoriously challenging task even on random instances [28, 13].”
Size biased couplings and the spectral gap for random regular graphs (2015, background): “Also see [12] for a simpler proof of this result.”