{"id":"arxiv/2611.02128","url":"https://arxiv.org/abs/2611.02128","tags":["math.CO"],"score":0,"title":"A hitting-time version of Kotzig's conjecture in random graphs","domain":"math.CO","source":"arxiv","authors":["Stefan Glock","Lyuben Lichev","Amedeo Sgueglia"],"reviews":0,"subject":"math.CO","summary":"A family of perfect matchings on the same vertex set is said to have the Kotzig property if the union of any pair of matchings forms a Hamilton cycle. Kotzig famously conjectured that, when $n$ is even, the complete graph on $n$ vertices can be decomposed into $n-1$ perfect matchings with the Kotzig property. A closely related conjecture of Wormald states that, for fixed $d \\ge 3$, whp a random $d$-regular graph contains $d$ perfect matchings with the Kotzig property. Recently, the first and third authors considered a version of these problems for the binomial random graph $G(n,p)$ and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}