The uniform model for $d$-regular graphs: concentration inequalities for linear forms and the spectral gap

Konstantin Tikhomirov, Pierre Youssef

Published 2016-10-06Version 1

In this paper, we address the problem of estimating the spectral gap of random $d$-regular graphs distributed according to the uniform model. Namely, let $\alpha>0$ be any positive number and let integers $d$ and $n$ satisfy $n^\alpha\leq d\leq n/2$. Let $G$ be uniformly distributed on the set of all $d$-regular simple undirected graphs on $n$ vertices, and let $\lambda(G)$ be the second largest (in absolute value) eigenvalue of $G$. We show that $\lambda(G)\leq C_\alpha \sqrt{d}$ with probability at least $1-\frac{1}{n}$, where $C_\alpha>0$ may depend 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$. The result is obtained as a consequence of an estimate for the second largest singular value of adjacency matrices of random {\it 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 non-trivial application of the Freedman inequality for martingales, combined with boots-trapping and tensorization arguments. Our method bears considerable differences compared to the approach used by Broder, Frieze, Suen and Upfal (1999) who established the upper bound for $\lambda(G)$ for $d=o(\sqrt{n})$, and to the argument of Cook, Goldstein and Johnson (2015) who derived a concentration inequality for linear forms and estimated $\lambda(G)$ in the range $d= O(n^{2/3})$ using size-biased couplings.