Skip to content
DraconiticResearch
Search Sources API
185,139 studies31 sourcesUpdated 26 min ago
PreprintCC BY 4.0arXiv

An Alon-Boppana Bound for the Non-Backtracking Operator

  • Theo McKenzie
Open at sourcePDFDOICite

Abstract

For any fixed k, we prove a lower bound on the kth largest modulus of an eigenvalue of the non-backtracking matrix B. Specifically, consider any deterministic or random family of graphs that converges locally to the unimodular Galton-Watson tree with root degree distribution D, and set κ:=𝔼[D(D−1)]/𝔼[D]. Given κ>1 and an exponential-moment bound on the empirical degree distributions, we show that |λk(B)|≥√κ−oN(1), where N is the number of vertices. When restricted to locally tree-like regular graphs, this recovers a well-known consequence of the Ihara-Bass formula. In the specific case where the graph is generated through the Erdős-Rényi model with expected degree d>1, this proves a conjecture of Bordenave, Lelarge, and Massoulié. To do this, we show that the normalized log-determinant of the Bethe-Hessian of the graph is bounded by that of the Bethe-Hessian of its local limit. This bound is violated if the eigenvalues of the non-backtracking matrix are too small. We establish this using an effective-conductance interpretation of the tree Green's function recursion.

Related

  1. Stability and exact extremal colourings for the Alon--Frankl--Lovász bound
    Tianhong Kan, Hongliang Lu, Feihong Yuan
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  2. A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
    Junran Yu, Gexin Yu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Failure of the linear A2 bound for the strong maximal operator
    Andrei K. Lerner
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. The sharp Lp bound for the imaginary part of the Beurling-Ahlfors operator on the lattice
    Komla Domelevo, Stefanie Petermichl
    arXivPreprintarXiv licenceFull textAnalysis & PDEsProbabilityarXiv
  5. Total scalar curvature under a curvature operator lower bound
    Jian Ge, Chuanhuan Li, Ronggang Li
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{mckenzie2026alonboppana,
  title = {{An Alon-Boppana Bound for the Non-Backtracking Operator}},
  author = {Theo McKenzie},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.17529},
  eprint = {2609.17529},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17529},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - An Alon-Boppana Bound for the Non-Backtracking Operator
AU  - Theo McKenzie
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.17529
UR  - https://arxiv.org/abs/2609.17529
AB  - For any fixed k, we prove a lower bound on the kth largest modulus of an eigenvalue of the non-backtracking matrix B. Specifically, consider any deterministic or random family of graphs that converges locally to the unimodular Galton-Watson tree with root degree distribution D, and set κ:=𝔼[D(D−1)]/𝔼[D]. Given κ>1 and an exponential-moment bound on the empirical degree distributions, we show that |λ_k(B)|≥√κ−o_N(1), where N is the number of vertices. When restricted to locally tree-like regular graphs, this recovers a well-known consequence of the Ihara-Bass formula. In the specific case where the graph is generated through the Erdős-Rényi model with expected degree d>1, this proves a conjecture of Bordenave, Lelarge, and Massoulié. To do this, we show that the normalized log-determinant of the Bethe-Hessian of the graph is bounded by that of the Bethe-Hessian of its local limit. This bound is violated if the eigenvalues of the non-backtracking matrix are too small. We establish this using an effective-conductance interpretation of the tree Green's function recursion.
ER  -