Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 20 min ago
PreprintarXiv licencearXiv

A 3-regular counterexample to the Bilu--Linial signing conjecture

  • Zhiqiang Xu
Open at sourcePDFDOICite

Abstract

We construct a finite connected simple cubic graph F such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside [−2√2,2√2]. This disproves the Bilu--Linial signing conjecture for general regular graphs. The graph F is not Ramanujan, and the conjecture restricted to Ramanujan base graphs remains open.

Related

  1. A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
    Zhiqiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A √2-Approximation to the Bilu-Linial Conjecture
    Zejun Huang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
    Fangfang Lin, Hong Zhou
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
    Ali Jadbabaie, Amin Saberi, Suvrit Sra
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  5. A counterexample to a conjecture of Duncan on versal actions
    Federico Scavia
    HALPreprintLicence not statedAlgebra & number theoryHAL

Cite

BibTeXRIS
BibTeX
@misc{xu20263regular,
  title = {{A 3-regular counterexample to the Bilu--Linial signing conjecture}},
  author = {Zhiqiang Xu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.15591},
  eprint = {2609.15591},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.15591},
}
RIS
TY  - UNPB
TI  - A 3-regular counterexample to the Bilu--Linial signing conjecture
AU  - Zhiqiang Xu
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.15591
UR  - https://arxiv.org/abs/2609.15591
AB  - We construct a finite connected simple cubic graph F such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside [−2√2,2√2]. This disproves the Bilu--Linial signing conjecture for general regular graphs. The graph F is not Ramanujan, and the conjecture restricted to Ramanujan base graphs remains open.
ER  -