Bordenave–Lelarge–Massoulié conjecture

The conjecture asks for a sharp lower bound on non-backtracking eigenvalues, including the Erdős–Rényi case. Bordenave, Lelarge, and Massoulié stated the matching lower bound as a conjecture in their 2015 paper.

Known results

• For Erdős–Rényi graphs with fixed $\alpha>1$, Bordenave, Lelarge, and Massoulié (2015) proved $\lambda_1(B)=\alpha+o(1)$ and $|\lambda_2(B)|\leq\sqrt{\alpha}+o(1)$ with high probability.
• The same paper established only a weaker lower bound and left $|\lambda_2(B)|\geq\sqrt{\alpha}-o(1)$ conjectural.

September 2026 claimed proof

Theo McKenzie’s unrefereed arXiv preprint claims that, for graph families converging locally to a unimodular Galton–Watson tree, the $k$th largest non-backtracking eigenvalue has modulus at least $\sqrt{\kappa}-o_N(1)$, thereby proving the conjecture in the Erdős–Rényi case. This claim is unverified.

Current status (as of September 2026): A preprint claims the conjectured lower bound in the stated generality, including the Erdős–Rényi case, but independent verification is absent.