The question whether a graph has a Hamilton cycle is one of the oldest and most fundamental graph-theoretic problems, and one of the prototypical NP-complete problems. In this paper we survey some of our recent results on Hamilton cycles in various families of highly symmetric graphs, including the solution of the well-known middle levels conjecture, and several far-ranging generalizations of it that were proved subsequently. We also address the algorithmic aspect of the problem, i.e., how to compute the corresponding Gray codes in optimal time and space.
The question whether a graph has a Hamilton cycle-a cycle that visits every vertex exactly once-is one of the oldest and most fundamental problems on graphs. Answering this question for a given graph is one of the prototypical NP-complete problems, as shown by Karp in his landmark paper [Kar72]. This problem has a large number of practical applications, after all, it a special case of the traveling salesman problem. Hamilton cycles are named after the Irish mathematician Sir William Rowan Hamilton, who invented the 'Icosian game', a puzzle that consists in finding a Hamilton cycle in the graph of the dodecahedron; see Figure 1. In this paper we survey some of our recent solutions to several long-standing problems that can be seen as advanced versions of this puzzle. We prove the existence of such cycles, and we develop algorithms that allow us to compute them efficiently.
The most advanced version of Hamilton's original puzzle is the following conjecture due to Lovász from the 1970s. A vertex-transitive graph is a graph that 'looks the same' from the point of view of every vertex. Formally, it is a graph in which any two vertices can be mapped onto each other by an automorphism.
The five well-understood counterexamples mentioned in this conjecture are a single edge, the Petersen graph, the Coxeter graph, and the two graphs obtained from the Petersen graph and Coxeter graph by replacing every vertex by a triangle. Even though these five graphs do not have a Hamilton cycle, they have a Hamilton path, so an alternative version of the conjecture asserts that every connected vertex-transitive graph has a Hamilton path. In stark contrast to that, Babai conjectured that there is an ε > 0 and infinitely many connected vertex-transitive graphs G whose longest cycle has length at most (1 − ε)|V (G)| [Bab95], where V (G) denotes the vertex set of G.
These conjectures tie together two seemingly unrelated concepts of a graph, namely its symmetry and its traversability, and they have received considerable attention in the literature. For example, it was shown that For more partial results towards Lovász' conjecture, we refer to the surveys [KM09, PR09].
Humans have long enjoyed making lists of things. This task also appears frequently in algorithmic applications, when we want to examine all objects of a particular combinatorial class, for instance to compute and optimize some objective value. Algorithms that efficiently generate all objects in a combinatorial class such as permutations, subsets, combinations, partitions, trees, strings etc. are used as core building blocks in a wide range of practical applications (the survey [Sav97] lists numerous references). If any two consecutively generated objects differ only in a constant amount, then we refer to such a listing as a combinatorial Gray code. The ultimate goal for all these problems is a combinatorial Gray code that allows to generate each new object in constant time (see [Ehr73]).
Here are five important examples for such generation problems: Many of the algorithms solving those Gray code problems are covered in the classical books [NW75,Wil89]. Also, more than half of the most recent volume of Knuth's seminal series The Art of Computer Programming is devoted to this fundamental subject [Knu11].
We can model each of the Gray code problems mentioned before as a graph, whose vertices are the combinatorial objects we want to generate, and whose edges capture the change operation applied in each step. For instance, for problem (i) from before, we take all 2 n bitstrings of length n as vertices, and we connect any two bitstrings that differ in a single bit by an edge. The resulting graph is the well-known n-dimensional hypercube, or n-cube for short. In this way, every combinatorial Gray code problem corresponds in a natural way to a Hamilton cycle problem in a suitably defined graph. In many cases the resulting graphs are vertex-transitive, and this is the connection to Lovász' conjecture mentioned in the previous section. The n-cube arising from problem (i) is a prime example of a vertex-transitive graph. Similarly, the graphs arising from problems (ii) and (iii) are also vertex-transitive.
One prominent special case of Lovász' conjecture is the middle levels conjecture, which asserts that the subgraph G n of the (2n + 1)-cube induced by all bitstrings with weight n or n + 1, has a Hamilton cycle for every n ≥ 1. Equivalently, G n is the subgraph of the Boolean lattice of subsets of [2n + 1] ordered by inclusion formed by all sets of size n or n + 1. The middle levels conjecture also became known as revolving door conjecture. Imagine a set of 2n + 1 people, split into two subsets of size n and n + 1 that are separated by a revolving door. The conjecture asks whether it is possible to move in each step one person from the larger group through the revolving door to the other side, such that every way to split the people into two subsets of size n and n + 1 is encountered exactly once. Another equivalent formulation of the conjecture can be found in Knuth's book [Knu11]: It asks whether we can generate all bitstrings of length 2n + 2 with weight n + 1, by repeatedly swapping the last bit with another bit at an arbitrary position.
It is easy to see that G n is bipartite and connected, and that it has N := 2n+1 n + 2n+1 n+1 = 2 Θ(n) many vertices. Moreover, all vertices have degree n + 1 = Θ(log(N )), i.e., this graph is rather sparse. The graph G n is also vertex-transitive, and the autormorphisms are given by bit permutation and possibly bit inversion.
The middle levels conjecture originated probably with Havel [Hav83] and Buck and Wiedemann [BW84], but has also been attributed to Dejter, Erdős, Trotter [KT88] and various others. It also appears in the popular books [Win04,Knu11,DG12] and in Gowers' recent expository paper [Gow17] on the work of Peter Keevash. The conjecture has attracted considerable attention over the last 30+ years. In a sequence of algorithmic improvements and with the availability of more powerful computers, so far the conjecture has been verified for all n ≤ 19 [SS99, SSS09, SA11]. Note that for n = 19 the middle levels graph G n has already N = 137.846.528.820 vertices.
The first notable asymptotic result is [Sav93], where it was shown that G n has a cycle of length N 0.836 . Improving on this, Felsner and Trotter showed that there is a cycle that visits 0.25N many vertices of the middle levels graph [FT95], and Savage and Winkler showed that there is a cycle that visits 0.839N many vertices [SW95]. Another major step towards the conjecture was Johnson's result [Joh04], who established the existence of a cycle of length (1 − c/ √ n)N , where c is some constant. Unfortunately, attempts to directly obtain a Hamilton cycle from the union of two perfect matchings in the middle levels graph have not been successful so far [DSW88, KT88, DKS94], even though these constructions of perfect matchings deepened our understanding of the structure of the middle levels graph. For other relaxations of the middle levels conjecture and partial results, see e.g. [HKRR05,GŠ10].
We prove the middle levels conjecture in full generality.
In fact, we prove the following more general result.
). For any n ≥ 1, the middle levels graph G n has at least 1 4 2 2 (n+1)/4 = 2 2 Ω(n) distinct Hamilton cycles.
Note that double-exponentially many distinct Hamilton cycles are substantially more than we get from applying all 2(2n + 1)! = 2 Θ(n log n) automorphisms of the middle levels graph to a single Hamilton cycle, i.e., Theorem 3.2 is not an immediate consequence of Theorem 3.1. In fact, any graph G has at most |V (G)|! different Hamilton cycles. This establishes an upper bound of N ! = 2 2 O(n) for the number of Hamilton cycles in the middle levels graph and shows that Theorem 3.2 is best possible up to the constant in the exponent.
The proof of these results follows a two-step approach. In a first step we construct a cycle factor in G n as described in our earlier paper [MW12]. A cycle factor is a collection of vertex-disjoint cycles that together cover all vertices of the graph. In a second step, we modify the cycles locally to join them step by step to a Hamilton cycle. This two-step approach of building a Hamilton cycle via a cycle factor has proved to be very successful for such Hamilton cycle problems (see e.g. [Joh09, Joh11, HRW12, Hol17, SW18]). The main advantage of this approach is that it reduces the problem of proving that a graph has a Hamilton cycle to the problem of proving that a suitably defined auxiliary graph is connected, which is much easier. We recently found a new, short and more accessible proof of Theorems 3.1 and 3.2, following the same basic proof strategy [GMN18].
We are able to translate our existence proof of a Hamilton cycle in the middle levels graph G n into an efficient Gray code algorithm.
). There is an algorithm, which for a given bitstring of length 2n + 1, n ≥ 1, with weight n or n + 1 computes the next ≥ 1 bitstrings in a Hamilton cycle in G n in time O( + n).
Clearly, the running time of this algorithm is O(1) on average per generated bitstring for = Ω(n). The space requirement O(n) of our algorithm is also optimal. Most steps of our algorithm require only constant time O(1) in the worst case to generate the next bitstring, but after every sequence of Θ(n) such 'fast' steps, a 'slow' step which requires time Θ(n) is encountered, yielding constant average time performance.
We implemented this algorithm in C++, and this code can be found on our website [www]. As a benchmark, we used this code to compute a Hamilton cycle in G n for n = 19 in 20 minutes on a standard desktop computer. This is by a factor of 72 faster than the 24 hours reported in [MN18] for our previous O(n) time algorithm, and by several orders of magnitude faster than the 164 days reported in [SA11] for a brute-force search. Recall that a Hamilton cycle in G n for n = 19 visits N = 137.846.528.820 ≈ 10 11 many bitstrings. For comparison, a program that simply counts from 1, . . . , N (and does nothing else) was only by a factor of 5 faster (4 minutes) than our middle levels Hamilton cycle computation for n = 19 on the same hardware. Roughly speaking, we need only about 5 machine instructions for producing the next vertex in the Hamilton cycle.
Consider the following sweeping generalization of the middle levels conjecture, which at the same time generalizes problems (i) and (ii) mentioned in Section 2: Can we generate all bitstrings of length n, with weight in an arbitrary interval [k, l], where 0 ≤ k ≤ l ≤ n, by flipping a single bit in each step [Ehr73,SW14]? This problem has three parameters, the length n of the bitstrings, the lower bound k and the upper bound l on the weight. In general the answer to this question is negative, as the bipartite graph underlying this problem, i.e., the subgraph of the n-cube induced by all bitstrings with weight in the interval [k, l], has partition classes of different sizes, and thus cannot have a Hamilton cycle. However, by slightly relaxing the requirement of flipping a single bit in each step, the problem can still be solved satisfactorily for all practical purposes. Specifically, a tight enumeration of all bitstrings of length n with weight in the interval [k, l] is a cyclic listing such that each bitstrings appears exactly once, and such that the number of transitions in which two bits are flipped is exactly equal to the size difference of the partition classes of the underlying graph, and in the remaining transitions, only a single bit is flipped. A tight enumeration is thus a natural generalization of a Hamilton cycle, and it is equal to a Hamilton cycle when the partition classes have the same size (as for instance for the middle levels graph G n ).
). For any n ≥ 3 there is a tight enumeration of all bitstrings of length n with weight in the interval [k, l] in the following cases:
A different relaxation of asking for a Hamilton cycle in a bipartite graph whose partition classes have possibly different size, is to ask for a cycle that visits all vertices in the smaller partition class. Our paper [GM18] also presents results that are very much analogous to Theorem 4.2 for this alternative relaxation of a Hamilton cycle. We implemented all those Gray code algorithms in C++, and made the code available on our website [www].
Essentially the only case of the aforementioned general problem that we cannot solve in full generality yet is when the dimension is odd and the lower and upper weight bound are symmetric around the middle. Formally, for any n ≥ 1 and 1 ≤ ≤ n + 1 we let G n, denote the corresponding subgraph of the (2n + 1)-cube induced by all bitstrings with weight in the interval [n + 1 − , n + ], so this graph contains exactly the middle 2 levels. The two partition classes of G n, have the same size, so we may hope for the existence of a Hamilton cycle. Note, however, that G n, is not vertex-transitive in general, as the vertices with weight n + 1 − or n + at the boundaries have a smaller degree than all other vertices. The central levels problems asks whether G n, has a Hamilton cycle for any n ≥ 1 and 1 ≤ ≤ n + 1. This is clearly a generalization of the middle levels conjecture (the case = 1) and of the Gray code problem (i) mentioned in Section 2 (the case = n + 1). The central levels problem was raised independently by Savage [Sav93], by Gregor and Škrekovski [GŠ10], and by Shen and Williams [SW15]. Apart from the known cases = 1 and = n + 1, the cases = n and = n − 1 were settled in [HH01,LS03] and [GŠ10], respectively. We recently managed to also settle the case = 2, i.e., we prove the Hamiltonicity of the middle four levels of the (2n + 1)-cube. For the general case, we can prove the existence of a cycle factor in G n, .
). For any n ≥ 1, the graph G n,2 has a Hamilton cycle. For any n ≥ 1 and 3 ≤ ≤ n − 2, the graph G n, has a cycle factor.
Our proof of Theorem 4.3 uses symmetric chain decompositions, a well-known concept from the theory of posets. A chain in the n-cube is a path (x k , x k+1 , . . . , x l ) where x i has weight i for all i = k, k + 1, . . . , l. The chain is symmetric if its end vertices are on symmetric levels, i.e., n = k + l. A symmetric chain decomposition of the n-cube is a partition of its vertices into symmetric chains. In our paper [GJMSW18] we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-cube for any n ≥ 12, and then combine certain edges from these decompositions to build cycle factors and eventually Hamilton cycles.
For any two integers k ≥ 1 and n ≥ 2k + 1, the bipartite Kneser graph H(n, k) has the k-element and (n − k)element subsets of [n] as vertices and an edge between any two vertices where one is a subset of the other. Observe that H(n, k) is connected and vertex-transitive, which makes it another excellent test case for Lovász' conjecture. Note that the special case H(2k + 1, k) is exactly the middle levels graph G k discussed in Section 3, so bipartite Kneser graphs generalize the middle levels graphs in a natural way.
The conjecture that all bipartite Kneser graphs have a Hamilton cycle was raised independently by Simpson [Sim91] and Roth (see [Gou91] and [Hur94]). Since then, there has been steady progress on the problem [Sim94, Hur94, Che00], and the conjecture has been confirmed with computer help for all n ≤ 27 and all relevant values of k [SS04]. The best known general result is due to Y. Chen, who showed that for any k ≥ 1 and n ≥ 2.62k + 1, the bipartite Kneser graph H(n, k) has a Hamilton cycle [Che03].
Note that the degree of every vertex in H(n, k) is n−k n−2k , so for fixed k, increasing n also increases the vertex degrees, which makes the task of finding a Hamilton cycle easier. The sparsest case, for which finding a Hamilton cycle is hardest, is the case n = 2k + 1, i.e., the middle levels conjecture.
We resolve the conjecture on the Hamiltonicity of bipartite Kneser graphs in full generality.
). For any k ≥ 1 and n ≥ 2k + 1, the bipartite Kneser graph H(n, k) has a Hamilton cycle.
The main feature of this result is that it has a short proof, using the positive result for the sparsest case n = 2k+1 stated in Theorem 3.1, and proving the denser cases by induction, where the sparsest case serves as an induction basis.
For any two integers k ≥ 1 and n ≥ 2k+1, the Kneser graph K(n, k) has the k-element subsets of [n] as vertices and an edge between any two vertices that are disjoint sets. These graphs were introduced by Lovász in his celebrated proof of Kneser's conjecture [Lov78]. The proof uses topological methods to show that the chromatic number of K(n, k) is equal to n − 2k + 2. Lovász's result initiated an exciting line of research [Bár78,Gre02,Zie02,Mat04] and gave rise to the nowadays flourishing field of topological combinatorics. Apart from the above, Kneser graphs have many other interesting properties. For instance, the maximum size of an independent set in K(n, k) is equal to n−1 k−1 , by the famous Erdős-Ko-Rado theorem [EKR61].
It has long been conjectured that Kneser graphs have Hamilton cycles. Apart from one obvious exception, namely the Petersen graph K(5, 2), no other negative instances are apparent. Observe that Kneser graphs are connected and vertex-transitive, and thus form another important instance of Lovász' conjecture. We proceed by giving an account of the long history of finding Hamilton cycles in Kneser graphs. The degree of every vertex in K(n, k) is n−k k , so for fixed k, increasing n also increases the vertex degrees, which makes the task of finding a Hamilton cycle easier. The density is also witnessed by cliques of size c ≥ 3, which are present for n ≥ ck and absent for n < ck. The sparsest case, for which finding a Hamilton cycle is hardest, is when n = 2k + 1. The corresponding graphs O k := K(2k + 1, k), for k ≥ 1, are known as odd graphs. They include the Petersen graph O 2 = K(5, 2). Note that all vertices in the odd graph O k have degree k + 1, which is only logarithmic in the number of vertices. The conjecture that the odd graph O k has a Hamilton cycle for every k ≥ 3, originated in the 1970s, in papers by Meredith and Lloyd [ML72,ML73] and by Biggs [Big79]. A stronger version of the conjecture asserts that O k even has (k + 1)/2 edge-disjoint Hamilton cycles. Already Balaban [Bal72] exhibited a Hamilton cycle for the cases k = 3 and k = 4, and Meredith and Lloyd described one for k = 5 and k = 6. Later, Mather [Mat76] also solved the case k = 7. With the help of computers, Shields and Savage [SS04] found Hamilton cycles in O k for all values of k up to 13. They also found Hamilton cycles in K(n, k) for all n ≤ 27 and all k ≥ 1 with n ≥ 2k + 1.
There is a long line of research devoted to proving that sufficiently dense Kneser graphs have a Hamilton cycle. Heinrich and Wallis [HW78] showed that K(n, k) has a Hamilton cycle if 1))k 2 / ln 2. This was improved by B. Chen and Lih [CL87], whose results imply that K(n, k) has a Hamilton cycle if n ≥ (1 + o(1))k 2 / log k, see [CI96]. In another breakthrough, Y. Chen [Che00] showed that K(n, k) is Hamiltonian when n ≥ 3k. A particularly nice and clean proof for the cases where n = ck, c ∈ {3, 4, . . .}, was obtained by Y. Chen and Füredi [CF02]. Their proof uses Baranyai's well-known partition theorem for complete hypergraphs [Bar75] to partition the vertices of K(ck, k) into cliques of size c. The asymptotically best result currently known, again due to Y. Chen [Che03], is that
Another line of attack towards proving Hamiltonicity is to find long cycles in K(n, k). To this end, Johnson [Joh04] showed that there exists a constant c > 0 such that the odd graph O k has a cycle that visits at least a (1 − c/ √ k)-fraction of all vertices, which is almost all vertices as k tends to infinity. Our proof techniques developed for the bipartite Kneser graphs discussed in the previous section allow us to generalize and improve upon this, by showing that for any k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) has a cycle that visits a 2k n -fraction of all vertices [MS17]. In particular, for any k ≥ 1, the odd graph O k = K(2k + 1, k) has a cycle that visits a (1 − 1 2k+1 )-fraction of all vertices. For instance, the Petersen graph O 2 has a cycle that visits 8 of its 10 vertices. A different relaxation of proving Hamiltonicity is to construct a cycle factor. In this direction, Johnson and Kierstead [JK04] showed that the edges of O k can be partitioned into cycle factors for odd k and into cycle factors and one matching for even k. A different cycle factor in O k , which turns out to be crucial for the following results, is constructed in our paper [MSW18]. This cycle factor has the property that all of its cycles have the same length 2k + 1, so the total number of cycles is given by the kth Catalan number 1 2k+1 2k+1 k . As a last partial result, let us mention the paper by Bueno and Horák [BH11], who proved that the prism over O k , i.e., the graph obtained from two copies of O k by joining corresponding vertices by a perfect matching, is Hamiltonian for even k.
Note that proving Hamiltonicity for the Kneser graph K(n, k) is arguably harder than for the bipartite Kneser graph H(n, k). In particular, proving that the odd graphs O k = K(2k + 1, k) are Hamiltonian is harder than the middle levels conjecture. Specifically, from a Hamilton cycle (x 1 , . . . , x N ) in K(n, k), where N = n k , we can easily construct a Hamilton cycle or a Hamilton path in H(n, k), as follows. Consider the sequences C 1 := (x 1 , x 2 , x 3 , x 4 , . . .) and C 2 := (x 1 , x 2 , x 3 , x 4 , . . .), where x i := [n] \ x i . If N is odd, then C 1 and C 2 together form a Hamilton cycle in H(n, k). If N is even, then C 1 and C 2 are two cycles in H(n, k) that can be joined to form a Hamilton path.
We prove that the odd graphs O k = K(2k + 1, k) (except for the Petersen graph) contain Hamilton cycles. That is, we resolve the sparsest case of the conjecture on the Hamiltonicity of Kneser graphs in the affirmative. Using the conditional results proved by Johnson [Joh11], Theorem 6.1 immediately yields the following more general statement.
). For any k ≥ 3 and a ≥ 0, the Kneser graph K(2k + 2 a , k) has a Hamilton cycle.
We also establish the following counting version of Theorem 6.1.
). For any k ≥ 6, the odd graph O k = K(2k + 1, k) has at least 2 2 k−6 distinct Hamilton cycles.
Similarly to our solution of the middle levels conjecture stated in Theorems 3.1 and 3.2, the double-exponential growth of the number of Hamilton cycles guaranteed by Theorem 6.3 is essentially best possible, and Theorem 6.3 is not an immediate consequence of Theorem 6.1.
Our proofs of Theorems 6.1 and 6.3 use a similar two-step approach as the proof of the middle levels conjecture, using the cycle factor described in our earlier paper [MSW18] as a starting point, thus effectively reducing the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words. The proofs are constructive and translate straightforwardly into an algorithm to compute a Hamilton cycle in the odd graph O k in polynomial time (polynomial in the size of the graph, which is exponential in k). By identifying each k-element subset of [2k + 1] with a bitstring of length 2k + 1 and weight k, a Hamilton cycle in the odd graph corresponds to a Gray code listing of all bitstrings of length 2k + 1 with weight k, such that consecutive bitstrings differ in all but one position. It remains open whether our proof can be translated into a constant-time algorithm to generate this Gray code, that is, an algorithm that in each step computes the bit that is not flipped in constant time, using only O(k) memory space and polynomial initialization time. To avoid costly complementation operations, such an algorithm could maintain two bitstrings, one the complement of the other, along with a flag indicating which of the two bitstrings is the current one; then, in each step, only a single bit in both bitstrings and the flag would need to be flipped.