The spectral gap of random regular graphs

2022/01/06 by Sarid, Amir · 2 citations
#05C80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2201.02015

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 λ(G_{n, d}) be its second largest eigenvalue by absolute value. For some constant c > 0 and any degree d with log¹⁰ n ≪ d ≤ c n, we show that λ(G_{n, d}) = (2 + o(1)) √(d (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 λ(G_{n, d}) for all d ≤ c n. 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.

Cited by

• Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
• On Independent Spanning Trees in Random and Pseudorandom Graphs

Related

• Arbitrary Spectral Edge of Regular Graphs
• Spectrum of Random d-regular Graphs Up to the Edge
• A new proof of Friedman's second eigenvalue Theorem and its extension to random lifts
• The Spectral Gap of Sparse Random Digraphs
• Eigenvalue spacings for regular graphs