Improved spectral bounds for signed regular graphs with structural assumptions
Improved Bounds for the Bilu--Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
Discrete Mathematics
Summary
The paper studies a famous question about how much the connections in a regular network can be 'signed' to limit certain mathematical properties of its structure. The authors improve previous estimates on a key number (called the spectral radius) that measures how complex or stable the signed network can be. They use techniques involving special polynomials and matrices to get tighter bounds, especially for networks without small cycles. Their work also shows limitations, proving some barriers to how good the bounds can become.
What this means in practice
- •For network analysts: Use improved spectral bounds to better assess stability and resonance limits in signed network models reflecting real-world interactions.
- •For quantum computing engineers: Apply refined matrix polynomial techniques to analyze and design quantum systems modeled by signed Hermitian matrices with bounded spectra.
A theory result. No direct application yet.
Authors
Fangfang Lin, Hong Zhou
Abstract
The Bilu--Linial conjecture asks whether every finite $d$-regular graph with $d \geq 2$ admits an edge signing $σ$ whose signed adjacency matrix $A_σ$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_σ}\leq\sqrt{2(d-1)}$ satisfies \[ ρ(A_σ) < \frac{3+\sqrt5}{2}\sqrt{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\sqrt2$ 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 \preceq 4r_{A_σ}^2I$, which yields a preliminary coefficient $\sqrt{7}$. Estimates for the fourth moment use information about short walks to obtain the coefficient $(3+\sqrt{5})/2$. With more graph structural assumptions, the coefficient improves to $\sqrt6$ for triangle-free graphs and to $\sqrt{(5+3\sqrt5)/2}$ for graphs of girth at least five. As a result of independent interest, we extend the construction to $χ[A_1,\ldots,A_k]$ for Hermitian matrices $A_1,\ldots,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+\sqrt5)/\sqrt6$.