A short proof of the middle levels theorem

- Faculty of Mathematics and Physics, Charles University in Prague
- More about Petr Gregor

- Institut für Mathematik, Technical University Berlin
- More about Torsten Mütze

- Institute of Theoretical Computer Science, ETH Zürich
- More about Jerri Nummenpalo

### Editorial introduction

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,…,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⊂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 A1,B1,…,AN,BN (where N=(2n+1n)) such that each set of size n or n+1 appears exactly once, and such that A1 is contained in B1, which contains A2, which is contained in B2, and so on all the way up to BN, which contains A1?

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 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 C1,C2 in a particular way, then the symmetric difference of all three cycles is a single cycle that visits the same vertices as C1 and C2. The authors prove various lemmas about the cycles in 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