Size biased couplings and the spectral gap for random regular graphs

Abstract

Let $\lambda$ be the second largest eigenvalue in absolute value of a uniform random $d$-regular graph on $n$ vertices. It was famously conjectured by Alon and proved by Friedman that if $d$ is fixed independent of $n$, then $\lambda =2\sqrt{d-1}+o(1)$ with high probability. In the present work we show that $\lambda =O(\sqrt{d})$ continues to hold with high probability as long as $d=O(n^{2/3})$, making progress towards a conjecture of Vu that the bound holds for all $1\le d\le n/2$. Prior to this work the best result was obtained by Broder, Frieze, Suen and Upfal (1999) using the configuration model, which hits a barrier at $d=o(n^{1/2})$. We are able to go beyond this barrier by proving concentration of measure results directly for the uniform distribution on $d$-regular graphs. These come as consequences of advances we make in the theory of concentration by size biased couplings. Specifically, we obtain Bennett-type tail estimates for random variables admitting certain unbounded size biased couplings.

41 pages; small changes in response to referees' comments; to appear in the Annals of Probability

References in corpus (3)

• Local semicircle law for random regular graphs
• Bulk eigenvalue statistics for random regular graphs
• The spectral gap of dense random regular graphs

Cited by in corpus (19)

• Local Kesten--McKay law for random regular graphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• A discrete log-Sobolev inequality under a Bakry-Emery type condition
• Hamilton Cycles in Random Graphs: a bibliography
• Infection spread for the frog model on trees
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• A central limit theorem for descents of a Mallows permutation and its inverse
• Sparse random tensors: Concentration, regularization and applications
• On the second eigenvalue of random bipartite biregular graphs
• The spectral gap of dense random regular graphs
• Card guessing and the birthday problem for sampling without replacement
• Many edge-disjoint rainbow spanning trees in general graphs
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Relaxation of monotone coupling conditions: Poisson approximation and beyond
• Central moment inequalities using Stein's method
• A note on quantum expanders
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Concentration inequalities from monotone couplings for graphs, walks, trees and branching processes
• Concentration inequalities using approximate zero bias couplings with applications to Hoeffding's statistic under the Ewens distribution