The spectral gap of dense random regular graphs

DOI10.1214/18-AOP1263MaRDI QIDQ1731891zbMATH OpenWikidataFDO

Authors Konstantin E. Tikhomirov, Pierre Youssef

Publication date 14 March 2019

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01765, https://projecteuclid.org/euclid.aop/1544691624

zbMATH Keywords

random matricesspectral gaprandom regular graphsuniform model

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: For any $alphain(0,1)$ and any $n^{alpha}leqdleqn/2$, we show that $lambda(G)leq{C}_{a}lphasqrtd$ with probability at least $1-frac1n$, where $G$ is the uniform random $d$-regular graph on $n$ vertices, $lambda(G)$ denotes its second largest eigenvalue (in absolute value) and $C_{a}lpha$ is a constant depending only on $alpha$. Combined with earlier results in this direction covering the case of sparse random graphs, this completely settles the problem of estimating the magnitude of $lambda(G)$, up to a multiplicative constant, for all values of $n$ and $d$, confirming a conjecture of Vu. The result is obtained as a consequence of an estimate for the second largest singular value of adjacency matrices of random {it directed} graphs with predefined degree sequences. As the main technical tool, we prove a concentration inequality for arbitrary linear forms on the space of matrices, where the probability measure is induced by the adjacency matrix of a random directed graph with prescribed degree sequences. The proof is a non-trivial application of the Freedman inequality for martingales, combined with boots-trapping and tensorization arguments. Our method bears considerable differences compared to the approach used by Broder, Frieze, Suen and Upfal (1999) who established the upper bound for $lambda(G)$ for $d=o(sqrtn)$, and to the argument of Cook, Goldstein and Johnson (2015) who derived a concentration inequality for linear forms and estimated $lambda(G)$ in the range $d=O(n^{2/3})$ using size-biased couplings.

Recommendations

• Size biased couplings and the spectral gap for random regular graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A proof of Alon’s second eigenvalue conjecture and related problems
• Sparse regular random graphs: spectral density and eigenvectors
• On the second eigenvalue and random walks in random \(d\)-regular graphs

Cites work

• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 6803211 (Why is no real title available?)
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A proof of Alon’s second eigenvalue conjecture and related problems
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Bulk eigenvalue statistics for random regular graphs
• Discrepancy properties for random regular digraphs
• Eigenvalues and expanders
• Expansion of random graphs: new proofs, new results
• Functional limit theorems for random regular graphs
• Local semicircle law for random regular graphs
• On tail probabilities for martingales
• On the norm of a random jointly exchangeable matrix
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• On the singularity of adjacency matrices for random regular digraphs
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Partitions and Their Representative Graphs
• Probability Inequalities for the Sum of Independent Random Variables
• Size biased couplings and the spectral gap for random regular graphs
• Smallest singular value of random matrices and geometry of random polytopes
• Sparse random graphs: eigenvalues and eigenvectors
• Sparse regular random graphs: spectral density and eigenvectors
• The Littlewood-Offord problem and invertibility of random matrices
• The expected eigenvalue distribution of a large regular graph
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(22)

• The spectral gap of random regular graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• The spectral gap of sparse random digraphs
• Mean-Field Approximations for Stochastic Population Processes with Heterogeneous Interactions
• Sherali-adams strikes back
• Spectral gap and edge universality of dense random regular graphs
• Reliable communication over highly connected noisy networks
• Dirac's theorem for random regular graphs
• Simplex links in determinantal hypertrees
• On the norm of a random jointly exchangeable matrix
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• A note on the trace method for random regular graphs
• Sparse random tensors: concentration, regularization and applications
• Circular law for sparse random regular digraphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• Global eigenvalue fluctuations of random biregular bipartite graphs
• On the second eigenvalue of random bipartite biregular graphs
• Quasi-majority functional voting on expander graphs
• Complete Minors in Graphs Without Sparse Cuts
• Spectral techniques applied to sparse random graphs
• Size biased couplings and the spectral gap for random regular graphs
• Sherali-Adams strikes back

This page was built for publication: The spectral gap of dense random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1731891)