On Kotzig's conjecture in random graphs

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 log n/n, 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.