Title: On Kotzig's conjecture in random graphs Show Chinese title

Title: 关于随机图中的Kotzig猜想

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\ge \frac{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,\dots,M_k$, the probability that a uniformly random perfect matching $M^*$ in $K_n$ has the property that $M^*\cup M_i$ forms a Hamilton cycle for each $i\in [k]$ is $\Theta_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. Show Chinese abstract

Abstract: 1963年，安东·科茨基著名地猜想，$K_{n}$，阶数为$n$的完全图，其中$n$是偶数，可以分解为$n-1$个完美匹配，使得每对这些匹配形成一个哈密顿循环。 这个问题仍然开放，这里我们考虑它在二项随机图$G(n,p)$中的变体。 我们证明，对于每个固定的$k$，存在一个常数$C=C(k)$，使得当$p\ge \frac{C \log n}{n}$时，高概率下$G(n,p)$包含$k$个边不相交的完美匹配，且每对之间形成一个哈密顿回路。事实上，我们的主要结果是对$K_n$的非常精确的计数结果。 我们证明，给定任何$k$个边不相交的完美匹配$M_1,\dots,M_k$，一个在$K_n$中均匀随机的完美匹配$M^*$使得$M^*\cup M_i$对每个$i\in [k]$形成一个哈密顿循环的概率是$\Theta_k(n^{-k/2})$。 这是通过多种方法的结合来证明的，包括随机过程分析、吸收法、熵法和切换法。 二项式随机图的结果是通过对我们的计数结果进行轻微加强，并利用最近在期望阈值猜想上的突破得出的。