On Kotzig's conjecture in random graphs

Abstract

In 1963, Anton Kotzig famously conjectured that K n , 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 n . We show that, given any k edge-disjoint perfect matchings M 1 , … , M k , the probability that a uniformly random perfect matching M ⁎ in K n has the property that M ⁎ ∪ M i forms a Hamilton cycle for each i ∈ [ k ] is Θ k ( 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.