Size biased couplings and the spectral gap for random regular graphs

Nicholas A. Cook, Larry Goldstein, Tobias Johnson

Published 2015-10-20Version 1

Let $\lambda$ be the second largest eigenvalue in absolute value of a uniform random $d$-regular graph on $n$ vertices. When $d$ and $n$ grow simultaneously with $d=o(n^{1/2})$, Broder, Frieze, Suen, and Upfal (1999) showed that $\lambda\leq C\sqrt{d}$ with high probability. We show that this bound holds so long as $d=O(n^{2/3})$, making progress towards a conjecture of Van Vu. Our proof relies on concentration estimates for random regular graphs, which we obtain by new developments on the theory of concentration by size biased couplings. Specifically, we prove concentration given the existence of certain unbounded size biased couplings, and obtain tail estimates analogous to the ones given by Bennett's inequality.