Expander graphs are useful across mathematics, all the way from number theory to applied computer science. The smaller the second eigenvalue of a regular graph, the better expander it is. Since this connection was discovered in the 1980s, researchers have tried to pinpoint the second eigenvalue of random regular graphs. The most prominent work in this direction was Joel Friedman's proof of Noga Alon's conjecture from 1985 that for a random d-regular graph on n vertices, the second eigenvalue is almost as small as possible, with high probability as n tends to infinity with d held fixed.

We consider the case of denser graphs, where d and n are both growing. Here, the best result (Broder, Frieze, Suen, Upfal 1999) holds only if d = o(n^(1/2)). We extend this to d = O(n^(2/3)). Our result relies on new concentration inequalities for statistics of random regular graphs based on the theory of size biased couplings, an offshoot of Stein's method. The theory we develop should be useful for proving concentration inequalities in a broad range of settings. This is joint with Nicholas Cook and Larry Goldstein.