A proof of Alon's second eigenvalue conjecture and related problems

By Joel Friedman. arXiv.org, 2004

463 citations recorded by the source corpus.

Ad-regular graph has largest or rst (adjacency matrix) eigenvalue 1 = d. Consider for an even d 4, a random d-regular graph model formed from d=2 uniform, independent permutations on f1;:::;ng. We shall show that for any >0 we have all eigenvalues aside from 1 = d are bounded by 2 p d 1+ with probability 1 O(n ), where =d p d 1+ 1 =2e 1. We also show that this probability is at most 1 c=n 0 , for a constant c and a 0 that is either or +1 (\more often" than + 1). We prove related theorems for other models of random graphs, including models with d odd. These theorems resolve the conjecture of Alon, that says that for any > 0a ndd, the second largest eigenvalue of \most" random dregular graphs are at most 2 p d 1+ (Alon did not specify precisely what \most" should mean or what model of random graph one should take).

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

View Paper: https://www.semanticscholar.org/paper/2105cb7675b455f2f7e8b28c7cf70a84bbd177a3

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

Sparse regular random graphs: Spectral density and eigenvectors (2009, background): “References [1] Alon, N., Krivelevich, M., and Vu, V. (2002) On the concentration of eigenvalues of random matrices.”
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].”
Reconstruction and estimation in the planted partition model (2012, background): “Friedman’s proof ofAlon’s conjecture [13] gives a very accurate information regarding the spectrum of uniformly random d-regular graphs.”
Spectra of Graphs (2011, background): “Alon [4] conjectured, and Friedman [175] proved that large random kregular graphs have second largest eigenvalue smaller than 2 √ k − 1+ǫ (for fixed k, ǫ > 0 and n sufficiently large).”
Spectral redemption in clustering sparse networks (2013, methodology): “The fact that this operator has better spectral properties than, for instance, the standard random walk operator has been used in the past in the context of random matrices and random graphs [13–15].”
Tensor Products of C*-Algebras and Operator Spaces (2020, background): “In [93], Joel Friedman proved that for any fixed ε > 0 when N →∞ we have”
Expander graph and communication-efficient decentralized optimization (2016, background): “On the other hand, we agree for consensus averaging, those matrices recommended serve as the best candidates.”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, methodology): “One of them is the “trace method” [26, 28, 38, 35, 36] which consists of analyzing traces of high powers of the matrices under consideration.”
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].”
Comparison of Metric Spectral Gaps (2013, background): “If G is a uniformly random n-vertex d-regular graph then by [15] λ(G) 6 2/ 4 √ d with high probability (for the best known bound on λ(G) when G is a random d-regular graph, see [35]).”
THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH (2007, methodology): “On the other hand, the Broder-Shamir method gives direct information on BH versus B ̃ H , not AH versus A ̃ H (see [14, 15]).”
Cutoff phenomena for random walks on random regular graphs (2008, background): “Before reviewing some of the related work in this area, as well as the conjectures that our work addresses, we state a few of our main results.”
Size biased couplings and the spectral gap for random regular graphs (2015, methodology): “Dividing the resulting adjacency matrix by two, we have the random regular graph model In,d considered in [27], Theorem 1.”
Adjacency matrices of random digraphs: singularity and anti-concentration (2015, background): “Among others, we refer the reader to [2], [3], [12], [14], [26], and [35] for results dealing with the eigenvalue distribution.”