The probability of selecting $k$ edge-disjoint Hamilton cycles in the complete graph

Abstract

Let $H_1,\dots ,H_k$ be Hamilton cycles in $K_n$, chosen independently and uniformly at random. We show, for $k=o(n^{1/100})$, that the probability of $H_1,\dots ,H_k$ being edge-disjoint is $(1+o(1))e^{-2\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. This extends a corresponding estimate obtained by Robbins in the case $k=2$.

8 pages