Seminar: The Hamilton-Waterloo Problem

Given a graph G, a 2-factor is a spanning subgraph of G where every vertex has degree 2, and is hence a collection of cycles. A 2-factorization of G is a set of 2-factors that between them partition the edges of G. Given a graph G, two 2-factors F₁ and F₂ and non-negative integers $\alpha$ and $\beta$, the Hamilton-Waterloo problem, HWP(G; F₁,F₂;$\alpha$,$\beta$) asks for a partition of the edges of G into $\alpha$ factors isomorphic to F₁ and $\beta$ factors isomorphic to F₂. Classically, G is the complete graph, K_v, or K_v minus a 1-factor when v is even.

In this talk we concentrate on the uniform case, where F₁ is a collection of n-cycles (C_n's) and F₂ is a collection of m-cycles (C_m's). Specifically, given non-negative integers v, m, n, $\alpha$, $\beta$, the Hamilton-Waterloo problem, HWP(G;n,m;$\alpha$,$\beta$), asks for a factorization of the complete graph, G into $\alpha$ C_n-factors and $\beta$ C_m-factors. When G is K_v (or K_v minus a 1-factor when v is even), m | v, n | v and $\alpha+\beta = (v-1)/2$ are necessary conditions. However, other options for G, such as a 'blowup' of a complete graph or a cycle are also relevant in obtaining solutions to the original problem.