题目: Colour discrepancy of Hamiltonian graphs

报告人：Jared Leon (University of Warwick)

时间：10月14日（星期三） 2:30pm ~ 3:30 pm

地点：数学新楼308

摘要:

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, \alpha}(n)$ for every $\alpha \geq 1/2$ such that every $r$-colouring of the edges of every graph with minimum degree at least $\alpha n$ contains a Hamilton cycle where one of the colours appears at least $f_{r, \alpha}(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 $\alpha n$ contains a Hamilton cycle where one of the colours appears at least $f_{r, \alpha}(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.