The spectral gap of random regular graphs

DOI10.1002/RSA.21150MaRDI QIDQ6076727zbMATH OpenOpenAlexFDO

Authors Amir Sarid

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2201.02015

zbMATH Keywords

eigenvalueexpanderFourier analysisrandom matrixrandom regular graphsspectral gap

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Expander graphs (05C48) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52)

Abstract: We bound the second eigenvalue of random $d$-regular graphs, for a wide range of degrees $d$, using a novel approach based on Fourier analysis. Let $G_{n,d}$ be a uniform random $d$-regular graph on $n$ vertices, and let $lambda(G_{n,d})$ be its second largest eigenvalue by absolute value. For some constant $c>0$ and any degree $d$ with $lo{g}^{10}nlldleqcn$, we show that $lambda(G_{n,d})=(2+o(1))sqrtd(n-d)/n$ asymptotically almost surely. Combined with earlier results that cover the case of sparse random graphs, this fully determines the asymptotic value of $lambda(G_{n,d})$ for all $dleqcn$. To achieve this, we introduce new methods that use mechanisms from discrete Fourier analysis, and combine them with existing tools and estimates on $d$-regular random graphs - especially those of Liebenau and Wormald.

Recommendations

• The spectral gap of dense random regular graphs
• On the second eigenvalue and random walks in random d-regular graphs
• 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
• Edge rigidity and universality of random regular graphs of intermediate degree

Cites work

• 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
• Analysis of Boolean Functions
• Edge rigidity and universality of random regular graphs of intermediate degree
• Eigenvalues and expanders
• Expansion of random graphs: new proofs, new results
• Explicit construction of linear sized tolerant networks
• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 6803211 (Why is no real title available?)
• On the concentration of eigenvalues of random symmetric matrices
• On the distribution of the roots of certain symmetric matrices
• On the second eigenvalue of a graph
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Size biased couplings and the spectral gap for random regular graphs
• Small subgraphs of random regular graphs
• Sparse random graphs: eigenvalues and eigenvectors
• Spectral norm of random matrices
• Subgraphs of dense random graphs with specified degrees
• The eigenvalues of random symmetric matrices
• The expected eigenvalue distribution of a large regular graph
• The spectral gap of dense random regular graphs

Cited in

(14)

• Discrepancy properties for random regular digraphs
• Emergence of a spectral gap in a class of random matrices associated with split graphs
• Spectral gap in random bipartite biregular graphs and applications
• A note on the trace method for random regular graphs
• On the second eigenvalue of random bipartite biregular graphs
• Spectral gap and edge universality of dense random regular graphs
• Minors in small-set expanders
• A note on quantum expanders
• Fluctuation of the largest eigenvalue of a kernel matrix with application in graphon-based random graphs
• Rigid partitions: from high connectivity to random graphs
• Minimum degree k and k-connectedness usually arrive together
• A new approach to strong convergence
• Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree
• Vertex-separating path systems in random graphs

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

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