This post continues my series on favorite theorems of the 21st century. For a complete overview of the categories and list of my previous selections, see this previous blog post. In the category Between the Centuries within Combinatorics, my personal favorite is the cycle decomposition theorem of Šajna.
One of the oldest results in combinatorics is Kirkman’s theorem from 1847, which states that for every integer the edges of the complete graph can be partitioned into edge-disjoint triangles. It is straightforward to verify that these congruence conditions on are necessary. Kirkman’s theorem became the starting point of several long-running research programs, some of which spanned more than a century.
One such program asked for decompositions of into cycles of a fixed length . We say that a graph is -decomposable if its edge set can be written as a disjoint union of cycles of length (these cycles need not be vertex-disjoint).
A particularly famous special case is . A classical result, attributed to Walecki by Lucas in 1892, asserts that for every odd the complete graph can be decomposed into cycles of length . Such cycles are called Hamiltonian cycles.
There are several obvious necessary conditions for a -decomposition of to exist. First, one must have . Second, the number of edges of , namely , must be divisible by . Finally, since every cycle contributes degree at each of its vertices, all vertex degrees in must be even, which forces to be odd.
In a landmark paper from 2002, Šajna (Šajna 2002) proved that these obvious necessary conditions are, in fact, sufficient. Her result culminated a long sequence of partial advances and brought a century-old project to a definitive conclusion. She also established an analogous statement for even , in which one removes a perfect matching from in order to make all degrees even.
The proof of Theorem opened the door to further progress. In 2014, Bryant, Horsley, and Pettersson (Bryant, Horsley, and Pettersson 2014) generalized Šajna’s result to decompositions into cycles of unequal lengths. They showed that for any odd and any integers satisfying the complete graph can be decomposed into cycles of lengths . Similarly, if is even and then can be decomposed into cycles of these lengths together with a perfect matching. This result resolved a conjecture posed by Alspach in 1981.
More generally, given any graph , we say that a graph is -decomposable if its edge set can be partitioned into copies of . Theorem settles the case where and . A closely related setting arises when is a -factor, that is, an -vertex graph in which every vertex has degree . Equivalently, a -factor is a disjoint union of cycles. The celebrated Oberwolfach problem asks for which odd integers and which -vertex -factors the complete graph admits an -decomposition. In 2021, Glock, Joos, Kim, Kühn, and Osthus (Glock et al. 2021) proved that such a decomposition exists for every -factor , provided that is sufficiently large.