A Note on the Trace Method for Random Regular Graphs

Abstract

The main goal of this note is to illustrate the advantage of analyzing the non-backtracking spectrum of a regular graph rather than the ordinary spectrum. We show that by switching to non-backtracking spectrum, the method of proof used in [Puder 2015, arXiv::1212.5216] yields a bound of $2\sqrt{d-1}+\frac{2}{\sqrt{d-1}}$ instead of the original $2\sqrt{d-1}+1$ on the second largest eigenvalue of a random $d$-regular graph.

9 pages, no figures. Minor changes upon previous version

References in corpus (3)

• The Relativized Second Eigenvalue Conjecture of Alon
• Word Measures on Symmetric Groups
• On the Relativized Alon Second Eigenvalue Conjecture I: Main Theorems, Examples, and Outline of Proof

Cited by in corpus (5)

• A random cover of a compact hyperbolic surface has relative spectral gap $\frac{3}{16}-\epsilon$
• Word Measures on Symmetric Groups
• Word Measures on $G{L}_N(q)$ and Free Group Algebras
• Black Holes, Complex Curves, and Graph Theory: Revising a Conjecture by Kasner
• On the Relativized Alon Second Eigenvalue Conjecture V: Proof of the Relativized Alon Conjecture for Regular Base Graphs