PDFLINK

# On Hamilton Cycles in Graphs Defined by Intersecting Set Systems

Torsten Mütze

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 -dimensional hypercube. It is convenient to encode the vertices of  as bitstrings of length , by considering the characteristic vector of each set, which has the th bit equal to 1 if and only if the element  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 th level 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 -step for every 1-bit and a -step for every 0-bit of . We then squeeze this Dyck path together, gluing every pair of an -step 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.

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 -element and -element subsets of , 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.

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 -sets differ only in the exchange of a single element (as they have a common neighbor in level ). 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 -element subset of , 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  and , both of length , obtained by complementing every even- or odd-indexed set in , respectively. The last entries of  and  are and , respectively, if is odd, and vice versa if is even. Furthermore, as we have and , so and  are paths in . Furthermore, if is odd, then their concatenation  is a Hamilton cycle in . On the other hand, if is even, then the two end vertices of  are adjacent and the two end vertices of  are adjacent, so these two disjoint cycles in  can be joined to a Hamilton path.

The sparsest Kneser graphs are obtained when , and they are also known as odd graphs . The odd graph  is the Petersen graph shown in Figure 2, which does not have a Hamilton cycle, but only a Hamilton path. The graph  is shown in Figure 13. The conjecture that  for has a Hamilton cycle was raised in the 1970s, even before the middle levels conjecture, in papers by Meredith and Lloyd ML73, and by Biggs Big79. By our earlier observation, the Hamiltonicity of  implies it for . In particular, Hamiltonicity of the odd graphs implies the middle levels conjecture. Consequently, Kneser graphs attracted a lot of attention, and there was a long line of research on proving that sufficiently dense Kneser graphs , i.e., those where is large w.r.t. , admit a Hamilton cycle.

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

In 2002, Chen and Füredi CF02 found a particularly nice proof that  has a Hamilton cycle when for some integer . The first ingredient of their proof is Baranyai’s partition theorem, which states that the vertices of the Kneser graph can be partitioned into groups of size  such that the vertices in each group are a partition of , i.e., they are pairwise disjoint and together cover . The second ingredient is a method to list all -element subset of  in such a way that any two consecutive sets  differ in an element exchange, i.e., for some . It is well known that such a listing can be obtained from the binary reflected Gray code for  by restricting it to the vertices in level , i.e., we simply delete from the full listing all vertices not in level ; see Figure 11 (a).

To prove that with and has a Hamilton cycle, Chen and Füredi first apply Baranyai’s theorem, which partitions all vertices of  into groups of size , such that each group is a partition of . Let be the sets in the th group, for every . Each of those groups forms a clique in the Kneser graph, i.e., it can be traversed in any order. Without loss of generality we may assume that , i.e., the element is contained in the last set of each group. Furthermore, by the aforementioned Gray code result, we can assume that are ordered so that any two consecutive sets differ in an element exchange, i.e., forms an exchange Gray code for all -element subsets of . Let be the element in  that is not contained in  (the indices  are considered modulo ). We may also assume that does not contain , otherwise the sets can be reordered appropriately, which is possible as there are at least of them. It follows that and consequently, is the desired Hamilton cycle in ; see Figure 11 (b). The method via Baranyai partitions was later refined by Chen Che00 to establish Hamiltonicity of all  with .

### 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  for all  have a Hamilton cycle. The starting point of their proof is the well-known Chung-Feller theorem. A flaw in a bitstring  is a prefix of  ending with 0 that has strictly less 1s than 0s; flaws are drawn as red steps in Figure 12. We write for the unique middle level  of , i.e., all bitstrings of length  with exactly many 1s, and we partition  into sets  for according to the number  of flaws. In particular, are Dyck words, and are complemented Dyck words. The Chung-Feller theorem asserts that , i.e., the number of strings is the same independently of the number of flaws, and it is the th Catalan number. It is not hard to prove this by establishing a bijection . In 2018, Mütze, Standke and Wiechert presented a new proof, using a bijection  that has the following additional properties; see Figure 12: only transposes two bits (0 and 1), for any we have that is the complement of , i.e., every bit is transposed (and thus complemented) exactly once when applying the bijection times, and the unique neighbors of  and  in level  of  for are all distinct and together cover precisely this level. We can thus build vertex-disjoint paths , all of length , that together cover  and that connect pairs of Dyck words and their complements (the length of each path is the number of its edges, which is one less than the number of vertices). Appending a 0-bit to all vertices and taking complements of the resulting vertices in level  yields a cycle factor in  which has many cycles of the same length ; see Figure 13.

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 , we seek a so-called 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  is shown in Figure 10 (b4).

### 4.3. Johnson’s inductive construction

In 2011, Johnson Joh11 devised an inductive construction for Hamilton cycles in Kneser graphs. Specifically, he showed that for with even  has a Hamilton cycle provided that the smaller Kneser graphs have a Hamilton cycle for all (or they are the Petersen graph ).

His construction works for a ground set of even cardinality  by partitioning it into fixed pairs  for , and by considering the possible intersection patterns of subsets with those pairs. Specifically, we associate a set with a tuple  by defining , or  if equals , or , respectively. In the simplest case, the subsets  intersect the pairs in either 0 or 2 elements, i.e., for all . In this case, for a Hamilton cycle in  can be lifted to a cycle in  by replacing every element  by the pair . More generally, consider subsets  which intersect all but a fixed set of pairs in 0 or 2 elements, i.e., for a fixed -set of indices . An edge in together with a -set in  lifts to a set of edges involving subsets which intersect all but this fixed set of pairs in 0 or 2 elements. For example, we have many edges (one for each pattern of s) of the form in  that arise from the edge in with as the special -set. Using this idea, a Hamilton cycle in lifts to a cycle (possibly of double the length) consisting of sets of this type in . With some care, one can join together these cycles corresponding to different -sets, and then for different values of  to give a Hamilton cycle in .

Combining Johnson’s result with the solution for the sparsest case presented in the previous section, we obtain that has a Hamilton cycle for all and . This settles in particular the second-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 for has a Hamilton cycle, which combined with the results from the previous two sections completely settles the problem for Kneser graphs. Their proof starts with a new cycle factor in , which is constructed using the following simple rule based on 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  as bitstrings, and we interpret the 1s in  as opening brackets and the 0s as closing brackets, and we match closest pairs of opening and closing brackets in the natural way, which will leave some 0s unmatched. This matching is done cyclically across the boundary of , i.e., is considered as a cyclic string. We write for the vertex obtained from  by complementing all matched bits, leaving the unmatched bits unchanged. Note that and  have no 1s at the same positions, implying that is an edge in the Kneser graph. Furthermore, is invertible and and , so the union of all edges  is a collection of disjoint cycles that together visit all vertices of ; see Figure 14.

The next step is to understand the structure of the cycles generated by . Interestingly, the evolution of a bitstring  under repeated applications of  can be described by a kinetic system of multiple gliders that move at different speeds and that interact over time, somewhat reminiscent of the gliders in Conway’s Game of Life. Specifically, each application of  is viewed as one unit of time moving forward. Furthermore, we partition the matched bits of  into groups, and each of these groups is called a 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 means going down to the next row in the picture, so the time axis points downward. Similarly, in Figure 14 (b), there are two matched 1s and the corresponding two matched 0s, and together these four bits form a glider of speed 2 that moves two steps to the right in every time step. As we see from these examples, a single glider of speed  simply moves uniformly, following the basic physics law

where is the time (i.e., the number of applications of ) and is the position of the glider in the bitstring as a function of time. The position  has to be considered modulo , as bitstrings are considered as cyclic strings and the gliders hence wrap around the boundary. The situation gets more interesting and complicated when gliders of different speeds interact with each other. For example, in Figure 14 (c), there is one glider of speed 2 and one glider of speed 1. As long as these groups of bits are separated, each glider moves uniformly as before. However, when the speed 2 glider catches up with the speed 1 glider, an overtaking occurs. During an overtaking, the faster glider receives a boost, whereas the slower glider is delayed. This can be captured by augmenting the corresponding equations of motion by introducing additional terms, making them nonuniform. In the simplest case of two gliders of different speeds, the equations become