VibeMathedMath problems solved with AI
Sign in

The Laplacian Sn,nS_{n,n} conjecture

The Laplacian matrix of a simple graph on nn vertices has nn real eigenvalues, the smallest being 00. The Sn,nS_{n,n} conjecture asserts that no simple graph on n≥2n \ge 2 vertices has Laplacian spectrum exactly {0,1,2,…,n−1}\{0, 1, 2, \ldots, n-1\}. It was verified for 2≤n≤152 \le n \le 15 and proved for n≥6 649 688 933n \ge 6\,649\,688\,933, leaving the range between open. Is the conjecture true?

Result
Proved(see note)
Status
Resolved
AI contribution
AI co-developed
Method
Argument
Field
Spectral graph theory
Posed by
Shaun Fallat, Steve Kirkland, Jason Molitierno and Michael Neumann
Year posed
2005
Years open
21y
Solved
2026-09-22
Model
ChatGPT-6 Astra
Vendor
OpenAI
Collaborators
Nathaniel Johnston
Verification
Unreviewed
Publication
Preprint
Significance
22 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

True: no simple graph on n≥2n \ge 2 vertices has Laplacian spectrum {0,1,…,n−1}\{0,1,\ldots,n-1\}. The paper closes the range left between the two previously settled regimes, n≤15n \le 15 and n≥6 649 688 933n \ge 6\,649\,688\,933.

Verification

Checked here on 27 September 2026 against arXiv:2609.26895, posted 22 September. The abstract states the conjecture, records that it was already proved for 2≤n≤152 \le n \le 15 and for n≥6 649 688 933n \ge 6\,649\,688\,933, and claims all remaining cases, so the entry's Resolved is the paper's own claim about the full range rather than an extrapolation. The mathematics was not checked here; five days old, no referee, no formalisation. Nathaniel Johnston works in this area.

Source

Submitted by RustyMarten346 on

Changelog4 changes
  • Micky Mousechanged What was actually shown from “True: no simple graph on $n \ge 2$ vertices has Laplacian spectrum $\{0,1,\ldots,n-1\}$. T…” to “True: no simple graph on $n \ge 2$ vertices has Laplacian spectrum $\{0,1,\ldots,n-1\}$. T…”, also Verification note
  • Micky Mousechanged Statement from “The Laplacian matrix of a simple graph on $n$ vertices has $n$ real eigenvalues, the small…” to “The Laplacian matrix of a simple graph on $n$ vertices has $n$ real eigenvalues, the small…”
  • Rasmus Lindahlapproved this entry
  • RustyMarten346submitted this entry

Discussion