OpenAlex ·
Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.15715
- Original
- Read it at the publisher
- Topics
Abstract
Bilu and Linial conjectured that 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$. For triangle-free graphs, the coefficient improves to $\sqrt6$, and for graphs with girth at least five, it improves to $\sqrt{35/6}$. 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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Products of Boolean Clones up to Minion Homomorphisms
Selflessness, MIF and opposition in groups acting on exotic buildings
Two Extremal Even Unimodular Lattices of Rank $88$
A Strongly Aperiodic Monotile in Three Dimensions
Kernel--wreath constructions and infinite families of finite simple skew braces
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.