Colour-biased Hamilton cycles in dense graphs and random graphs

Abstract

A classical result of Dirac says that every $n$-vertex graph with minimum degree at least $\frac{n}{2}$ contains a Hamilton cycle. A `discrepancy' version of Dirac's theorem was shown by Balogh--Csaba--Jing--Pluhár, Freschi--Hyde--Lada--Treglown, and Gishboliner--Krivelevich--Michaeli as follows. Every $r$-colouring of the edge set of every $n$-vertex graph with minimum degree at least $(\frac{1}{2}+\frac{1}{2r}+o(1))n$ contains a Hamilton cycle where one of the colours appears at least $(1+o(1))\frac{n}{r}$ times. In this paper, we generalize this result by asymptotically determining the maximum possible value $f_{r,\hat{I}\pm }(n)$ for every $\hat{I}\pm \in [\frac{1}{2},1]$ such that every $r$-colouring of the edge set of every $n$-vertex graph with minimum degree at least $\hat{I}\pm n$ contains a Hamilton cycle where one of the colours appears at least $f_{r,\hat{I}\pm }(n)$ times. In particular, we show that $f_{r,\hat{I}\pm }(n)=(1-o(1))\min \{(2\hat{I}\pm -1)n,\frac{2\hat{I}\pm n}{r},\frac{2n}{r+1}\}$ for every $\hat{I}\pm \in [\frac{1}{2}+\frac{1}{2r},1]$. A graph $H$ is called an $\hat{I}\pm$-residual subgraph of a graph $G$ if $d_H(v)\ge \hat{I}\pm d_{G[V(H)]}(v)$ for every $v\in V(H)$. Extending Dirac's theorem in the setting of random graphs, Lee and Sudakov showed the following. The Erdős--Rényi random graph $G(n,p)$, with $p$ above the Hamiltonicity threshold, typically has the property that every $(\frac{1}{2}+o(1))$-residual spanning subgraph contains a Hamilton cycle. Motivated by this, we prove the following random version of our `discrepancy' result. The random graph $G\sim G(n,p)$, with $p$ above the Hamiltonicity threshold, typically satisfies that every $r$-colouring of the edge set of every $\hat{I}\pm$-residual spanning subgraph of $G$ contains a Hamilton cycle where one of the colours appears at least $f_{r,\hat{I}\pm }(n)$ times.