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 .=2d.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.