Expansion of random graphs: new proofs, new results

By Doron Puder. 2012

111 citations recorded by the source corpus.

We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on recent deep results in combinatorial group theory. It applies to both regular and irregular random graphs. Let $$\Gamma $$Γ be a random $$d$$d-regular graph on $$n$$n vertices, and let $$\lambda $$λ be the largest absolute value of a non-trivial eigenvalue of its adjacency matrix. It was conjectured by Alon (Combinatorica 6(2), 83–96, 1986) that a random $$d$$d-regular graph is “almost Ramanujan”, in the following sense: for every $$\varepsilon >0$$ε>0, $$\lambda <2\sqrt{d-1}+\varepsilon $$λ<2d-1+ε asymptotically almost surely. Friedman famously presented a proof of this conjecture in Friedman (Memoirs of the AMS 910, 2008). Here we suggest a new, substantially simpler proof of a nearly-optimal result: we show that a random $$d$$d-regular graph satisfies $$\lambda <2\sqrt{d-1}+1$$λ<2d-1+1 a.a.s. A main advantage of our approach is that it is applicable to a generalized conjecture: For $$d$$d even, a $$d$$d-regular graph on $$n$$n vertices is an $$n$$n-covering space of a bouquet of $$d/2$$d/2 loops. More generally, fixing an arbitrary base graph $$\Omega $$Ω, we study the spectrum of $$\Gamma $$Γ, a random $$n$$n-covering of $$\Omega $$Ω. Let $$\lambda $$λ be the largest absolute value of a non-trivial eigenvalue of $$\Gamma $$Γ. Extending Alon’s conjecture to this more general model, Friedman (Duke Math J 118(1),19–35, 2003) conjectured that for every $$\varepsilon >0,$$ε>0, a.a.s. $$\lambda <\rho +\varepsilon $$λ<ρ+ε, where $$\rho $$ρ is the spectral radius of the universal cover of $$\Omega $$Ω. When $$\Omega $$Ω is regular we get a bound of $$\rho +0.84$$ρ+0.84, and for an arbitrary $$\Omega $$Ω, we prove a nearly optimal upper bound of $$\sqrt{3}\rho $$3ρ. This is a substantial improvement upon all known results (by Friedman, Linial-Puder, Lubetzky-Sudakov-Vu and Addario-Berry-Griffiths).

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/91e4a8c7ef8f5c03f2899540231048b1acc45c2c

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

The spectral gap of dense random regular graphs (2016, background): “Friedman proved, in particular, that λ(G) = 2 √ d− 1 + o(1) with probability tending to one with 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”
Eigenvalues of random lifts and polynomials of random permutation matrices (2018, background): “He would like to thanks Doron Puder for early discussions on this problem.”
A new proof of Friedman's second eigenvalue theorem and its extension to random lifts (2015, background): “This class of models sheds a new light on Ramanujan-type properties, and, since the work of Amit and Linial [3, 4] and Friedman [10], it has attracted a substantial attention [15, 1, 16, 24, 12].”