=Paper=
{{Paper
|id=Vol-2113/invited3
|storemode=property
|title=On Hamilton cycles in highly symmetric graphs
|pdfUrl=https://ceur-ws.org/Vol-2113/invited3.pdf
|volume=Vol-2113
|authors=Torsten Mütze
|dblpUrl=https://dblp.org/rec/conf/gascom/Mutze18
}}
==On Hamilton cycles in highly symmetric graphs==
https://ceur-ws.org/Vol-2113/invited3.pdf
On Hamilton cycles in highly symmetric graphs
Torsten Mütze
Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany
muetze@math.tu-berlin.de
Abstract
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.
1 Introduction
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.
Conjecture 1.1 ( [Lov70]). Every connected vertex-transitive graph has a Hamilton cycle, apart from five
counterexamples.
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
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
12
Figure 1: The dodecahedron (solid black) with a Hamilton cycle (dashed red).
connected vertex-transitive graphs on n vertices, with n = kp, where k ≤ 4 and p prime (except for the Petersen
graph and the Coxeter graph), with n = pk where k ≤ 4 and p prime, and with n = 2p2 , where p is prime, contain
a Hamilton cycle [Tur67, Als79, Mar85, Mar87, Che98, KM08].
√ Babai showed that every connected vertex-transitive
graph on n ≥ 4 vertices has a cycle of length at least 3n [Bab79]. Also, it was shown in [CHM14] that for
any ε > 0, for large enough n any connected vertex-transitive graph on n vertices and minimum degree εn has a
Hamilton cycle.
For more partial results towards Lovász’ conjecture, we refer to the surveys [KM09, PR09].
2 Combinatorial Gray codes
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:
(i) Generate all bitstrings of length n by flipping a single bit in each step [Gra53, Ehr73, BER76].
(ii) Generate all bitstrings of length n with weight k by exchanging a 0 and 1 in each step [TL73, EHR84a,
EM84b, Rus88, Cha89, JM95]. The weight of a bitstring is the number of 1s in it.
(iii) Generate all permutations of [n] := {1, 2, . . . , n} by swapping two adjacent elements in each step [Joh63,
Tro62, Der75, Sed77].
(iv) Generate all spanning trees of a graph by exchanging a single edge in each step [Cum66, HH72].
(v) Generate all triangulations of a convex n-gon by flipping a single edge in each step [Luc87, LRR93, HN99].
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 2n 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.
13
3 The middle levels conjecture
One prominent special case of Lovász’ conjecture is the middle levels conjecture, which asserts that the subgraph Gn
of the (2n + 1)-cube induced by all bitstrings with weight n or n + 1, has a Hamilton cycle for every n ≥ 1.
Equivalently, Gn 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 Gn is bipartite and connected, and that it has N := 2n+1 + 2n+1
Θ(n)
n n+1 = 2 many
vertices. Moreover, all vertices have degree n + 1 = Θ(log(N )), i.e., this graph is rather sparse. The graph Gn 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 Gn has already N = 137.846.528.820
vertices.
The first notable asymptotic result is [Sav93], where it was shown that Gn 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].
3.1 Our contributions
We prove the middle levels conjecture in full generality.
Theorem 3.1 ( [Müt16]). For any n ≥ 1, the middle levels graph Gn has a Hamilton cycle.
In fact, we prove the following more general result.
b(n+1)/4c Ω(n)
Theorem 3.2 ( [Müt16]). For any n ≥ 1, the middle levels graph Gn has at least 14 22 = 22 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
O(n)
cycles. This establishes an upper bound of N ! = 22 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 Gn 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].
14
4 Efficient Gray code algorithms
4.1 Our contributions
We are able to translate our existence proof of a Hamilton cycle in the middle levels graph Gn into an efficient
Gray code algorithm.
Theorem 4.1 ( [MN17]). 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 Gn 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 Gn 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 Gn for n = 19 visits N = 137.846.528.820 ≈ 1011 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 Gn ).
Theorem 4.2 ( [GM18]). 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:
(i) If 0 = k < l ≤ n or 0 ≤ k < l = n.
(ii) If 1 ≤ k < l ≤ n and l − k ≥ 2 is even.
(iii) If 1 ≤ k < l ≤ n − 1 and l − k = 1.
(iv) If 1 ≤ k < l ≤ dn/2e or bn/2c ≤ k < l ≤ n − 1, and l − k ≥ 3 is odd.
For each case, there is a corresponding algorithm that generates each bitstring of a tight enumeration in time O(1)
on average.
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 Gn,` 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 Gn,` have the same size, so we may hope for the existence of a Hamilton cycle. Note, however,
15
that Gn,` 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 Gn,` 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 Gn,` .
Theorem 4.3 ( [GJMSW18]). For any n ≥ 1, the graph Gn,2 has a Hamilton cycle. For any n ≥ 1 and
3 ≤ ` ≤ n − 2, the graph Gn,` 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 (xk , xk+1 , . . . , xl ) where xi 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.
5 Bipartite Kneser graphs
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 Gk 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 Simp-
son [Sim91] and Roth (see [Gou91] and [Hur94]). Since then, there has been steady progress on the prob-
lem [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].
n−k
Note that the degree of every vertex in H(n, k) is 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.
5.1 Our contributions
We resolve the conjecture on the Hamiltonicity of bipartite Kneser graphs in full generality.
Theorem 5.1 ( [MS17]). 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.
6 Kneser graphs
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
other interesting properties. For instance, the maximum size of an independent set in K(n, k) is equal
have many
to n−1
k−1 , by the famous Erdős-Ko-Rado theorem [EKR61].
16
6.1 Hamilton cycles in Kneser graphs
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 Ok := K(2k + 1, k), for k ≥ 1, are known as odd graphs. They
include the Petersen graph O2 = K(5, 2). Note that all vertices in the odd graph Ok have degree k + 1, which
is only logarithmic in the number of vertices. The conjecture that the odd graph Ok 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 Ok even has b(k + 1)/2c 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 Ok 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 n ≥ 2k + k/( k 2 − 1) =
(1 + o(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 K(n, k) has a Hamilton cycle
if n ≥ (3k + 1 + 5k 2 − 2k + 1)/2 = (1 + o(1))2.618 . . . · k.
Another line of attack towards proving Hamiltonicity is to find long cycles in K(n, k). To this end, John-
√ showed that there exists a constant c > 0 such that the odd graph Ok has a cycle that visits at least
son [Joh04]
a (1 − c/ k)-fraction of all vertices, which is almost all vertices as k tends to infinity. Our proof techniques devel-
oped 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 Ok = K(2k + 1, k) has a cycle that visits a
1
(1 − 2k+1 )-fraction of all vertices. For instance, the Petersen graph O2 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 Ok can be partitioned into cycle factors for odd k and into cycle
factors and one matching for even k. A different cycle factor in Ok , 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
1 2k+1
same length 2k + 1, so the total number of cycles is given by the kth Catalan number 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 Ok , i.e., the graph obtained from two copies of Ok by joining corresponding vertices by a perfect matching,
is Hamiltonian for even k.
6.2 Relation to bipartite Kneser graphs
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 Ok = K(2k + 1, k) are Hamiltonian is harder than
the middle levels conjecture. Specifically, from a Hamilton cycle (x1 , . . . , xN ) in K(n, k), where N = nk ,
we can easily construct a Hamilton cycle or a Hamilton path in H(n, k), as follows. Consider the sequences
C1 := (x1 , x2 , x3 , x4 , . . .) and C2 := (x1 , x2 , x3 , x4 , . . .), where xi := [n] \ xi . If N is odd, then C1 and C2 together
form a Hamilton cycle in H(n, k). If N is even, then C1 and C2 are two cycles in H(n, k) that can be joined to
form a Hamilton path.
6.3 Our contributions
We prove that the odd graphs Ok = 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.
17
Theorem 6.1 ( [MNW18]). For any k ≥ 3, the odd graph Ok = K(2k + 1, k) has a Hamilton cycle.
Using the conditional results proved by Johnson [Joh11], Theorem 6.1 immediately yields the following more
general statement.
Theorem 6.2 ( [MNW18]). For any k ≥ 3 and a ≥ 0, the Kneser graph K(2k + 2a , k) has a Hamilton cycle.
We also establish the following counting version of Theorem 6.1.
k−6
Theorem 6.3 ( [MNW18]). For any k ≥ 6, the odd graph Ok = K(2k + 1, k) has at least 22 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 Ok 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.
References
[Als79] B. Alspach. Hamiltonian cycles in vertex-transitive graphs of order 2p. In: Proceedings of the
Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic
Univ., Boca Raton, Fla., 1979), Congressus Numerantium, XXIII–XX, pp. 131–139. Utilitas Math.,
Winnipeg, Man., 1979.
[Bab79] L. Babai. Long cycles in vertex-transitive graphs. Journal of Graph Theory, 3(3):301–304, 1979.
[Bab95] L. Babai. Automorphism groups, isomorphism, reconstruction. In: Handbook of combinatorics, Vol.
1, 2, pp. 1447–1540. Elsevier Sci. B. V., Amsterdam, 1995.
[Bal72] A. T. Balaban. Chemical graphs. XIII. Combinatorial patterns. Revue Roumaine des Mathematiques
Pures et Appliquees, 17:3–16, 1972.
[Bár78] I. Bárány. A short proof of Kneser’s conjecture. Journal of Combinatorial Theory Series A, 25(3):325–
326, 1978.
[Bar75] Zs. Baranyai. On the factorization of the complete uniform hypergraph. In: Infinite and finite sets
(Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, pp. 91–108. Colloq.
Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam, 1975.
[Big79] N. Biggs. Some odd graph theory. In: Second International Conference on Combinatorial Mathematics
(New York, 1978), volume 319 of Ann. New York Acad. Sci., pp. 71–81. New York Acad. Sci., New
York, 1979.
[BER76] J. Bitner, G. Ehrlich and E. Reingold. Efficient generation of the binary reflected Gray code and its
applications. Communications of the ACM, 19(9):517–521, 1976.
[BW84] M. Buck and D. Wiedemann. Gray codes with restricted density. Discrete Mathematics, 48(2-3):163–
171, 1984.
18
[BH11] L. R. Bueno and P. Horák. On Hamiltonian cycles in the prism over the odd graphs. Journal of
Graph Theory, 68(3):177–188, 2011.
[Cha89] P. Chase. Combination generation and graylex ordering. Congressus Numerantium, 69:215–242, 1989.
[Che98] Y. Q. Chen. On Hamiltonicity of vertex-transitive graphs and digraphs of order p4 . Journal of
Combinatorial Theory Series B, 72(1):110–121, 1998.
[Che00] Y. Chen. Kneser graphs are Hamiltonian for n ≥ 3k. Journal of Combinatorial Theory Series B,
80(1):69–79, 2000.
[Che03] Y. Chen. Triangle-free Hamiltonian Kneser graphs. Journal of Combinatorial Theory Series B,
89(1):1–16, 2003.
[CF02] Y. Chen and Z. Füredi. Hamiltonian Kneser graphs. Combinatorica, 22(1):147–149, 2002.
[CL87] B. Chen and K. Lih. Hamiltonian uniform subset graphs. Journal of Combinatorial Theory Series B,
42(3):257–263, 1987.
[CHM14] D. Christofides, J. Hladký and A. Máthé. Hamilton cycles in dense vertex-transitive graphs. Journal
of Combinatorial Theory Series B, 109:34–72, 2014.
[CI96] W. E. Clark and M. E. H. Ismail. Binomial and Q-binomial coefficient inequalities related to the
Hamiltonicity of the Kneser graphs and their Q-analogues. Journal of Combinatorial Theory Series
A, 76(1):83–98, 1996.
[Cum66] R. L. Cummins. Hamilton circuits in tree graphs. IEEE Transactions in Circuit Theory, CT-13:82–90,
1966.
[Der75] N. Dershowitz. A simplified loop-free algorithm for generating permutations. Nordisk tidskrift for
informationsbehandling (BIT), 15(2):158–164, 1975.
[DG12] P. Diaconis and R. Graham. Magical mathematics. Princeton University Press, Princeton, NJ, 2012.
The mathematical ideas that animate great magic tricks, With a foreword by Martin Gardner.
[DKS94] D. A. Duffus, H. A. Kierstead and H. S. Snevily. An explicit 1-factorization in the middle of the
Boolean lattice. Journal of Combinatorial Theory Series A, 65(2):334–342, 1994.
[DSW88] D. A. Duffus, B. Sands and R. Woodrow. Lexicographic matchings cannot form Hamiltonian cycles.
Order, 5(2):149–161, 1988.
[EHR84a] P. Eades, M. Hickey and R. Read. Some Hamilton paths and a minimal change algorithm. Journal
of the ACM, 31(1):19–29, 1984.
[EM84b] P. Eades and B. McKay. An algorithm for generating subsets of fixed size with a strong minimal
change property. Information Processing Letters, 19(3):131–133, 1984.
[Ehr73] G. Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial
configurations. Journal of the ACM, 20:500–513, 1973.
[HH01] M. El-Hashash and A. Hassan. On the Hamiltonicity of two subgraphs of the hypercube. In:
Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph
Theory and Computing (Baton Rouge, LA, 2001), volume 148, pp. 7–32, 2001.
[EKR61] P. Erdős, C. Ko and R. Rado. Intersection theorems for systems of finite sets. The Quarterly Journal
of Mathematics, 12:313–320, 1961.
[FT95] S. Felsner and W. T. Trotter. Colorings of diagrams of interval orders and α-sequences of sets.
Discrete Mathematics, 144(1-3):23–31, 1995.
[GJMSW18] P. Gregor, S. Jäger, T. Mütze, J. Sawada and K. Wille. Gray codes and symmetric chains. To
appear in Proceedings of the 45th International Colloqium on Automata, Languages and Programming
(ICALP 2018). At https://arxiv.org/abs/1802.06021, 2018.
19
[GM18] P. Gregor and T. Mütze. Trimming and gluing Gray codes. Theoretical Computer Science, 714:74–95,
2018.
[GMN18] P. Gregor, T. Mütze and J. Nummenpalo. A short proof of the middle levels theorem. To appear in
Discrete Analysis. At https://arxiv.org/abs/1710.08249, 2018.
[Gou91] R. J. Gould. Updating the Hamiltonian problem—a survey. Journal of Graph Theory, 15(2):121–157,
1991.
[Gow17] W. T. Gowers. Probabilistic combinatorics and the recent work of Peter Keevash. Bulletin of the
American Mathematical Society (N.S.), 54(1):107–116, 2017.
[Gra53] F. Gray. Pulse code communication, 1953. March 17, 1953 (filed Nov. 1947). U.S. Patent 2,632,058.
[Gre02] J. E. Greene. A new short proof of Kneser’s conjecture. American Mathematical Monthly, 109(10):918–
920, 2002.
[GŠ10] P. Gregor and R. Škrekovski. On generalized middle-level problem. Information Sciences, 180(12):2448–
2457, 2010.
[Hav83] I. Havel. Semipaths in directed cubes. In: Graphs and other combinatorial topics (Prague, 1982),
volume 59 of Teubner-Texte Math., pp. 101–108. Teubner, Leipzig, 1983.
[HW78] K. Heinrich and W. D. Wallis. Hamiltonian cycles in certain graphs. Journal of the Australian
Mathematical Society Series A, 26(1):89–98, 1978.
[Hol17] A. E. Holroyd. Perfect snake-in-the-box codes for rank modulation. IEEE Transactions on Information
Theory, 63(1):104–110, 2017.
[HRW12] A. E. Holroyd, F. Ruskey and A. Williams. Shorthand universal cycles for permutations. Algorithmica,
64(2):215–245, 2012.
[HH72] C. A. Holzmann and F. Harary. On the tree graph of a matroid. SIAM Journal on Applied
Mathematics, 22:187–193, 1972.
[HKRR05] P. Horák, T. Kaiser, M. Rosenfeld and Z. Ryjáček. The prism over the middle-levels graph is
Hamiltonian. Order, 22(1):73–81, 2005.
[Hur94] G. Hurlbert. The antipodal layers problem. Discrete Mathematics, 128(1-3):237–245, 1994.
[HN99] F. Hurtado and M. Noy. Graph of triangulations of a convex polygon and tree of triangulations.
Computational Geometry, 13(3):179–188, 1999.
[JM95] T. Jenkyns and D. McCarthy. Generating all k-subsets of {1 · · · n} with minimal changes. Ars
Combinatoria, 40:153–159, 1995.
[Joh63] S. Johnson. Generation of permutations by adjacent transposition. Mathematics of Computation,
17:282–285, 1963.
[Joh04] J. R. Johnson. Long cycles in the middle two layers of the discrete cube. Journal of Combinatorial
Theory Series A, 105(2):255–271, 2004.
[Joh09] J. R. Johnson. Universal cycles for permutations. Discrete Mathematics, 309(17):5264–5270, 2009.
[Joh11] J. R. Johnson. An inductive construction for Hamilton cycles in Kneser graphs. Electronic Journal
of Combinatorics, 18(1):Paper 189, 12, 2011.
[JK04] J. R. Johnson and H. A. Kierstead. Explicit 2-factorisations of the odd graph. Order, 21(1):19–27, 2004.
[Kar72] R. M. Karp. Reducibility among combinatorial problems. In: R. E. Miller, J. W. Thatcher, J. D.
Bohlinger (Eds.): Complexity of Computer Computations, pp. 85–103, Springer, 1972.
20
[KT88] H. A. Kierstead and W. T. Trotter. Explicit matchings in the middle levels of the Boolean lattice.
Order, 5(2):163–171, 1988.
[Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1.
Addison-Wesley, Upper Saddle River, NJ, 2011.
[KM08] K. Kutnar and D. Marušič. Hamiltonicity of vertex-transitive graphs of order 4p. European Journal
of Combinatorics, 29(2):423–438, 2008.
[KM09] K. Kutnar and D. Marušič. Hamilton cycles and paths in vertex-transitive graphs—current directions.
Discrete Mathematics, 309(17):5491–5500, 2009.
[LS03] S. Locke and R. Stong. Problem 10892: Spanning cycles in hypercubes. American Mathematical
Monthly, 110:440–441, 2003.
[Lov70] L. Lovász. Problem 11. In Combinatorial Structures and Their Applications (Proc. Calgary Internat.
Conf., Calgary, Alberta, 1969). Gordon and Breach, New York, 1970.
[Lov78] L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory
Series A, 25(3):319–324, 1978.
[Luc87] J. M. Lucas. The rotation graph of binary trees is Hamiltonian. Journal of Algorithms, 8(4):503–535,
1987.
[LRR93] J. M. Lucas, D. Roelants van Baronaigien and F. Ruskey. On rotations and the generation of binary
trees. Journal of Algorithms, 15(3):343–366, 1993.
[Mar85] D. Marušič. Vertex transitive graphs and digraphs of order pk . In: Cycles in graphs (Burnaby, B.C.,
1982), volume 115 of North-Holland Math. Stud., pp. 115–128. North-Holland, Amsterdam, 1985.
[Mar87] D. Marušič. Hamiltonian cycles in vertex symmetric graphs of order 2p2 . Discrete Mathematics,
66(1-2):169–174, 1987.
[Mat76] M. Mather. The Rugby footballers of Croam. Journal of Combinatorial Theory Series B, 20(1):62–63,
1976.
[Mat04] J. Matoušek. A combinatorial proof of Kneser’s conjecture. Combinatorica, 24(1):163–170, 2004.
[ML72] G. H. J. Meredith and E. K. Lloyd. The Hamiltonian graphs O4 to O7 . In: Combinatorics (Proc.
Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 229–236. Inst. Math. Appl., Southend-
on-Sea, 1972.
[ML73] G. H. J. Meredith and E. K. Lloyd. The footballers of Croam. Journal of Combinatorial Theory
Series B, 15:161–166, 1973.
[Müt16] T. Mütze. Proof of the middle levels conjecture. Proceedings of the London Mathematical Society,
112(4):677–713, 2016.
[MN17] T. Mütze and J. Nummenpalo. A constant-time algorithm for middle levels Gray codes. In: Proceedings
of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2238–2253. SIAM,
Philadelphia, PA, 2017.
[MN18] T. Mütze and J. Nummenpalo. Efficient computation of middle levels Gray codes. ACM Transactions
on Algorithms (TALG), 14(2):29 pp., 2018.
[MNW18] T. Mütze, J. Nummenpalo and B. Walczak. Sparse Kneser graphs are Hamiltonian. To appear in:
Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC 2018). At
https://arxiv.org/abs/1711.01636, 2018.
[MSW18] T. Mütze, C. Standke and V. Wiechert. A minimum-change version of the Chung-Feller theorem for
Dyck paths. European Journal of Combinatorics, 69:260–275, 2018.
21
[MS17] T. Mütze and P. Su. Bipartite Kneser graphs are Hamiltonian. Combinatorica, 37(6):1207–1219, 2017.
[MW12] T. Mütze and F. Weber. Construction of 2-factors in the middle layer of the discrete cube. Journal
of Combinatorial Theory Series A, 119(8):1832–1855, 2012.
[NW75] A. Nijenhuis and H. Wilf. Combinatorial algorithms. Academic Press, New York-London, 1975.
Computer Science and Applied Mathematics.
[PR09] I. Pak and R. Radoičić. Hamiltonian paths in Cayley graphs. Discrete Mathematics, 309(17):5501–
5508, 2009.
[Rus88] F. Ruskey. Adjacent interchange generation of combinations. Journal of Algorithms, 9(2):162–180,
1988.
[Sav93] C. D. Savage. Long cycles in the middle two levels of the Boolean lattice. Ars Combinatoria, 35(A):97–
108, 1993.
[Sav97] C. D. Savage. A survey of combinatorial Gray codes. SIAM Review, 39(4):605–629, 1997.
[SW95] C. D. Savage and P. Winkler. Monotone Gray codes and the middle levels problem. Journal of
Combinatorial Theory Series A, 70(2):230–248, 1995.
[SW18] J. Sawada and A. Williams. A Hamilton path for the sigma-tau problem. In: Proceedings of the
Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans,
LA, USA, January 7-10, 2018, pp. 568–575, 2018.
[Sed77] R. Sedgewick. Permutation generation methods. ACM Computing Surveys, 9(2):137–164, 1977.
[SW15] X. S. Shen and A. Williams. A middle levels conjecture for multiset permutations with uniform-
frequency. Preprint available at http://www.columbia.edu/˜xss2000/multiset.pdf, 2015.
[SS99] I. Shields and C. D. Savage. A Hamilton path heuristic with applications to the middle two levels
problem. In: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics,
Graph Theory, and Computing (Boca Raton, Florida, 1999), volume 140, pp. 161–178, 1999.
[SS04] I. Shields and C. D. Savage. A note on Hamilton cycles in Kneser graphs. Bulletin of the Institute of
Combinatorics and its Applications, 40:13–22, 2004.
[SSS09] I. Shields, B. Shields and C. D. Savage. An update on the middle levels problem. Discrete Mathematics,
309(17):5271–5277, 2009.
[SA11] M. Shimada and K. Amano. A note on the middle levels conjecture. At
https://arxiv.org/abs/0912.4564, 2011.
[Sim91] J. Simpson. Hamiltonian bipartite graphs. In: Proceedings of the Twenty-second Southeastern
Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), volume 85,
pp. 97–110, 1991.
[Sim94] J. Simpson. On uniform subset graphs. Ars Combinatoria, 37:309–318, 1994.
[SW14] B. Stevens and A. Williams. The coolest way to generate binary strings. Theory of Computing
Systems, 54(4):551–577, 2014.
[TL73] D. Tang and C. Liu. Distance-2 cyclic chaining of constant-weight codes. IEEE Transactions on
Computers, C-22:176–180, 1973.
[Tro62] H. Trotter. Algorithm 115: Perm. Communications of the ACM, 5(8):434–435, 1962.
[Tur67] J. Turner. Point-symmetric graphs with a prime number of points. Journal of Combinatorial Theory,
3:136–145, 1967.
22
[Wil89] H. Wilf. Combinatorial algorithms: an update, volume 55 of CBMS-NSF Regional Conference Series
in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA,
1989.
[Win04] P. Winkler. Mathematical puzzles: a connoisseur’s collection. A K Peters, Ltd., Natick, MA, 2004.
[www] The Combinatorial Object Server. At http://www.math.tu-berlin.de/~muetze/cos
[Zie02] G. M. Ziegler. Generalized Kneser coloring theorems with combinatorial proofs. Inventiones
Mathematicae, 147(3):671–691, 2002.
23