Discrepancy of Hamilton Cycles in Random Subgraphs

The concept of discrepancy for Hamilton cycles has recently attracted significant attention: for a graph \(G\) with edges coloured red or blue, we are interested in finding a Hamilton cycle with many more edges in the dominant colour. Bounds for discrepancy for Hamilton cycles were explored deterministically by Balogh, Csaba, Jing and Pluhar, and in the random graph by Gishboliner, Krivelevich and Michaeli. Following a result of Krivelevich, Lee and Sudakov on the robustness of Dirac graphs with respect to Hamiltonicity, we examine the discrepancy for Hamilton cycles in random subgraphs of graphs with high minimum degree.

More precisely, we show that for \(c>0\) there exists \(k>0\) such that for \(G\) a graph on \(n\) vertices with minimum degree at least \((\frac{3}{4}+c)n\), a random subgraph \(G_p\) with \(p\) above the Hamiltonicity threshold asymptotically almost surely satisfies that any 2-colouring of its edges leads to a Hamilton cycle with discrepancy at least \(kn\). Both the minimum degree and the bound on \(p\) are asymptotically optimal.