THE SPECTRAL GAP OF DENSE RANDOM REGULAR GRAPHS

For any alpha is an element of (0,1) and any n(alpha) <= d <= n/2, we show that lambda(G) <= C-alpha root d with probability at least 1 - 1/n, where G is the uniform random undirected d-regular graph on n vertices, lambda(G) denotes its second largest eigenvalue (in absolute value) and C-alpha is a constant depending only on alpha. Combined with earlier results in this direction covering the case of sparse random graphs, this completely settles the problem of estimating the magnitude of lambda(G), up to a multiplicative constant, for all values of n and d, confirming a conjecture of Vu. The result is obtained as a consequence of an estimate for the second largest singular value of adjacency matrices of random directed graphs with predefined degree sequences. As the main technical tool, we prove a concentration inequality for arbitrary linear forms on the space of matrices, where the probability measure is induced by the adjacency matrix of a random directed graph with prescribed degree sequences. The proof is a nontrivial application of the Freedman inequality for martingales, combined with self-bounding and tensorization arguments. Our method bears considerable differences compared to the approach used by Broder et al. [SIAM J. Comput. 28 (1999) 541-573] who established the upper bound for lambda(G) for d = o(root n), and to the argument of Cook, Goldstein and Johnson [Ann. Probab. 46 (2018) 72-125] who derived a concentration inequality for linear forms and estimated lambda(G) in the range d = O(n (2/3)) using size-biased couplings.