A short proof of the middle levels theorem

A short proof of the middle-levels theorem, Discrete Analysis 2018:8, 12 pp.

Let $n$ be a positive integer, and define a bipartite graph where one vertex set consists of all subsets of $\{1,2,\dots,2n+1\}$ of size $n$, the other consists of all subsets of size $n+1$, and we join a set $A$ of size $n$ to a set $B$ of size $n+1$ if and only if $A\subset B$. The following innocent looking question was an open problem for a long time: does this graph contain a Hamilton cycle? That is, can we find a sequence of sets $A_1,B_1,\dots,A_N,B_N$ (where $N=\binom{2n+1}n$) such that each set of size $n$ or $n+1$ appears exactly once, and such that $A_1$ is contained in $B_1$, which contains $A_2$, which is contained in $B_2$, and so on all the way up to $B_N$, which contains $A_1$?

For very small values of $n$, one can find Hamilton cycles, and one can even imagine that one is finding them in a potentially systematic way, but in the end all patterns seem to evaporate. One difficulty is that it can be shown that in any Hamilton cycle, each of the $2n+1$ possible edge directions must occur the same number of times. This means that if one tries to use a solution to the $n-1$ case to build a Hamilton cycle for the $n$ case, one will have to chop it up into exponentially many pieces. (This is in sharp contrast with the case of the entire $n$-dimensional cube, where one can easily prove that it contains a Hamilton cycle by taking two parallel Hamilton cycles in copies of an $(n-1)$-dimensional cube, removing an edge from the first and the corresponding edge from the second, and adding two linking edges to form a single Hamilton cycle.)

Another approach that one might imagine attempting to use is a probabilistic one, perhaps creating most of a Hamilton cycle randomly and then making a few adjustments at the end in order to complete it. But this kind of argument also runs into problems: the constraints are not too severe to start with, but the more of the cycle one constructs, the stronger they become, and without a clever idea one gets stuck long before completing a cycle.

In 2014 the problem, by then over 30 years old, was solved by Torsten Mütze [1], one of the authors of this paper, using a long and technical (and constructive) argument. This paper gives a much shorter and simpler argument that avoids nearly all the technicalities of the first argument and thereby makes Mütze’s remarkable result truly accessible for the first time.

Very roughly, the idea behind the proof is to begin by finding a certain special collection $\mathcal C$ of vertex-disjoint cycles that includes all vertices. If there were only one cycle in the collection, we would be done, but since that is not the case, we have to join them together. This is done by using an auxiliary collection of 6-cycles: if a 6-cycle intersects the union of two cycles $C_1,C_2$ in a particular way, then the symmetric difference of all three cycles is a single cycle that visits the same vertices as $C_1$ and $C_2$. The authors prove various lemmas about the cycles in $\mathcal C$ and the 6-cycles, which they then use to prove that this process can be continued until there is just one cycle left. (The reason 6-cycles are used, rather than 4-cycles as in the case of the complete cube, is brutally simple: it is easy to check that the middle-layers graph does not contain any 4-cycles.)

The proof gives rise to an efficient algorithm for actually finding Hamilton cycles in the middle-layers graph. If you are curious to see what the cycles look like, the algorithm can be run online on this web page.

[1] Torsten Mütze, Proof of the middle levels conjecture, Proc. London Math. Soc. 112 (2016), pp. 677-713. Also available at arXiv:1404.4442