Kotzig's conjecture and Wormald's random-regular-graph conjecture
For every integer , the complete graph has a decomposition into perfect matchings such that, for every pair , the graph with edge set is a Hamiltonian cycle.
References
- A hitting-time version of Kotzig's conjecture in random graphs — arXiv — Stefan Glock, Lyuben Lichev, Amedeo Sgueglia
Source: arXiv
Progress summary
A November 2026 report claims a sharp threshold for a random-graph version, but neither the complete-graph conjecture nor the random-regular-graph conjecture is settled.
The problem combines Kotzig’s 1963 conjecture that has a perfect -factorisation with Wormald’s conjecture that random fixed-degree regular graphs have one asymptotically almost surely. Both exact conjectures remain open.
Known results
- For fixed , Glock and Sgueglia (2025) proved that typically contains edge-disjoint perfect matchings with pairwise Hamiltonian unions when .
- Glock and Sgueglia (2025) obtained corresponding extension-counting estimates and a deterministic extension theorem under a non-overlap condition.
- A 2026 preprint constructs asymptotically almost all of a complete-graph factorisation with the pairwise Hamiltonian property, but not an exact solution.
November 2026 hitting-time claim
Glock, Lichev, and Sgueglia report a sharp hitting-time theorem for every fixed in the binomial random-graph process. The retrieved literature does not independently corroborate this claim; the earlier paper instead lists the hitting-time statement as open. It is progress on a random-graph variant, not a solution of either exact conjecture.
Current status (as of November 2026): The complete-graph and random-regular-graph conjectures remain open; a sharper random-graph hitting-time result is claimed but unverified.
Solutions 0
No solutions have been posted yet.