The Bilu-Linial signing conjecture for regular graphs
Bilu and Linial asked whether every connected -regular graph admits a signing of its edges by whose signed adjacency matrix has all eigenvalues in , the Ramanujan interval. A positive answer would give an iterative construction of Ramanujan graphs of every degree; Marcus, Spielman and Srivastava proved the one-sided version, which yields bipartite Ramanujan graphs. Does every regular graph have such a signing?
- Result
- Disproved(see note)
- Status
- Resolved
- AI contribution
- AI-assisted
- Method
- Construction
- Field
- Spectral graph theory
- Posed by
- Yonatan Bilu and Nathan Linial (2004, 2006)
- Year posed
- 2006
- Years open
- 20y
- Solved
- 2026-09-14
- Model
- ChatGPT
- Vendor
- OpenAI
- Collaborators
- Zhiqiang Xu
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 35 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
False for general regular graphs: an explicit cubic graph for which every signing produces an eigenvalue outside the Ramanujan interval. is not itself Ramanujan, and the conjecture restricted to Ramanujan base graphs - the form that would yield Ramanujan graphs of every degree by iteration - remains open.
What the AI did
From the paper: the counterexample and its proof strategy were developed with the assistance of ChatGPT, and the author states that all AI-generated text was reviewed and the mathematics verified. The model is not named more precisely in the disclosure.
Verification
Checked here on 22 September 2026 against arXiv:2609.15591: the abstract gives a finite connected simple cubic graph every signing of which has an eigenvalue outside , and states the limitation plainly - is not Ramanujan, so the conjecture restricted to Ramanujan base graphs remains open. The reference list confirms Bilu and Linial (CPC 13 (2004) and Combinatorica 26 (2006)) and the Marcus-Spielman-Srivastava line. The mathematics was not checked here; eight days old, no referee.