A hitting-time version of Kotzig's conjecture in random graphs
Abstract
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 ≥ 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 proved that, for every fixed k, there is C=C(k) such that whp G(n,Clog n/n) contains k perfect matchings with the Kotzig property. We strengthen this result by showing a hitting time version: for every fixed k, whp the hitting time in the random graph process for finding k edge-disjoint perfect matchings with the Kotzig property is the same as the hitting time for a graph with minimum degree k. This is a generalisation of the celebrated result of Bollobás and Frieze for even n establishing the hitting time for k edge-disjoint Hamilton cycles. The proof uses several ideas. We first design a coupling, via a randomised algorithm, of the random graph at the hitting time with k almost-independent perfect matchings and a set of random reservoir edges, which may be of independent interest. We then prove various statistical properties of these matchings, in particular concerning the cycle structure of the $2$-factors formed by pairs of matchings. This includes a novel concept of ``shuffledness'', which we establish through a careful exposure argument and a concentration inequality for random permutations. Finally, we show that the initial $2$-factors can be merged into Hamilton cycles, using the random reservoir edges, by analysing certain Pósa-type rotations via branching processes.
Related
- Sprinkling for random regular graphs and Kim-Vu's sandwich conjecture
- Counterexamples to the Mao-Wu-Xu spectral conjecture and a three-scale boundary for spherical random graphs
- Distribution of the First Hitting Point on a Boundary Set for a Random Walk in a Lattice Strip
- Capacities and Hitting Times for Simple and (critical) Branching Random Walk Sausages
- Hitting time for loose Hamilton cycles in the random hypergraph process
BibTeX
@misc{glock2026hittingtime,
title = {{A hitting-time version of Kotzig's conjecture in random graphs}},
author = {Stefan Glock and Lyuben Lichev and Amedeo Sgueglia},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02128},
eprint = {2611.02128},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02128},
}
RIS
TY - UNPB
TI - A hitting-time version of Kotzig's conjecture in random graphs
AU - Stefan Glock
AU - Lyuben Lichev
AU - Amedeo Sgueglia
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02128
UR - https://arxiv.org/abs/2611.02128
AB - 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 ≥ 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 proved that, for every fixed k, there is C=C(k) such that whp G(n,Clog n/n) contains k perfect matchings with the Kotzig property. We strengthen this result by showing a hitting time version: for every fixed k, whp the hitting time in the random graph process for finding k edge-disjoint perfect matchings with the Kotzig property is the same as the hitting time for a graph with minimum degree k. This is a generalisation of the celebrated result of Bollobás and Frieze for even n establishing the hitting time for k edge-disjoint Hamilton cycles. The proof uses several ideas. We first design a coupling, via a randomised algorithm, of the random graph at the hitting time with k almost-independent perfect matchings and a set of random reservoir edges, which may be of independent interest. We then prove various statistical properties of these matchings, in particular concerning the cycle structure of the $2$-factors formed by pairs of matchings. This includes a novel concept of ``shuffledness'', which we establish through a careful exposure argument and a concentration inequality for random permutations. Finally, we show that the initial $2$-factors can be merged into Hamilton cycles, using the random reservoir edges, by analysing certain Pósa-type rotations via branching processes.
ER -