In 1963, Anton Kotzig famously conjectured that K₍, the complete graph of order n, where n is even, can be decomposed into n-1 perfect matchings such that every pair of these matchings forms a Hamilton cycle. The problem is still wide open and here we consider a variant of it for the binomial random graph G (n, p). We prove that, for every fixed k, there exists a constant C=C (k) such that, when p C nn, with high probability, G (n, p) contains k edge-disjoint perfect matchings with the property that every pair of them forms a Hamilton cycle. In fact, our main result is a very precise counting result for Kₙ. We show that, given any k edge-disjoint perfect matchings M₁, , Mₖ, the probability that a uniformly random perfect matching M^* in Kₙ has the property that M^* Mᵢ forms a Hamilton cycle for each i k is Θₖ (n^-k/2). This is proved by building on a variety of methods, including a random process analysis, the absorption method, the entropy method and the switching method. The result on the binomial random graph follows from a slight strengthening of our counting result via the recent breakthroughs on the expectation threshold conjecture.
Glock et al. (Thu,) studied this question.