google-deepmind / google-deepmind/formal-conjectures
Formalise WOW-284, disproved by the Hoffman–Singleton graph
- Dominant language
- Lean
- Stars
- 1.3k
- Forks
- 485
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 327
Description
### What is the conjecture
WOW-284 states that if a finite simple graph `G` is connected, has at least three vertices, and has girth at least five, then its minimum dual degree is at most the negative of its least distance eigenvalue:
`δ*(G) ≤ -∂min(D(G))`.
Aouchiche and Hansen record the conjecture as Conjecture 7.16 in *Distance Spectra of Graphs: A Survey* ([DOI](https://doi.org/10.1016/j.laa.2014.06.010)), attributing it to Fajtlowicz's 1998 *Written on the Wall* report.
The conjecture is false. The 50-vertex Hoffman–Singleton graph is 7-regular, connected, and has girth five. Its distance spectrum is
`{91^(1), 1^(21), (-4)^(28)}`,
so `δ*(G) = 7 > 4 = -∂min(D(G))`.
The explicit coordinate construction and counterexample have been formally verified in Lean 4.31. The permanent proof source is at:
https://github.com/SamPetkov/wow284/tree/08ae20d27792d5f5c2a2587d51b5e2256c1ae06a/lean
This contribution intentionally covers only the fully formalized 50-vertex counterexample. Further examples and a generalization are under development and are not claimed here.
### Prerequisites needed
Definitions of graph distance matrices, dual degree, and the relevant least-eigenvalue statement may need to be supplied locally if the current Mathlib release does not expose a suitable API. The long external proof should be linked with `@[formal_proof using lean4 at …]`, following the repository policy.
### [AMS categories](https://github.com/google-deepmind/formal-conjectures/labels?q=ams-)
* ams-05
### Choose either option
- [x] I plan on adding this conjecture to the repository
- [ ] This issue is up for grabs: I would like to see this conjecture added by somebody else
Contributor guide
Research direction
Start by reading the verified Lean 4.31 source in the linked wow284/lean directory and inspect how formal-conjectures links external proofs with @[formal_proof using lean4 at …]. Check whether the current Mathlib release provides the needed graph-distance, dual-degree, and least-eigenvalue APIs. Done means the 50-vertex Hoffman–Singleton counterexample is added with the required local definitions or imports and proof link.
Written by the indexing model from the issue text.
Assessment
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100