Size biased couplings and the spectral gap for random regular graphs

Abstract

Let $λ$ 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 $λ=2\sqrt{d-1} +o(1)$ with high probability. In the present work we show that $λ=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