A short proof of the middle levels theorem

• Published in: Discrete analysis 2018-05, p.1-12
• Main Authors: Gregor, Petr, Mütze, Torsten, Nummenpalo, Jerri
• Format: Article
• Language: English
• ISSN: 2397-3129; 2397-3129
• DOI: 10.19086/da.3659

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 i