Session I.3 - Graph Theory and Combinatorics
Monday, June 12, 15:30 ~ 16:00
Minimum degree edge-disjoint Hamilton cycles in random directed graphs
Adva Mond
Cambridge University, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
At most how many edge-disjoint Hamilton cycles does a given directed graph contain? A trivial upper bound is the minimum between the minimum out- and in-degrees. We show that a typical random directed graph $D(n,p)$ contains precisely this many edge-disjoint Hamilton cycles, given that $p \gt = (\log^C n)/n$ where $C$ is a fixed integer, which is optimal up to a factor of $\operatorname{polylog} n$. Our proof provides a randomised algorithm to generate the cycles and uses a (relatively) recent "online sprinkling" idea, as was introduced by Ferber and Vu, to generate $D(n,p)$, allowing us to control some key properties of the graph.
Joint work with Asaf Ferber (University of California, Irvine) and Kaarel Haenni (Caltech).