Proof of the 1-factorization and Hamilton decomposition conjectures
Graphs, Hypergraphs, and Computing
20 February 14:00 - 15:00
Allan Lo - University of Birmingham
We prove the following results (via a unified approach) for all sufficiently large n:
(i) [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.
(ii) [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.
(iii) [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.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU