Colour-biased Hamilton cycles

Dirac’s Theorem states that every (n-vertex) graph with minimum degree at least n/2 contains a Hamilton cycle. A discrepancy version of this theorem, proved by various groups, states that every r-colouring of the edges of every graph with minimum degree at least (1/2 + 1/2r + o(1))n contains a Hamilton cycle where one of the colours appears at least (1 + o(1))n / r times. We generalise this result by asymptotically determining the maximum possible value f_{r, α}(n) for every α >= 1/2 such that every r-colouring of the edges of every graph with minimum degree at least αn contains a Hamilton cycle where one of the colours appears at least f_{r, α}(n) times.

Lee and Sudakov extended Dirac’s theorem to the setting of random graphs by showing that a random graph (above the threshold to contain a Hamilton cycle) typically has the property that every spanning subgraph with minimum degree at least (1/2+o(1))np contains a Hamilton cycle. We show that such a random graph typically satisfies that every r-colouring of the edges of every spanning subgraph with minimum degree at least αn contains a Hamilton cycle where one of the colours appears at least f_{r, α}(n) times. This is asymptotically optimal and strengthens a result of Gishboliner, Krivelevich and Michaeli.

In this talk I will share some of the ideas behind our proofs. This is joint work with Natalie Behague and Debsoumya Chakraborti.