Seminar

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.
Organizers
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU

Program
Contact

Klas Markström

klas.markstrom@math.umu.se

Other
information

For practical matters at the Institute, send an e-mail to secretary@mittag-leffler.se