google-deepmind / google-deepmind/formal-conjectures

Formalise WOW-284, disproved by the Hoffman–Singleton graph

Open
#4,556 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.