PDFLINK |

# On Hamilton Cycles in Graphs Defined by Intersecting Set Systems

Communicated by *Notices* Associate Editor Emilie Purvine

## 1. Introduction

In 1857 the Irish mathematician William Rowan Hamilton invented a puzzle whose goal is to find a cycle in the graph of the dodecahedron that visits every vertex exactly once. He dubbed it the ‘Icosian game’, as the resulting cycle has exactly twenty (‘icosa’ in ancient Greek) edges and vertices. In honor of Hamilton, a cycle that visits every vertex of a graph exactly once is now called a *Hamilton cycle*. The dodecahedron has the interesting property that it looks the same from the point of view of any vertex. Formally, it is *vertex-transitive*, i.e., any two vertices can be mapped onto each other by an automorphism of the graph. In 1970 Lovász raised a conjecture which can be considered a highly advanced version of the Icosian game. Specifically, he conjectured that every connected vertex-transitive graph admits a Hamilton cycle, apart from five exceptional graphs, which are a single edge, the Petersen graph, the Coxeter graph, and the graphs obtained from the latter two by replacing every vertex by a triangle.

The Petersen graph, shown in Figure 2, is a 10-vertex graph that serves as a famous example and counterexample for many problems in graph theory, and we will encounter it again later in this article. A variant of Lovász’ conjecture asserts that every connected vertex-transitive graph admits a *Hamilton path* (without exceptions), i.e., we still need to visit every vertex exactly once, but the first and last vertex of the tour need not be adjacent. While the Icosian game is about one particular graph, Lovász’ conjecture talks about infinitely many graphs, which on the one hand are very constrained, but on the other hand very hard to get your hands on. One can easily construct numerous explicit families of vertex-transitive graphs for which it is not known whether they are Hamiltonian. An important example for this are *Cayley graphs*, which are defined for a group and a set of generators as the graph that has as vertices all group elements, and whose edges arise by multiplication with a generator. Even for particular groups like the symmetric group, and for generators with certain properties (like two generators, or generators that are involutions), only partial results are known.

In this expository article, we consider another rich family of vertex-transitive graphs, which features prominently throughout combinatorics, namely graphs defined by intersecting set systems. We give an overview of the many beautiful techniques and ingredients devised during the past 40 years that establish the existence of Hamilton cycles in those graphs, thus settling interesting special cases of Lovász’ conjecture. Our discussion starts with the easy instances and ends with the hardest and most general ones, and it emphasizes the key obstacles on this journey.

### 1.1. The hypercube

The starting point is the Boolean lattice, i.e., the inclusion order on all subsets of see Figure ;3. The cover relations of this poset are pairs of sets which differ in a single element, i.e., for some and the corresponding cover graph , is the well-known * hypercube -dimensional*. It is convenient to encode the vertices of as bitstrings of length by considering the characteristic vector of each set, which has the , bit equal to 1 if and only if the element th is contained in the set. With this encoding, edges of connect exactly pairs of vertices that differ in a single bit. This graph is vertex-transitive, and a Hamilton cycle can be found easily, by applying the following simple greedy rule discovered by Williams: Start at an arbitrary vertex, and repeatedly flip the rightmost bit that creates a previously unvisited vertex. The resulting cycle is known as *binary reflected Gray code*, named after Bell Labs researcher Frank Gray, and it is shown in Figure 3 for .

## 2. The Middle Levels Conjecture

The * level th* of is the set of all vertices with exactly many 1s. In terms of subsets in the Boolean lattice, these are the subsets of size exactly Now consider the hypercube of odd dimension . and the subgraph induced by the middle two levels , and see Figure ;4. We denote this subgraph by and we note that it is vertex-transitive. Havel ,Hav83 in 1983, and independently Buck and Wiedemann BW84 in 1984 conjectured that has a Hamilton cycle for all and this problem became known as ,*middle levels conjecture*. It turns out that this problem is considerably harder than finding a Hamilton cycle in the entire cube. Thus, the conjecture is a prime example of an easy-to-state combinatorial proposition that one feels should be easy to prove at first sight, but that turns out to be surprisingly intricate upon further investigation. Also, it is an explicit instance of Lovász’ conjecture, and failing to prove it for this particular family of graphs shows how little we understand about the general problem. Consequently, the middle levels conjecture has attracted a lot of attention in the literature (see e.g., KT88FT95SW95, and it is mentioned in several popular books, in particular in Diaconis and Graham’s book *Magical Mathematics*, and in Winkler’s book *Mathematical Puzzles: A Connoisseur’s Collection*. Furthermore, Knuth gave the middle levels conjecture the highest difficulty rating (49/50) among all open problems in his book *The Art of Computer Programming*, Volume 4A. In a recent survey, Gowers comments on the conjecture as follows:

If one starts trying to build a Hamilton cycle in one runs into the problem of having too much choice and no obvious way of making it. (A natural thing to try to do is find some sort of inductive construction, but a lot of people have tried very hard to do this, with no success—a natural pattern just doesn’t seem to emerge after the first few small cases.) ,

### 2.1. Kierstead-Trotter matchings

A *matching* in a graph is a set of pairwise disjoint edges, and a matching is *perfect* if it includes every vertex. Kierstead and Trotter KT88 in 1988 suggested to tackle the middle levels conjecture by taking the union of two edge-disjoint perfect matchings in with the hope that their union forms the desired Hamilton cycle. ,

The two matchings they considered can be described explicitly as follows: We write and for the vertices in levels and of respectively, i.e., these are the two partition classes of , A .*Dyck word* is a bitstring with the same number of 1s and 0s and the property that every prefix contains at least as many 1s as 0s. We write for the set of all Dyck words of length Furthermore, for any string . and any integer we write , for the cyclic left shift of by steps. Note that every vertex can be written uniquely as for some and Indeed, the counting works out correctly, as the number of Dyck words is the Catalan number . the number of cyclic shifts is , and , We then define . Furthermore, we decompose . uniquely as for and we define , It is easy to show that . and are bijections between and and therefore , and are two edge-disjoint perfect matchings between the two partition classes and of The union of . and thus forms a *cycle factor* in the graph i.e., a collection of disjoint cycles that together visit all vertices. In fact, for , we are lucky and is a single cycle, i.e., a Hamilton cycle in see Figure ;4. Unfortunately, our luck ends for larger values of as the number of cycles of , for is .

### 2.2. Interpretation of the cycles as plane trees

The middle levels conjecture was finally solved by Mütze Müt16 in 2016, who later provided a 2-page proof Müt23a. The short proof picks up on Kierstead and Trotter’s argument as follows: The counting sequence for the number of cycles of is OEIS sequence A002995, which counts plane trees with edges, hinting at a bijection between plane trees with edges and cycles in see Figure ;8.

Indeed, this bijection follows from the definition of and and it also uses the following well-known bijection between Dyck paths with , steps and ordered rooted trees with edges; see Figure 5: Given a Dyck word we consider the corresponding Dyck path, which has an , for every 1-bit and a -step for every 0-bit of -step We then squeeze this Dyck path together, gluing every pair of an . and -step on the same height that ‘see’ each other (i.e., that have no other step at the same height in between them) together to form an edge of the ordered rooted tree. -step

For a vertex we consider the vertex , that is two steps away along a cycle of i.e., , is obtained by traversing one edge of and one edge of so , Specifically, for . with and we have We now define . and and we consider the ordered rooted trees corresponding to the Dyck words , and which differ in a tree rotation. Consequently, walking two steps along a cycle of , corresponds to a tree rotation and a cyclic left shift of the bitstring. As (the number of shifts) and (the number of tree edges) are coprime, all cyclic shifts of every tree lie on the same cycle. As the equivalence classes of ordered rooted trees under tree rotation are precisely plane trees, obtained by ‘forgetting’ the root, we obtain the desired bijection. Now that we have a nice combinatorial interpretation of the cycles in the factor all that is left to do is to join the cycles to a single Hamilton cycle. ,

### 2.3. Gluing cycles

The proof proceeds by gluing the cycles of the factor together via small gluing cycles. Given a cycle factor in a graph, a *gluing cycle* for a set of cycles from the factor has every second edge in common with one of the cycles in such a way that the symmetric difference of the edge sets of , is a single cycle on the same vertex set as In the simplest case . the cycle is a 4-cycle that joins two cycles as in Figure 7 (a). Unfortunately, the middle levels graph has no 4-cycles at all. However, we can use a 6-cycle that intersects as shown in Figure 7 (b), and obtain the same effect.

As it turns out, there is a large collection of such gluing 6-cycles for the factor and all these gluing cycles are edge-disjoint, i.e., the gluing operations do not interfere with each other. Furthermore, each gluing cycle that joins cycles , and corresponds to a local modification of the plane trees associated with and which consists in removing a leaf from the plane tree, and reattaching it to a neighboring vertex. We can thus define an auxiliary graph , which has as nodes all plane trees with edges, corresponding to the cycles of the factor and which has edges between pairs of plane trees that differ in such a local modification, corresponding to gluing cycles; see Figure ,8. It remains to show that the auxiliary graph is connected, which is done by showing that every plane tree can be transformed into a star by a sequence of local modifications as described before.

We thus reduced the problem of proving that has a Hamilton cycle to proving that the auxiliary graph is connected, which is much easier, as nodes and edges of have a nice combinatorial interpretation. This two-step approach of building a Hamilton cycle (cycle factor+gluing) and the corresponding reduction to a spanning tree problem is very powerful, and has been employed also in several of the proofs discussed later.

## 3. Bipartite Kneser Graphs

For integers and the ,*bipartite Kneser graph * has as vertices all and -element subsets of -element and an edge between any two subsets , and with The bipartite Kneser graph . is the cover graph of the subposet of the Boolean lattice of induced by the levels and In particular, . is the middle levels graph, i.e., bipartite Kneser graphs generalize the middle levels graphs. Furthermore, bipartite Kneser graphs are vertex-transitive, which makes them interesting test cases for Lovász’ conjecture. Simpson Sim91 and independently Roth conjectured in 1991 that all bipartite Kneser graphs admit a Hamilton cycle. Note that the degrees of are large when is large w.r.t. i.e., intuitively, the middle levels case , is the sparsest and hardest one, whereas the denser cases should be easier to prove. The densest graph is the cover graph of what poset theorists call the ‘standard example’, namely a complete bipartite graph minus a perfect matching. Indeed, there has been considerable work on establishing that sufficiently dense bipartite Kneser graphs have a Hamilton cycle. Once the sparsest case was established with the proof of the middle levels conjecture, the Hamiltonicity of all was shown shortly thereafter by Mütze and Su MS17 in 2017. In fact, their proof is a 5-page inductive argument, which uses the sparsest case as a basis.

### 3.1. Havel’s construction and its subsequent refinement

We write for the subgraph of the hypercube induced by levels and Already Havel .Hav83 in his 1983 paper considered the following strengthening of the middle levels conjecture: For any and there is a cycle , in that visits all vertices in level i.e., in the smaller of the two partition classes, shown in red in Figure ,9. For both partition classes have the same size and is a Hamilton cycle in i.e., this statement is the middle levels conjecture. For , Havel proved this statement by an easy induction: Indeed, we can split into two subgraphs and by partitioning all vertices according to the value of the last bit. Using induction, we can glue together the two cycles , and to obtain Note that this approach fails for . as in this case , lies above the middle and lies below the middle, so the size difference between lower and upper level is opposite in both parts.

**Figure 10.**

Hamilton cycles in (a1)–(a4) bipartite Kneser graphs for , and (b1)–(b4) Kneser graphs ; for , Vertices are in their bitstring representation .( and ).

(a1) | (a2) | (a3) | (a4) | (b1) | (b2) | (b3) | (b4) |

The method of Mütze and Su extends Havel’s idea as follows: In addition to the cycle in we maintain a set of vertex-disjoint paths , in shown in blue in Figure ,9, each of which starts at a vertex of in level and ends at a vertex in level and visits only one vertex of each level in between. The number of such paths equals the number of vertices in levels , or namely , i.e., these paths visit all vertices in level , but they do not visit all vertices in the levels below that. For , the paths have no edges, so this strengthening is again the middle levels conjecture. For the cycles and paths can be constructed following a very similar inductive approach as before, by partitioning vertices according to the last bit and gluing together two copies of the structures obtained by induction.

From the cycle and the paths we construct a Hamilton cycle in as follows: We replace each of the vertices of the cycle in level which is the starting vertex of some path from , by the other end vertex of this path in level , This gives a cyclic sequence in which all vertices in level . are interleaved with all vertices in level with the additional property that the predecessor and successor of any ,level- vertex are reachable from it by a path in that moves up from level to level As moving up along a path in . corresponds to moving to a superset, this sequence is indeed a Hamilton cycle in This cycle has the remarkable additional closeness property that any two consecutive . differ only in the exchange of a single element (as they have a common neighbor in level -sets This construction is illustrated in Figure ).10 (a1)–(a4) for the cases and ( is a solution to the middle levels conjecture).

## 4. Kneser Graphs

For integers and the ,*Kneser graph * has as vertices all subset of -element and edges between any two disjoint sets. Kneser graphs have many interesting properties, for example, their chromatic number was shown to be , by Lovász using topological methods, and their independence number is by the famous Erdős-Ko-Rado theorem. Kneser graphs are clearly vertex-transitive, and is the *bipartite double cover* of i.e., we take two copies of , and replace every corresponding pair of edges inside the copies by the two ‘diagonal’ cross edges between them. Consequently, if admits a Hamilton cycle, then admits a Hamilton path or cycle. Indeed, given a Hamilton cycle in where , we define , and we consider the two sequences ,

The sparsest Kneser graphs are obtained when *odd graphs *. The odd graph

### 4.1. The Chen-Füredi construction via Baranyai’s partition theorem

**Figure 11.**

(a) Exchange Gray code for 2-element subsets of [8] obtained by restricting the binary reflected Gray code in

(a) | (b) |

In 2002, Chen and Füredi CF02 found a particularly nice proof that *Baranyai’s partition theorem*, which states that the

To prove that

### 4.2. Settling the odd graphs via a Chung-Feller bijection

In 2021, Mütze, Nummenpalo, and Walczak MNW21 proved that the sparsest Kneser graphs, namely the odd graphs *Chung-Feller theorem*. A *flaw* in a bitstring

The proof of Mütze, Nummenpalo, and Walczak is completed by gluing the cycles of this factor together via 6-cycles and 8-cycles, which glue together 3 or 4 cycles, respectively, from the factor at a time. The main technical difficulty is that the corresponding auxiliary graph is now a hypergraph with hyperedges of cardinality 3 or 4, respectively; see the bottom right of Figure 13 (only 3-hyperedges are present in the figure). To obtain a Hamilton cycle in *loose* spanning tree in the auxiliary hypergraph, i.e., a spanning tree in which any two hyperedges overlap at most in a singleton. For this it is not enough to prove that the hypergraph is connected, as there are connected hypergraphs that do not admit any loose spanning tree. Instead the paper constructs one particular loose spanning tree. The resulting Hamilton cycle in

### 4.3. Johnson’s inductive construction

In 2011, Johnson Joh11 devised an inductive construction for Hamilton cycles in Kneser graphs. Specifically, he showed that

His construction works for a ground set of even cardinality

Combining Johnson’s result with the solution for the sparsest case

### 4.4. Settling the remaining cases via Greene-Kleitman parenthesis matching and gliders

In 2022, Merino, Mütze, and Namrata MMN22 proved that *parenthesis matching*, a technique that was pioneered by Greene and Kleitman GK76 in the context of symmetric chain partitions of the Boolean lattice: We consider vertices of *cyclically* across the boundary of

The next step is to understand the structure of the cycles generated by *glider*. A glider has a *speed* associated to it, which is given by the number of 1s in its group. For example, in the cycle shown in Figure 14 (a), there is a single matched 1 and the corresponding matched 0, and together these two bits form a glider of speed 1 that moves one step to the right in every time step. Applying

where