The spectral gap of dense random regular graphs

By Konstantin E. Tikhomirov, Pierre Youssef. Annals of Probability, 2016

53 citations recorded by the source corpus.

For any $\alpha\in (0,1)$ and any $n^{\alpha}\leq d\leq n/2$, we show that $\lambda(G)\leq C_\alpha \sqrt{d}$ with probability at least $1-\frac{1}{n}$, where $G$ is the uniform random $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 {\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.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/53481d97e1486661bc417598de52cf77c697031a