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

2020/01/05 by Asaf Ferber, Ferber, Asaf, Kaarel Haenni +3
Mathematics · Engineering · #Limits and Structures in Graph Theory #Analytic Number Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2001.01149

Abstract

Let H₁,…,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₁,…,H_k being edge-disjoint is (1+o(1))e^-2\binomk2. This extends a corresponding estimate obtained by Robbins in the case k=2.

Related

• Minimum degree edge-disjoint Hamilton cycles in random directed graphs
• Edge-disjoint Hamilton cycles in random graphs
• Hamilton cycles in a semi-random graph model
• Packing Loose Hamilton Cycles
• On Kotzig's conjecture in random graphs