GSS Fall 2017 - Joe Briggs: Topologists outperform finite graph theorists in Hamilton decomposition
Channel: Grad Student
Date: 2017-10-25

One of the oldest results in graph theory says that complete graphs on an $2k+1$ number of vertices can be $k$-edge colored with a Hamilton cycle in each color. Because we enjoy coloring finite graphs for a living, many graph theorists have asked which other classes of $2k$−regular graphs can be similarly colored. But looks can be deceptive, and 2 straightforward-sounding conjectures in this vain have resisted much progress for 40 years! Remarkably, it has been shown recently that 2 particular countably infinite analogues of these questions have affirmative answers.

We will define Cartesian graph products, Cayley graphs, and the notion of an infinite Hamilton cycle that makes most sense from a topological viewpoint here. We will also draw many pictures. Remarkably, it appears that introducing any finiteness makes these problems more difficult!