Allan Lo: Proof of the 1-factorization and Hamilton decomposition conjectures

We prove the following results (via a unified approach) for all sufficiently large n:

1. [1-factorization conjecture] Suppose that n is even and d >= n / 2. Then every d-regular graph G on n vertices has a decomposition into perfect matchings. Equivalently, the edge-chromatic number of G is d.
2. [Hamilton decomposition conjecture] Suppose that d >= (n-1) / 2. Then every d-regular graph G on n vertices has a decomposition into Hamilton cycles and at most one perfect matching.
3. [Optimal packings of Hamilton cycles] Suppose that G is a graph on n vertices with minimum degree at least n/2. Then G contains at least (n-2)/8 edge-disjoint Hamilton cycles.

In the talk, I shall sketch the proof of the Hamilton decomposition conjecture when G is close to the union of two disjoint cliques.

This is joint work with Béla Csaba, Daniela Kühn, Deryk Osthus and Andrew Treglown