Size biased couplings and the spectral gap for random regular graphs

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√d-1+o(1) with high probability. In the present work, we show that λ=O(√d) continues to hold with high probability as long as d=O(n2/3), making progress toward a conjecture of Vu that the bound holds for all 1≤ d≤ 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(n1/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.