Metraipolis › archive › dc_67a29ff1dd20
Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials — arXiv:2609.15715
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15715
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T01:25:34.181Z
- SHA-256 of the archived text
0554c0ccf02b7379334038278b1688940296f7e774bd26122931f74828122812- Stable URL of this page
https://metraipolis.com/documento/dc_67a29ff1dd20
How to cite
Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials — arXiv:2609.15715 — arXiv (en), https://arxiv.org/abs/2609.15715 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_67a29ff1dd20 (Metraipolis archive dc_67a29ff1dd20, sha256 0554c0ccf02b7379334038278b1688940296f7e774bd26122931f74828122812)
BibTeX
@misc{dc67a29ff1dd20,
title = {Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials — arXiv:2609.15715},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15715},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_67a29ff1dd20; sha256 0554c0ccf02b7379334038278b1688940296f7e774bd26122931f74828122812},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15715. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Bilu and Linial conjectured that every finite $d$-regular graph with $d \geq 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}\leq\sqrt{2(d-1)}$ satisfies \[ \rho(A_\sigma) < \frac{3+\sqrt5}{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\sqrt2$ 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 \preceq 4r_{A_\sigma}^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 $\chi[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$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.15715 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T00:39:30.256Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).