Improved Bounds for the Bilu--Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials

The Bilu–Linial conjecture asks whether every finite $d$-regular graph with $d\ge 2$ admits an edge signing $\sigma$ whose signed adjacency matrix $A_{\sigma }$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_{\sigma }}\le \sqrt{2(d-1)}$ satisfies $$\rho (A_{\sigma })<\frac{3+\sqrt{5}}{2}\sqrt{d-1},$$ where $r_{A_{\sigma }}$ is the largest root of the mixed determinantal polynomial $\chi [A_{\sigma },-A_{\sigma }]$. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient $2\sqrt{2}$ in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of $\chi [A_{\sigma },-A_{\sigma }]$. The second moment gives a simple matrix inequality $A_{\sigma }^2+dI⪯4r_{A_{\sigma }}^{2}I$, which yields a preliminary coefficient $\sqrt{7}$. Estimates for the fourth moment use information about short walks to obtain the coefficient $(3+\sqrt{5})\mathrm{/}2$. With more graph structural assumptions, the coefficient improves to $\sqrt{6}$ for triangle-free graphs and to $\sqrt{(5+3\sqrt{5})\mathrm{/}2}$ for graphs of girth at least five. As a result of independent interest, we extend the construction to $\chi [A_1,\dots ,A_k]$ for Hermitian matrices $A_1,\dots ,A_k$ with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of $K_8$ shows that the mixed-root condition alone cannot guarantee a coefficient below $(4+\sqrt{5})\mathrm{/}\sqrt{6}$.