The walk through the middle levels

A Gray code visits every binary word of $n$ places, changing one place per step. Along the way it wanders through the cube’s levels — the words with no ones, with one, with two — climbing and falling as it adds and removes ones. The pattern of which places change can be controlled, and every place can be made to do its share. A stricter demand is to control the levels: to walk through a chosen set of words, changing one place per step, and never step outside it.

The sharpest version of that demand turned out to be one of the hardest problems in the combinatorics of the cube.

On five places there are ten words with two ones and ten with three. The walk in the figure visits all twenty, alternating between the two levels, each step adding a one or removing one. From 00011 it adds a one to reach 01011, removes a different one to reach 01001, and so on round the ring, returning to 00011 after twenty steps. An exhaustive search finds 24 such walks.

Why the middle two #

A walk that changes one place per step moves between neighbouring levels at every step: adding a one goes up a level, removing one goes down. So a walk confined to two neighbouring levels alternates between them, and a closed walk alternating between two sets must visit them equally often.

The number of words with $j$ ones among $n$ places is the binomial coefficient $\binom{n}{j}$, and the row of Pascal’s triangle for seven places reads 1, 7, 21, 35, 35, 21, 7, 1. Neighbouring entries are equal only in the middle, and only when $n$ is odd. So the only pair of neighbouring levels that a closed walk can cover completely is the middle pair, the words with $k$ and $k + 1$ ones among $2k + 1$ places.

For an even number of places there is no such pair at all. On six places the levels run 1, 6, 15, 20, 15, 6, 1, and the middle level of twenty stands alone between two levels of fifteen; any walk between the middle and a neighbour must leave five of the middle words unvisited. The equality of sizes is the same kind of condition as the evenness of every place’s count — a necessary balance, checked before any search — and for odd lengths it holds, which is exactly where the difficulty begins, because a necessary condition that holds says nothing about whether the walk exists.

The question — does such a walk exist for every $k$? — is the middle levels problem. Ivan Havel posed it in 1983, Marc Buck and Doug Wiedemann independently a year later, and it circulated for three decades as the middle levels conjecture. Donald Knuth, collecting it in The Art of Computer Programming, rated the exercise 49 on a scale where 50 means an unsolved research problem.

Small cases, and what they suggest #

The small cases are easy, and deceptively so. For $k = 1$ there are three places, and the middle levels are the three words with one one and the three with two — a hexagon, walked round in the obvious way. For $k = 2$ there are twenty words and the search in the first figure finds 24 walks.

For $k = 3$ there are seventy words, each joined to four others, and a plain depth-first search stalls: it builds long paths that cannot be closed and backtracks through an astronomical number of them. What finds the walk in the figure is a different strategy, rotation–extension, due to Lajos Pósa. Grow a path from one end; when the end has no unvisited neighbour, pick a neighbour already on the path and reverse the stretch of path beyond it, which gives the path a new end without losing any word. Repeated with random choices, this finds a Hamiltonian cycle on the seventy words within a few thousand moves.

For $k = 4$, with 252 words, the same search succeeds as quickly. By 2009 such cycles had been found by computer for every $k$ up to 17, and by 2011 for $k = 19$ — graphs with tens of billions of words. That is strong evidence, and it is the kind that can fail. Small cases lie often enough in this subject that a conjecture checked to $k = 19$ was still a conjecture, and a proof was expected to need an idea that no search would supply.

Catalan numbers hiding in the middle #

The middle levels have more structure than their size suggests, and the structure is a classical count. Take a word of $2k + 1$ places with $k$ ones and turn it round cyclically, moving the first place to the end, $2k + 1$ times. The rotations are all different, because a word whose rotations repeated would have its ones spread evenly round the circle in some number of blocks, and $k$ ones among $2k + 1$ places cannot be divided evenly. So the $\binom{2k+1}{k}$ words fall into classes of exactly $2k + 1$ rotations each.

The number of classes is $\binom{2k+1}{k}/(2k+1)$, which for $k = 2$ is $10/5 = 2$ and for $k = 3$ is $35/7 = 5$ — the Catalan numbers, the sequence that counts bracketings, triangulations and lattice paths that never cross the diagonal. That is the cycle lemma: of the $2k + 1$ rotations of each word, exactly one reads as a balanced bracket sequence followed by one extra closing bracket, when ones are read as opening brackets and zeros as closing ones.

This is what the covering by small cycles is built from. Pair each word of the lower level with a word of the upper level by adding a one in a position chosen by its bracket structure, and pair it with another by a second rule; the two pairings together are a set of disjoint cycles covering every word, and the cycles can be described through the bracket sequences, which is to say through the Catalan structures. The joining step of the proof then works on those descriptions — on trees and bracket sequences — rather than on the cube’s words directly, which is where the problem became tractable.

Why a search is not a proof, and why this one was hard #

The middle levels are a large, highly symmetric, sparse graph: each word with $k$ ones is joined to the $k + 1$ words obtained by adding a one, and each word with $k + 1$ ones to the $k + 1$ obtained by removing one. Every vertex has the same number of neighbours, and the graph looks the same from every vertex. Those properties make random search succeed and make structured construction difficult, because there is no distinguished place to start and no obvious way to decompose the graph into pieces whose cycles can be joined.

The natural approach, and the one that eventually worked, is to find a collection of disjoint cycles that together cover every word, and then to join them into one. Covering by cycles is comparatively easy — there are classical constructions that do it, built from the way Catalan-number structures such as bracket sequences sit inside the middle levels. Joining is hard, because merging two cycles means finding a place where they run side by side and swapping two pairs of edges, and every swap must be chosen so that it does not disturb the swaps made elsewhere.

Torsten Mütze published a proof in 2016, in the Proceedings of the London Mathematical Society, that such a joining is always possible, so that the middle levels of every odd-dimensional cube have a Hamiltonian cycle. The proof ran to some forty pages. In 2018 Petr Gregor, Mütze and Jerri Nummenpalo gave a shorter one, and the construction is now efficient enough that each next word of the cycle can be computed in constant time on average — the middle levels have a Gray code as usable as the reflected one, if much harder to describe.

Walking a single level by swaps #

The middle levels problem asks for a walk between two levels. A single level cannot be walked at all by one-place changes, since each such change leaves the level. But it can be walked by a slightly larger step.

A word with $k$ ones names a choice of $k$ things from $n$, and the natural step within a level is a swap: one thing leaves the choice and another enters, which changes two places, a one becoming zero and a zero becoming one. An order of all the $k$-element choices in which each step is a swap is called a revolving door, and one exists for every $n$ and $k$. The construction is a recursion of the reflected kind: list the choices from $n - 1$ things, then the choices that include the $n$-th thing in reverse order of what remains. Albert Nijenhuis and Herbert Wilf made it standard in the 1970s.

The revolving door is easy and the middle levels walk is hard, and the difference is instructive. The revolving door allows any swap, so every choice has $k(n - k)$ neighbours; the middle levels walk must reach each word by a single change and leave by another, and alternating between levels removes the freedom that makes the revolving door’s recursion work. A middle levels cycle, read at every other step, is a revolving door on the $k$-level whose swaps are constrained to pass through a common word of the level above — a much thinner set of steps.

The same question on other graphs #

The middle levels problem is one member of a family of questions about symmetric graphs that are easy to state and hard to answer.

The Kneser graphs join two $k$-element subsets of $n$ things when they share nothing, and their colourings are the subject of a topological theorem. Whether they have Hamiltonian cycles was open for decades, with the Petersen graph — the Kneser graph of 2-element subsets of 5 things — as the famous exception that has none. In 2023 Arturo Merino, Mütze and Namrata proved that every connected Kneser graph except the Petersen graph is Hamiltonian, using the middle levels methods as a key ingredient. The middle levels graph and the Kneser graphs are closely related: two choices of $k$ things from $2k + 1$ that share nothing are exactly the ones joined, through their complements, in the middle levels.

The Cayley graphs of finite groups are another family in the same position. A group drawn as a map, with one dot per element and one arrow per generator, looks the same from every dot, and whether every such graph has a Hamiltonian cycle is open even for groups as well understood as the symmetric groups with some generating sets. For the commutative groups it is known, and for several other classes, and in each case the proof is specific to the class. The cube is itself a Cayley graph, of the group of binary words under exclusive-or, and the reflected Gray code is its Hamiltonian cycle; the middle levels are not a Cayley graph, which is part of why they resisted.

What the figures cannot show #

The figures draw cycles for $k$ up to 4 and count them for $k$ up to 2. The cycles are found by randomised search with fixed seeds, and each is checked step by step; they establish existence for those $k$ and nothing else. The theorem for every $k$ is Mütze’s, and it is a construction of a different kind from anything a figure can display — its cycles are specified by rules about bracket sequences and their rotations, not found.

The ring drawings place each word at its position in the cycle and cannot show why the cycle exists or how it relates to the cube’s geometry. Two words adjacent on the ring differ in one place; words far apart on the ring can differ in one place as well, since each word has $k + 1$ neighbours and the cycle uses only two of them. The drawing shows the order, not the graph.

The randomised search also says nothing about how typical its cycles are. Rotation–extension wanders through the space of long paths more or less at random, and the cycle it closes is whichever one it happens to reach first; a different seed gives a different cycle. That is the right tool for existence, and the wrong one for structure, which is why the search’s quick success on seventy and 252 words was never taken as a hint of how a proof might go.

And the count of 24 cycles for five places is exhaustive, while for seven places the number of cycles is not drawn and is very large. The growth of the number of middle levels cycles with $k$ is known only in rough terms, and nothing about it follows from the three cases shown.

Still open: every symmetric graph #

In 1969 László Lovász asked whether every connected graph that looks the same from every vertex — every vertex-transitive graph — has a path through all its vertices. The middle levels graph is vertex-transitive, and so are the cube, the Kneser graphs and the Cayley graphs of every finite group. Only five connected vertex-transitive graphs are known to have no Hamiltonian cycle: the complete graph on two vertices, the Petersen graph, the Coxeter graph, and graphs obtained from the last two by replacing each vertex with a triangle. All of them have Hamiltonian paths. The Petersen graph, for instance, has ten vertices and cannot be toured in a closed walk, but a walk through all ten that does not return home is easy to find — which is why the conjecture is stated for paths and why the handful of exceptions to the cycle version have never been taken as evidence against it.

Whether every connected vertex-transitive graph has a Hamiltonian path is Lovász’s conjecture, and it is open. Some believe the opposite, that counterexamples exist and are merely hard to find. The middle levels theorem is one of the largest families on which the conjecture has been confirmed in its strong, cyclic form, and it took thirty years for one family. The difficulty the cube keeps presenting is the one the first walk on it already pointed to: existence of a Hamiltonian cycle has no general test, and each symmetric family seems to need its own proof.

Two levels, and thirty years #

The question fits in a line: walk through every word of $2k + 1$ places with $k$ or $k + 1$ ones, one change at a time, and come home. The necessary condition is a count — the two levels must be equal in size, which forces them to be the middle pair. The small cases are solved in an instant: a hexagon, 24 cycles on twenty words, and search that finds cycles on seventy and 252 words almost at once.

And for thirty years nobody could prove that the pattern continues. What was missing was not evidence but structure: a way of building the cycle that works for every $k$ at once, which in the end came from covering the levels with many small cycles and proving they can always be sewn together. The contrast with the reflected Gray code, which covers the whole cube with a one-line recursion, is the measure of how much a single restriction — stay between two levels — changes a problem about the cube.

The proof also changed what the problem is for. A Gray code through the middle levels lists every choice of $k$ things from $2k + 1$ so that consecutive choices differ by adding or removing a single thing, alternately; it is a revolving door with an intermediate stop at every step. Once the cycle could be computed in constant time per step, it became a practical way to generate such choices, and the techniques built to join its small cycles have since been turned on the Kneser graphs, on other levels of the cube, and on the general question of which symmetric graphs can be toured — the question that Lovász’s conjecture keeps open.