The spectral gap of dense random regular graphs

Konstantin Tikhomirov, Pierre Youssef

Research output: Contribution to journalArticle

Abstract

For any α ∈ (0, 1) and any n α ≤ d ≤ n/2, we show that λ(G) ≤ C α √d with probability at least 1 - 1/n, where G is the uniform random undirected d-regular graph on n vertices, λ(G) denotes its second largest eigenvalue (in absolute value) and C α is a constant depending only on α. Combined with earlier results in this direction covering the case of sparse random graphs, this completely settles the problem of estimating the magnitude of λ(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 λ(G) for d = o(√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 λ(G) in the range d = O(n 2/3 ) using size-biased couplings.

Original languageEnglish (US)
Pages (from-to)362-419
Number of pages58
JournalAnnals of Probability
Volume47
Issue number1
DOIs
StatePublished - Jan 1 2019

Keywords

  • Random matrices
  • Random regular graphs
  • Spectral gap
  • Uniform model

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'The spectral gap of dense random regular graphs'. Together they form a unique fingerprint.

  • Cite this