Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
Abstract
Bilu and Linial conjectured that every finite d-regular graph with d ≥ 2 admits an edge signing σ whose signed adjacency matrix Aσ has spectral radius at most 2√(d−1). We prove that every signing meeting the mixed-root condition rAσ≤√(2(d−1)) satisfies ρ(Aσ) < (3+√5)/2√(d−1), where rAσ is the largest root of the mixed determinantal polynomial χ[Aσ,−Aσ]. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient 2√2 in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of χ[Aσ,−Aσ]. The second moment gives a simple matrix inequality Aσ2 + dI ⪯ 4rAσ2I, which yields a preliminary coefficient √7. Estimates for the fourth moment use information about short walks to obtain the coefficient (3+√5)/2. For triangle-free graphs, the coefficient improves to √6, and for graphs with girth at least five, it improves to √(35/6). As a result of independent interest, we extend the construction to χ[A1,…,Ak] for Hermitian matrices A1,…,Ak with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of K8 shows that the mixed-root condition alone cannot guarantee a coefficient below (4+√5)/√6.
Related
- Remarks on the monodromy conjecture for symmetric determinantal hypersurfaces
- A variant of Collatz's conjecture over binary polynomials
- The Generalized Lax Conjecture for Strictly Hyperbolic Polynomials
- The Odlyzko-Poonen Conjecture on Irreducibility of Random Polynomials
- Improved bounds for the two-point logarithmic Chowla conjecture
BibTeX
@misc{lin2026improved,
title = {{Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials}},
author = {Fangfang Lin and Hong Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.15715},
eprint = {2609.15715},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15715},
}
RIS
TY - UNPB
TI - Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
AU - Fangfang Lin
AU - Hong Zhou
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2609.15715
UR - https://arxiv.org/abs/2609.15715
AB - Bilu and Linial conjectured that every finite d-regular graph with d ≥ 2 admits an edge signing σ whose signed adjacency matrix A_σ has spectral radius at most 2√(d−1). We prove that every signing meeting the mixed-root condition r_A_σ≤√(2(d−1)) satisfies ρ(A_σ) < (3+√5)/2√(d−1), where r_A_σ is the largest root of the mixed determinantal polynomial χ[A_σ,−A_σ]. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient 2√2 in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of χ[A_σ,−A_σ]. The second moment gives a simple matrix inequality A_σ^2 + dI ⪯ 4r_A_σ^2I, which yields a preliminary coefficient √7. Estimates for the fourth moment use information about short walks to obtain the coefficient (3+√5)/2. For triangle-free graphs, the coefficient improves to √6, and for graphs with girth at least five, it improves to √(35/6). As a result of independent interest, we extend the construction to χ[A_1,…,A_k] for Hermitian matrices A_1,…,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+√5)/√6.
ER -