Kotzig's Perfect 1-Factorisation Conjecture, Asymptotically
Kotzig conjectured that for every even the complete graph decomposes into perfect matchings such that every pair of them forms a Hamilton cycle. An asymptotic version holds: decomposes into perfect matchings of which have the property that any pair forms a Hamilton cycle.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Construction
- Field
- Design theory
- Posed by
- Anton Kotzig
- Year posed
- 1964
- Years open
- 62y
- Solved
- 2026-07-10
- Model
- ChatGPT 5.4
- Vendor
- OpenAI
- Collaborators
- Yangyang Cheng, Amedeo Sgueglia
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 30 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
asymptotic form only; Kotzig's conjecture itself remains far from solved
What the AI did
The authors state that the construction in Theorem 1.3, a generalisation of the one in their introduction, was generated by ChatGPT 5.4, which also supplied a correct but long proof of it. The proof they present is a cleaner and substantially different one of their own, and the proof of the main theorem, Theorem 1.2, was obtained entirely by the authors. The model's construction is nonetheless load-bearing: the main result is built by deleting a random subset of the matchings it produces.
Verification
arXiv preprint that routes through a robust-expander result of Kuhn and Osthus; not yet peer-reviewed.
Source
arXiv:2607.09459 - The perfect 1-factorisation conjecture holds asymptotically