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   -   am2759@cam.ac.uk

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).

View abstract PDF