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\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 proved that, for every fixed $k$, there is $C=C(k)$ such that whp $G(n,C\log 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.

arXiv comment24 pages, 4 figures