What was already known
The human authors had independently proved the edgeless case by a different generating-function and shifting argument before receiving the model proof.
AI involvement
At Gowers's broad prompt to choose an approachable open combinatorics problem, ChatGPT 5.5 Pro selected this conjecture and produced an affirmative proof. Its retained key idea is a probabilistic coupling proving a multiset-shadow inequality, unlike the authors' proof.
The model selected the problem from a broad request and generated the alternative proof without reported human mathematical hints.
Importance
Adds a checked, distinct proof of a useful special case and some disconnected-graph consequences.
Limitations
The all-graphs conjecture remains open. The human authors’ separate proof and graph applications are credited to them.
Technical verification
The human authors expressly confirmed correctness of the AI-produced Appendix A proof and printed its full argument. This is a source-reported complete human proof check, not an AIProofWatch reproduction.
Formal checking
Reviewed the AI proof for correctness and paraphrased the complete argument
- Checker
- The first two paper authors
- Scope
- The Appendix A multiset-shadow proof of Theorem 1.5
- Basis
- Reported by the linked checker
Checking a formal statement does not establish that it matches the original problem.
Human understanding
The authors explain the AI proof's probabilistic multiset-shadow coupling and how it differs from their own shifting/generating-function proof.
Correction and publication history
Adds a checked, distinct proof of a useful special case and some disconnected-graph consequences.
Read this published revision