PERFECT SNAKE-IN-THE-BOX CODES
FOR RANK MODULATION

arXiv:1602.08073v3 [math.CO] 14 Oct 2016

ALEXANDER E. HOLROYD
Abstract. For odd n, the alternating group on n elements is generated by the permutations that jump an element from any odd position to position 1. We prove Hamiltonicity
of the associated directed Cayley graph for all odd n 6= 5. (A result of Rankin implies that
the graph is not Hamiltonian for n = 5.) This solves a problem arising in rank modulation
schemes for flash memory. Our result disproves a conjecture of Horovitz and Etzion, and
proves another conjecture of Yehezkeally and Schwartz.

1. Introduction
The following questions are motivated by applications involving flash memory. Let Sn
be the symmetric group of permutations π = [π(1), . . . , π(n)] of [n] := {1, . . . , n}, with
composition defined by (πρ)(i) = π(ρ(i)). For 2 ≤ k ≤ n let


τk := k, 1, 2, . . . , k − 1, k + 1, . . . , n ∈ Sn

be the permutation that jumps element k to position 1 while shifting elements 1, 2, . . . , k−1
right by one place. Let Sn be the directed Cayley graph of Sn with generators τ2 , . . . , τn ,
i.e. the directed graph with vertex set Sn and a directed edge, labelled τi , from π to πτi
for each π ∈ Sn and each i = 2, . . . , n.
We are concerned with self-avoiding directed cycles (henceforth referred to simply as
cycles except where explicitly stated otherwise) in Sn . (A cycle is self-avoiding if it visits
each vertex at most once). In applications to flash memory, a permutation represents the
relative ranking of charges stored in n cells. Applying τi corresponds to the operation of
increasing the ith charge to make it the largest, and a cycle is a schedule for visiting a
set of distinct charge rankings via such operations. Schemes of this kind were originally
proposed in [10].
One is interested in maximizing the length of such a cycle, since this maximizes the
information that can be stored. It is known that Sn has a directed Hamiltonian cycle,
i.e. one that includes every permutation exactly once; see e.g. [8, 10, 11, 13]. However,
for the application it is desirable that the cycle should not contain any two permutations
that are within a certain fixed distance r of each other, with respect to some metric d on
Sn . The motivation is to avoid errors arising from one permutation being mistaken for
another [10, 14]. The problem of maximizing cycle length for given r, d combines notions
of Gray codes [18] and error-detecting/correcting codes [2], and is sometimes known as a
snake-in-the-box problem. (This term has its origins in the study of analogous questions
involving binary strings as opposed to permutations; see e.g. [1]).
Date: 24 February 2016 (revised 10 October 2016).
Key words and phrases. Hamiltonian cycle; Cayley graph; snake-in-the-box; Gray code; rank
modulation.
1

2

ALEXANDER E. HOLROYD

The main result of this article is that, in the case that has received most attention
(described immediately below) there is a cycle that is perfect, i.e. that has the maximum
size even among arbitrary sets of permutations satisfying the distance constraint.
More precisely, our focus is following case considered in [9, 24, 25]. Let r = 1 and let
d be the Kendall tau metric [12], which is defined by setting d(π, σ) to be the inversion
number of π −1 σ, i.e. the minimum number of elementary transpositions needed to get from
π to σ. (The ith elementary transposition swaps the permutation elements in positions
i and i + 1, where 1 ≤ i ≤ n − 1). Thus, the cycle is not allowed to contain any two
permutations that are related by a single elementary transposition. The primary object of
interest is the maximum possible length Mn of such a directed cycle in Sn .
It is easy to see that Mn ≤ n!/2. Indeed, any set of permutations satisfying the above
distance constraint includes at most one from the pair {π, πτ2 } for every π, but these pairs
partition Sn . To get a long cycle, an obvious approach is to restrict to the alternating
group An of all even permutations. Since an elementary transposition changes the parity
of a permutation, this guarantees that the distance condition is satisfied. The generator
τk lies in An if and only if k is odd. Therefore, if n is odd, this approach reduces to
the problem of finding a maximum directed cycle in the directed Cayley graph An of An
with generators τ3 , τ5 , . . . , τn . Yehezkeally and Schwartz [24] conjectured that for odd n
the maximum cycle length Mn is attained by a cycle of this type; our result will imply
this. (For even n this approach is less useful, since without using τn we can access only
permutations that fix n.) As in [9, 24, 25], we focus mainly on odd n.
For small odd n, it is not too difficult to find cycles in An with length reasonably close
to the upper bound n!/2, by ad-hoc methods. Finding systematic approaches that work
for all n is more challenging. Moreover, getting all the way to n!/2 apparently involves a
fundamental obstacle, but we will show how it can be overcome.
Specifically, it is obvious that M3 = 3!/2 = 3. For general odd n ≥ 5, Yehezkeally √
and
Schwartz [24] proved the inductive bound Mn ≥ n(n − 2)Mn−2 , leading to Mn ≥ Ω(n!/ n)
asymptotically. They also showed by computer search that M5 = 5!/2 − 3 = 57. Horowitz
and Etzion [9] improved the inductive bound to Mn ≥ (n2 −n−1)Mn−2 , giving Mn = Ω(n!).
They also proposed an approach for constructing a longer cycle of length n!/2 − n + 2(=
(1 − o(1))n!/2), and showed by computer search that it works for n = 7 and n = 9. They
conjectured that this bound is optimal for all odd n. Zhang and Ge [25] proved that the
scheme of [9] works for all odd n, establishing Mn ≥ n!/2 − n + 2, and proposed another
scheme aimed at improving the bound by 2 to n!/2 − n + 4. Zhang and Ge proved that
their scheme works for n = 7, disproving the conjecture of [9] in this case, but were unable
to prove it for general odd n.
The obvious central question here is whether there exists a perfect cycle, i.e. one of
length n!/2, for any odd n > 3. As mentioned above, Horovitz and Etzion [9] conjectured
a negative answer for all such n, while the authors of [24, 25] also speculate that the answer
is negative. We prove a positive answer for n 6= 5.
Theorem 1. For all odd n ≥ 7, there exists a directed Hamiltonian cycle of the directed
Cayley graph An of the alternating group An with generators τ3 , τ5 , . . . , τn . Thus, Mn =
n!/2.
Besides being the first of optimal length, our cycle has a somewhat simpler structure
than those in [9, 25]. It may in principle be described via an explicit rule that specifies

PERFECT SNAKE-IN-THE-BOX CODES

3

which generator should immediately follow each permutation π, as a function of π. (See
[8, 22] for other Hamiltonian cycles of Cayley graphs that can be described in this way).
While the improvement from n!/2 − n + 2 to n!/2 is in itself unlikely to be important for
applications, our methods are quite general, and it is hoped that they will prove useful for
related problems.
We briefly discuss even n. Clearly, one approach is to simply leave the last element of the
permutation fixed, and use a cycle in An−1 , which gives Mn ≥ Mn−1 for even n. Horovitz
and Etzion [9] asked for a proof or disproof that this is optimal. In fact, we expect that
one can do much better. We believe that Mn ≥ (1 − o(1))n!/2 asymptotically as n → ∞
(an n-fold improvement over (n − 1)!/2), and perhaps even Mn ≥ n!/2 − O(n2). We will
outline a possible approach to showing bounds of this sort, although it appears that a full
proof for general even n would be rather messy. When n = 6 we use this approach to show
M6 ≥ 315 = 6!/2 − 45, improving the bound M6 ≥ 57 of [9] by more than a factor of 5.
Hamiltonian cycles of Cayley graphs have been extensively studied, although general
results are relatively few. See e.g. [4, 13, 15, 23] for surveys. In particular, it is unknown
whether every undirected Cayley graph is Hamiltonian. Our key construction (described
in the next section) appears to be novel in the context of this literature also.
Central to our proof are techniques having their origins in change ringing (Englishstyle church bell ringing). Change ringing is also concerned with self-avoiding cycles in
Cayley graphs of permutations groups (with a permutation representing an order in which
bells are rung), and change ringers discovered key aspects of group theory considerably
before mathematicians did – see e.g. [5, 7, 20, 21]. As we shall see, the fact that A5 has no
Hamiltonian cycle (so that we have the strict inequality M5 < 5!/2) follows from a theorem
of Rankin [16, 19] that was originally motivated by change ringing.
2. Breaking the parity barrier
In this section we explain the key obstruction that frustrated the previous attempts at
a Hamiltonian cycle of An in [9, 24, 25]. We then explain how it can be overcome. We will
then use these ideas to prove Theorem 1 in Sections 3 and 4.
By a cycle cover of a directed Cayley graph we mean a set of self-avoiding directed
cycles whose vertex sets partition the vertex set of the graph. A cycle or a cycle cover can
be specified in several equivalent ways: we can list the vertices or edges encountered by a
cycle in order, or we can specify a starting vertex of a cycle and list the generators it uses
in order, or we can specify which generator immediately follows each vertex – i.e. the label
of the unique outgoing edge that belongs to the cycle or cycle cover. It will be useful to
switch between these alternative viewpoints.
A standard approach to constructing a Hamiltonian cycle is to start with a cycle cover,
and then successively make local modifications that unite several cycles into one, until we
have a single cycle. (See [3, 4, 7–9, 15, 17, 22–25] for examples.) However, in An and many
other natural cases, there is a serious obstacle involving parity, as we explain next.
The order order(g) of a group element g is the smallest t ≥ 1 such that g t = id, where
id is the identity. In our case, let τk , τℓ be two distinct generators of An , and observe that
their ratio ρ := τℓ τk−1 is simply the permutation that jumps element ℓ to position k while
shifting the intervening elements by 1. For example, when n = 9 we have τ9 = [912345678]
and τ7−1 = [234567189], so τ9 τ7−1 = [123456978] (element 9 jumps first to position 1 and

4

ALEXANDER E. HOLROYD

then back to position 7). In general, the ratio ρ has order q := |k − ℓ| + 1, which is odd.
In the example, q = 3.
The fact that order(ρ) = q corresponds to the fact that in the Cayley graph An , starting
from any vertex, there is a cycle of length 2q consisting of directed edges oriented in
alternating directions and with alternating labels τℓ and τk . Consider one such alternating
cycle Q, and suppose that we have a cycle cover that includes all q of the τk -edges of Q.
Consequently, it includes none of the τℓ -edges of Q (since it must include only one outgoing
edge from each vertex). An example is the cycle cover that uses the outgoing τk -edge from
every vertex of An . Then we may modify the cycle cover as follows: delete all the τk -edges
of Q, and add all the τℓ -edges of Q. This results in a new cycle cover, because each vertex
of the graph still has exactly one incoming edge and one outgoing edge present.
Suppose moreover that all the τk -edges of Q lay in distinct cycles in the original cycle
cover. Then the effect of the modification is precisely to unite these q cycles into one new
cycle (having the same vertices). The new cycle alternately traverses the new τℓ -edges
and the remaining parts of the q original cycles. All other cycles of the cycle cover are
unaffected. See Figure 1 (left) for the case (k, ℓ) = (n − 2, n) (with q = 3), and Figure 1
(right) for the permutations at the vertices of the alternating cycle Q.
A modification of the above type reduces the total number of cycles in the cycle cover
by q − 1, and therefore, since q is odd, it does not change the parity of the total number of
cycles. Less obviously, it turns out that this parity is preserved by such a modification even
if we relax the assumption that the q deleted edges lie in distinct cycles. (See [16] or [19]
for proofs.) This is a problem, because many cycle covers that one might naturally start
with have an even number of cycles. This holds in particular for the cycle cover that uses
a single generator τk everywhere (for n ≥ 5), and also for the one that arises in an obvious
inductive approach to proving Theorem 1 (comprising |An |/|An−2| = n(n − 1) cycles each
of length |An−2 |). Thus we can (apparently) never get to a Hamiltonian cycle (i.e. a cycle
cover of one cycle) by this method.
The above ideas in fact lead to the following rigorous condition for non-existence of
directed Hamiltonian cycles. The result was proved by Rankin [16], based on an 1886
proof by Thompson [20] of a special case arising in change ringing; Swan [19] later gave a
simpler version of the proof.
Theorem 2. Consider the directed Cayley graph G of a finite group with two generators
a, b. If order(ab−1 ) is odd and |G|/ order(a) is even, then G has no directed Hamiltonian
cycle.
An immediate consequence is that A5 has no directed Hamiltonian cycle (confirming the
computer search result of [9]), and indeed An has no directed Hamiltonian cycle using only
two generators for odd n ≥ 5.
To break the parity barrier, we must use at least three generators in a fundamental
way. The problem with the previous approach was that order(τℓ τk−1 ) is odd: we need an
analogous relation involving composition of an even number of ratios of two generators. In
terms of the graph An , we need a cycle of length a multiple of 4 whose edges are oriented
in alternating directions. It is clear that such a thing must exist for all odd n ≥ 7, because
the ratios τk τℓ−1 generate the alternating group on the n − 2 elements {3, . . . , n}, which
contains elements of even order. We will use the example:

−1
−1
−1
(1)
order ζ = 2, where ζ := τn τn−2
τn τn−4
τn τn−4
.

PERFECT SNAKE-IN-THE-BOX CODES

·
c
·
b
·
a
·

τn
τn−2

τn−2

τn

τn
τn−2

·
·
·
·
·
·
·

5

·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·

·
·
·
·
·
·
·

a
·
c
·
b
·
a

b
a
a
c
c
b
b

c
b
b
a
a
c
c

Figure 1. Left: linking 3 cycles by replacing generator τn−2 with generator
τn in 3 places. We start with the 3 thin blue cycles, each of which comprises a
dotted edge labeled with generator τn−2 , and a curved arc that represents the
remaining part of the cycle. We delete the dotted edges and replace them
with the thick solid black edges (labelled τn ), to obtain one (solid) cycle,
containing the same vertices as the original 3 cycles. Right: the permutations
at the six vertices that are marked with solid discs in the left picture. The
permutation at the (green) circled vertex is [. . . . . . , a, b, c], where a, b, c ∈ [n],
and the permutations are listed in clockwise order around the inner hexagon
starting and finishing there. The ellipsis · · · · · · represents a sequence of n−3
distinct elements of [n], the same sequence everywhere it occurs. A solid
black curve indicates that the ratio between the two successive permutations
is τn (so that an element jumps from position n to 1), while a dotted blue
−1
curve indicates τn−2
(with a jump from 1 to n − 2).

τn−4

τn

τn

τn−4
τn

τn−2

τn−2
τn
τn−4

τn
τn

τn−4

·
e
·
d
·
c
·
e
·
b
·
a
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·

a
·
a
·
d
·
c
·
c
·
b
·
a

b
a
b
a
a
d
d
c
d
c
c
b
b

c
b
e
b
b
a
a
d
e
d
d
c
c

d
c
c
e
e
b
b
a
a
e
e
d
d

e
d
d
c
c
e
e
b
b
a
a
e
e

Figure 2. The key construction. Left: replacing a suitable combination
of generators τn−2 and τn−4 with τn links 6 cycles into one, breaking the
parity barrier. We start with the 2 blue and 4 red thin cycles, and replace
the dotted edges with the thick black solid edges to obtain the solid cycle.
Right: the permutations appearing at the vertices marked with solid discs,
listed in clockwise order starting and ending at the circled vertex, which is
[. . . . , a, b, c, d, e]. The ellipsis · · · · represents the same sequence everywhere
it occurs.

6

ALEXANDER E. HOLROYD

−1
It is a routine matter to check (1): the ratio τn τn−s
is the permutation that jumps an
element from position n to n − s (while fixing 1, . . . , n − s − 1 and shifting n − s, . . . , n − 1
right one place), so to compute the composition ζ of three such ratios we need only keep
track of the last 5 elements. Figure 2 (right) shows the explicit computation: starting
from an arbitrary permutation π = [. . . , a, b, c, d, e] ∈ An , the successive compositions
−1
−1
π, πτn , πτn τn−2
, πτn τn−2
τn , . . . , πζ 2 = π are listed – the ellipsis · · · · represents the same
sequence everywhere it occurs. This explicit listing of the relevant permutations will be
useful later.
We can use the above observation to link 6 cycles into one, as shown in Figure 2 (left).
Let Q′ be a length-12 cycle in An with edges in alternating orientations that corresponds
to the identity (1). That is to say, every alternate edge in Q′ has label τn , and is oriented
in the same direction around Q′ . The other 6 edges are oriented in the opposite direction,
and have successive labels τn−2 , τn−4 , τn−4 , τn−2 , τn−4 , τn−4 . Suppose that we start with a
cycle cover in which the two τn−2 -edges and the four τn−4 -edges of Q′ all lie in distinct
cycles. Then we can delete these 6 edges and replace them with the six τn -edges of Q′ .
This results in a new cycle cover in which these 6 cycles have been united into one, thus
reducing the number of cycles by 5 and changing its parity. See Figure 2 (left) – the old
cycles are in thin red and blue, while the new cycle is shown by solid lines and arcs.
We will prove Theorem 1 by induction. The inductive step will use one instance of
the above 6-fold linkage to break the parity barrier, together with many instances of the
simpler 3-fold linkage described earlier with (k, ℓ) = (n − 2, n). The base case n = 7 will
use the 6-fold linkage in the reverse direction (replacing six τn -edges with τn−2 , τn−4 , . . .),
together with the cases (k, ℓ) = (7, 5), (7, 3) of the earlier linkage.

3. Hypergraph spanning
The other main ingredient for our proof is a systematic way of organizing the various
linkages. For this the language of hypergraphs will be convenient. Similar hypergraph
constructions were used in [9, 25]. A hypergraph (V, H) consists of a vertex set V and a
set H of nonempty subsets of V , which are called hyperedges. A hyperedge of size r is
called an r-hyperedge.
The incidence graph of a hypergraph (V, H) is the bipartite graph with vertex set
V ∪ H, and with an edge between v ∈ V and h ∈ H if v ∈ h. A component of a
hypergraph is a component of its incidence graph, and a hypergraph is connected if it has
one component. We say that a hypergraph is acyclic if its incidence graph is acyclic. Note
that this a rather strong condition: for example, if two distinct hyperedges h and h′ share
two distinct vertices v and v ′ then the hypergraph is not acyclic. (Several non-equivalent
notions of acyclicity for hypergraphs have been considered – the notion we use here is
sometimes called Berge-acyclicity – see e.g. [6]).
We are interested in hypergraphs of a particular kind that are related to the linkages
considered in the previous section. Let [n](k) be the set of all n!/(n − k)! ordered ktuples of distinct elements of [n]. If t = (a, b, c) ∈ [n](3) is a triple, define the triangle
∆(t) = ∆(a, b, c) := {(a, b), (b, c), (c, a)} ⊂ [n](2) of pairs that respect the cyclic order.
(Note that ∆(a, b, c) = ∆(c, a, b) 6= ∆(c, b, a).) In our application to Hamiltonian cycles,
∆(a, b, c) will encode precisely the linkage of 3 cycles shown in Figure 1. The following fact
and its proof are illustrated in Figure 3.

PERFECT SNAKE-IN-THE-BOX CODES
19

7

98

87
28

18

81

29

71

91

27

92
39

38

82 37 72

36

76
61

12

49
62
35
52

23

93 48 83

47

59 94
73
46
63

34

58

69

84
57
74

45

95
68
85

56

79
96
67

78

89

17
26

42
51

65

53

64

75

86

97

31
25

41

14

24

16

13

43
54

15

21

32

Figure 3. The hypergraph of Proposition 3, when n = 9. The vertices are
all the ordered pairs (a, b) = ab ∈ [n](2) , and the hyperedges are triangles of
the form {ab, bc, ca}. Hyperedges are colored according to the step of the
induction at which they are added. In the last step from n = 8 to n = 9, all
the white hyperedges are added, i.e. those incident to vertices that contain
9.
Proposition 3. Let n ≥ 3. There exists an acyclic hypergraph with vertex set [n](2) , with
all hyperedges being triangles ∆(t) for t ∈ [n](3) , and with exactly two components: one
containing precisely the 3 vertices of ∆(3, 2, 1), and the other containing all other vertices.
Proof. We give an explicit inductive construction. When n = 3 we simply take as hyperedges the two triangles ∆(3, 2, 1) and ∆(1, 2, 3).
Now let n ≥ 4, and assume that ([n − 1](2) , H) is a hypergraph satisfying the given
conditions for n − 1. Consider the larger hypergraph ([n](2) , H) with the same set of hyperedges, and note that its components are precisely: (i) ∆(3, 2, 1); (ii) an acyclic component
which we denote K that contains all vertices of [n − 1](2) \ ∆(3, 2, 1); and (iii) the 2n − 2
isolated vertices {(i, n), (n, i) : i ∈ [n − 1]}.
We will add some further hyperedges to ([n](2) , H). For i ∈ [n − 1], write i+ for the
integer in [n − 1] that satisfies i+ ≡ (i + 1) mod (n − 1), and define

D := ∆(i, i+ , n) : i ∈ [n − 1]

= ∆(1, 2, n), ∆(2, 3, n), . . . , ∆(n − 2, n − 1, n), ∆(n − 1, 1, n) .
Any element ∆(i, i+ , n) of D has 3 vertices. One of them, (i, i+ ), lies in K, while the
others, (i+ , n) and (n, i), are isolated vertices of ([n](2) , H). Moreover, each isolated vertex
of ([n](2) , H) appears in exactly one hyperedge in D. Therefore, ([n](2) , H ∪ D) has all the
claimed properties.

We remark that the above hypergraph admits a simple (non-inductive) description – it
consists of all ∆(a, b, c) such that max{a, b} < c and b ≡ (a + 1) mod (c − 1).
In order to link cycles into a Hamiltonian cycle we will require a connected hypergraph.
For n ≥ 3 there is no connected acyclic hypergraph of triangles with vertex set [n](2) .
(This follows from parity considerations: an acyclic component composed of m triangles
has 1 + 2m vertices, but |[n](2) | is even.) Instead, we simply introduce a larger hyperedge,
as follows.

8

ALEXANDER E. HOLROYD

Corollary 4. Let n ≥ 5 and let a, b, c, d, e ∈ [n] be distinct. There exists a connected acyclic
hypergraph with vertex set [n](2) such that one hyperedge is the 6-hyperedge ∆(a, b, e) ∪
∆(c, d, e), and all others are triangles ∆(t) for t ∈ [n](3) .
Proof. By symmetry, it is enough to prove this for any one choice of (a, b, c, d, e); we choose
(2, 1, 4, 5, 3). The result follows from Proposition 3, on noting that ∆(3, 4, 5) = ∆(4, 5, 3)
is a hyperedge of the hypergraph constructed there: we simply unite it with ∆(3, 2, 1) =
∆(2, 1, 3) to form the 6-hyperedge.

4. The Hamiltonian cycle
We now prove Theorem 1 by induction on (odd) n. We give the inductive step first,
followed by the base case n = 7. The following simple observation will be used in the
inductive step.
Lemma 5. Let n ≥ 3 be odd, and consider any Hamiltonian cycle of An . For every i ∈ [n]
there exists a permutation π ∈ An with π(n) = i that is immediately followed by a τn -edge
in the cycle.
Proof. Since the cycle visits all permutations of An , it must contain a directed edge from
a permutation π satisfying π(n) = i to a permutation π ′ satisfying π ′ (n) 6= i. This is a
τn -edge, since any other generator would fix the rightmost element.

Proof of Theorem 1, inductive step. We will prove by induction on odd n ≥ 7 the statement:
(2)

there exists a Hamiltonian cycle of An that includes at least one τn−2 -edge.

As mentioned above, we postpone the proof of the base case n = 7. For distinct a, b ∈ [n]
define the set of permutations of the form [. . . , a, b]:
n
o

An (a, b) := π ∈ An : π(n − 1), π(n) = (a, b) .
Let n ≥ 9, and let L = (τs(1) , τs(2) , . . . , τs(m) ) be the sequence of generators used by a
Hamiltonian cycle of An−2 , as guaranteed by the inductive hypothesis, in the order that
they are encountered in the cycle starting from id ∈ An−2 (where m = (n − 2)!/2, and
s(i) ∈ {3, 5, . . . , n − 2} for each i). Now start from any permutation π ∈ An (a, b) and
apply the sequence of generators L (where a generator τk ∈ An−2 is now interpreted as
the generator τk ∈ An with the same name). This gives a cycle in An whose vertex set is
precisely An (a, b). (The two rightmost elements a, b of the permutation are undisturbed,
because L does not contain τn .) Note that, for given a, b, different choices of the starting
permutation π ∈ An (a, b) in general result in different cycles.
We next describe the idea of the proof, before giving the details. Consider a cycle cover
C comprising, for each (a, b) ∈ [n](2) , one cycle C(a, b) with vertex set An (a, b) of the form
described above (so n(n − 1) cycles in total). We will link the cycles of C together into a
single cycle by substituting the generator τn at appropriate points, in the ways discussed
in Section 2. The linking procedure will be encoded by the hypergraph of Corollary 4. The
vertex (a, b) of the hypergraph will correspond to the initial cycle C(a, b). A 3-hyperedge
∆(a, b, c) will indicate a substitution of τn for τn−2 in 3 of the cycles of C, linking them
together in the manner of Figure 1. The 6-hyperedge will correspond to the parity-breaking
linkage in which τn is substituted for occurrences of both τn−2 and τn−4 , linking 6 cycles as

PERFECT SNAKE-IN-THE-BOX CODES

9

in Figure 2. One complication is that the starting points of the cycles of C must be chosen
so that τn−2 - and τn−4 -edges occur in appropriate places so that all these substitutions are
possible. To address this, rather than choosing the cycle cover C at the start, we will in fact
build our final cycle sequentially, using one hyperedge at a time, and choosing appropriate
cycles C(a, b) as we go. We will start with the 6-hyperedge, and for each subsequent
3-hyperedge we will link in two new cycles. Lemma 5 will ensure enough τn−2 -edges for
subsequent steps: for any (a, b, c) ∈ [n](3) , there is a vertex of the form [. . . , a, b, c] in C(b, c)
followed by τn−2 -edge. The inductive hypothesis (2) will provide the τn−4 -edges needed for
the initial 6-fold linkage.
We now give the details. In preparation for the sequential linking procedure, choose an
acyclic connected hypergraph ([n](2) , H) according to Corollary 4, with the 6-hyperedge
being ∆0 ∪ ∆′0 , where ∆0 := ∆(c, d, e) and ∆′0 := ∆(a, b, e), and where we write
(3)

(a, b, c, d, e) = (n − 4, n − 3, n − 2, n − 1, n).

Let N = |H| − 1, and order the hyperedges as H = {h0 , h1 , . . . , hN } in such a way that
h0 = ∆0 ∪ ∆′0 is the 6-hyperedge, and, for each 1 ≤ i ≤ N, the hyperedge hi shares
S
exactly one vertex with i−1
ℓ=0 hℓ . (To see that this is possible, note that for any choice of
h0 , . . . , hi−1 satisfying this condition, connectedness of the hypergraph implies that there
exists hi that shares at least one vertex with one of its predecessors; acyclicity then implies
that it shares exactly one.)
We will construct the required Hamiltonian cycle via a sequence of steps j = 0, . . . , N.
At the end of step j we will have a self-avoiding directed cycle Cj in An with the following
properties.
S
(i) The vertex set of Cj is the union of An (x, y) over all (x, y) ∈ ji=0 hi .
S
(ii) For every (x, y, z) ∈ [n](3) such that (y, z) ∈ ji=0 hi but ∆(x, y, z) ∈
/
{∆0 , ∆′0 , h1 , h2 , . . . , hj }, there exists a permutation π ∈ An of the form
[. . . , x, y, z] that is followed immediately by a τn−2 -edge in Cj .
We will check by induction on j that the above properties hold. The final cycle CN will
be the required Hamiltonian cycle. The purpose of the technical condition (ii) is to ensure
that suitable edges are available for later linkages; the idea is that the triple (x, y, z) is
available for linking in two further cycles unless it has already been used.
We will describe the cycles Cj by giving their sequences of generators. Recall that L is
the sequence of generators of the Hamiltonian cycle of An−2 . Note that L contains both
τn−2 and τn−4 , by Lemma 5 and the inductive hypothesis (2) respectively. For each of
k = n − 2, n − 4, fix some location i where τk occurs in L (so that s(i) = k), and let L[τk ]
be the sequence obtained by starting at that location and omitting this τk from the cycle:

L[τk ] := τs(j+1) , τs(j+2) . . . , τs(m) , τs(1) , . . . , τs(j−1) .
Note that the composition in order of the elements of L[τk ] is τk−1 .
For step 0, let C0 be the cycle that starts at id ∈ An and uses the sequence of generators
τn , L[τn−2 ], τn , L[τn−4 ], τn , L[τn−4 ],
τn , L[τn−2 ], τn , L[τn−4 ], τn , L[τn−4 ],

10

ALEXANDER E. HOLROYD

(where commas denote concatenation). This cycle is precisely of the form illustrated in
Figure 2 (left) by the solid arcs and lines. The curved arcs represent the paths corresponding to the L[·] sequences. The vertex set of each such path is precisely An (u, v) for some
pair (u, v); we denote this path P (u, v). The solid lines represent the τn -edges. Moreover, since Figure 2 (right) lists the vertices (permutations) at the beginning and end of
each path P (u, v), we can read off the pairs (u, v). With a, . . . , e as in (3), the pairs are
{(d, e), (c, d), (e, c), (b, e), (a, b), (e, a)}. This set equals ∆0 ∪ ∆′0 = h0 , so property (i) above
holds for the cycle C0 .
We next check that C0 satisfies (ii). Let (x, y, z) ∈ [n](3) be such that (y, z) ∈ h0 . The
cycle C0 includes a path P (y, z) with vertex set An (y, z) and generator sequence L[τk ]
(where k is n − 2 or n − 4). Let C(y, z) be the cycle that results from closing the gap,
i.e. appending a τk -edge f to the end of P (y, z). Note that P (y, z) and C(y, z) both have
vertex set An (y, z). By Lemma 5 applied to An−2, the cycle C(y, z) contains a permutation
of the form [. . . , x, y, z] immediately followed by a τn−2 -edge, g say. Edge g is also present
in C0 unless g = f . Consulting Figure 2, and again using the notation in (3), we see that
this happens only in the two cases (x, y, z) = (e, c, d), (e, a, b). But in these cases we have
∆(x, y, z) = T0 , T0′ respectively. Thus condition (ii) is satisfied at step 0.
Now we inductively describe the subsequent steps. Suppose that step j − 1 has been
completed, giving a cycle Cj−1 that satisfies (i) and (ii) (with parameter j −1 in place of j).
We will augment Cj−1 to obtain a larger cycle Cj , in a manner encoded by the hyperedge
hj . Let

hj = ∆(a, b, c) = (a, b), (b, c), (c, a)
(where we no longer adopt the notation (3)). By our choice of the ordering of H, exactly
Sj−1
one of these pairs belongs to i=0
hi ; without loss of generality, let it be (b, c). By property
(ii) of the cycle Cj−1, it contains a vertex of the form [. . . , a, b, c] immediately followed by
a τn−2 -edge, f say. Delete edge f from Cj−1 to obtain a directed path Pj−1 with the same
vertex set. Append to Pj−1 the directed path that starts at the endvertex of Pj−1 and then
uses the sequence of generators
τn , L[τn−2 ], τn , L[τn−2 ], τn .
−1
) = 3, this gives a cycle, which we denote Cj .
Since order(τn τn−2
The new cycle Cj has precisely the form shown in Figure 1 (left) by the solid arcs and
lines, where Cj−1 is the thin blue cycle in the upper left, containing the circled vertex,
which is the permutation [. . . , a, b, c]. The arc is Pj−1, and the dotted edge is f . As
before, the permutations at the filled discs may be read from Figure 1 (right). Thus, Cj
consists of the path Pj−1 , together with two paths P (a, b), P (c, a) with respective vertex
sets An (a, b), An (c, a) (the other two thin blue arcs in the figure), and three τn -edges (thick
black lines) connecting these three paths. Hence Cj satisfies property (i).
We now check that Cj satisfies (ii). The argument is similar to that used in step 0. Let
(x, y, z) satisfy the assumptions in (ii). We consider two cases. First suppose (y, z) ∈
/ hj .
Sj−1
hi , and so property (ii) of Cj−1 implies that Cj−1 has a vertex of the
Then (y, z) ∈ i=0
form [. . . , x, y, z] followed by a τn−2 -edge g, say. Then g is also present in Cj unless g = f .
But in that case we have (x, y, z) = (a, b, c), and so ∆(x, y, z) = hj , contradicting the
assumption on (x, y, z). On the other hand, suppose (y, z) ∈ hj . Then (y, z) equals (a, b)
or (c, a). Suppose the former; the argument in the latter case is similar. Let C(a, b) be the

PERFECT SNAKE-IN-THE-BOX CODES

11

row
permutations
generator
1
6777∗∗∗, 7776∗∗∗
τ5
2
67∗∗∗∗∗, 76∗∗∗∗∗
τ3
3
5671∗∗∗, 576∗∗∗∗
τ5
4
2567∗∗∗, 4576∗∗∗
τ5
5 5671234, 5612347, 5623714, 5637142
τ3
6
5623471, 5671423
τ5
7
otherwise
τ7
Table 1. Rules for generating a directed Hamiltonian cycle of A7 . Permutations of the given forms should be followed by the generator in the same
row of the table. The symbol ∗ denotes an arbitrary element of [7], and a
denotes any element other than a.

cycle obtained by appending a τn−2 -edge to P (a, b). Applying Lemma 5 shows that C(a, b)
contains a vertex of the form [. . . , x, a, b] followed by a τn−2 -edge g, say. Then g is also
present in P (a, b) unless x = c, but then ∆(x, y, z) = hj , contradicting the assumption in
(ii). Thus, property (ii) is established.
To conclude the proof, note that the final cycle CN is Hamiltonian, by property (i) and
the fact that the hypergraph of Corollary 4 has vertex set [n](2) . To check that it includes
some τn−2 -edge as required for (2), recall that hN has only one vertex in common with
h0 , . . . , hN −1 , so there exist x, y, z with (y, z) ∈ hN but ∆(x, y, z) ∈
/ H. Hence property (ii)
implies that CN contains a τn−2 -edge.

Proof of Theorem 1, base case. For the base case of the induction, we give an explicit directed Hamiltonian cycle of A7 that includes τ5 at least once. (In fact the latter condition
must necessarily be satisfied, since, as remarked earlier, Theorem 2 implies that there is
no Hamiltonian cycle using only τ3 and τ7 .)
Table 1 specifies which generator the cycle uses immediately after each permutation of
A7 , as a function of the permutation itself. The skeptical reader may simply check by
computer that these rules generate the required cycle. But the rules were constructed by
hand; below we briefly explain how.
First suppose that from every permutation of A7 we apply the τ7 generator, as specified
in row 7 of the table. This gives a cycle cover comprising |A7 |/7 = 360 cycles of size 7.
Now consider the effect of replacing some of these τ7 ’s according to rows 1–6 in succession.
Each such replacement performs a linkage, as in Figures 1 and 2. Row 1 links the cycles
in sets of 3 to produce 120 cycles of length 21, each containing exactly one permutation
of the form 67∗∗∗∗∗ or 76∗∗∗∗∗. Row 2 then links these cycles in sets of 5 into 24 cycles
of length 105, each containing exactly one permutation of the form 675∗∗∗∗ or 765∗∗∗∗.
Rows 3 and 4 link various sets of three cycles, permuting elements 1234, to produce 6
cycles. Finally, rows 5 and 6 break the parity barrier as discussed earlier, uniting these 6
cycles into one.


12

ALEXANDER E. HOLROYD

5. Even size
We briefly discuss a possible approach for even n. Recall that Mn is the maximum length
of a cycle Sn in which no two permutations are related by an adjacent transposition.
To get a cycle longer than Mn−1 we must use τn . But this is an odd permutation, so
we cannot remain in the alternating group An . We suggest following τn immediately by
another odd generator, say τn−2 , in order to return to An (note that τ2 is forbidden). In
order to include permutations of the form [. . . , j] for every j ∈ [n], we need to perform
such a transition (at least) n times in total in our cycle. In the ith transition we visit one
odd permutation, αi say, between the generators τn and τn−2 . For the remainder of the
cycle we propose using only generators τk for odd k, so that we remain in An .
In fact, one may even try to fix the permutations α1 , . . . , αn in advance. The problem
then reduces to that of finding long self-avoiding directed paths in An−1 , with specified start
and end vertices, and avoiding certain vertices – those that would result in a permutation
that is related to some αi by an elementary transposition. Since there are n αi ’s and n − 1
elementary transpositions, there are O(n2 ) vertices to be avoided in total.
Since, for large n, the number of vertices to be avoided is much smaller than |An−1 |, we
think it very likely that paths of length (1 − o(1))|An−1| exist, which would give Mn ≥
(1 − o(1))n!/2 as n → ∞. It is even plausible that Mn ≥ n!/2 − O(n2 ) might be achievable.
The graph An−1 seems to have a high degree of global connectivity, as evidenced by the
diverse constructions of cycles of close to optimal length in [9, 24, 25]. For a specific
approach (perhaps among others), one might start with a short path linking the required
start and end vertices, and then try to successively link in short cycles (say those that use a
single generator such as τn−1 ) in the manner of Figure 1, leaving out the relatively few short
cycles that contain forbidden vertices. It is conceivable that the forbidden permutations
might conspire to prevent such an approach, for example by blocking even short paths
between the start and end vertices. However, this appears unlikely, especially given the
additional flexibility in the choice of α1 , . . . , αn .
While there appear to be no fundamental obstacles, a proof for general even n along the
above lines might be rather messy. (Of course, this does not preclude some other more
elegant approach). Instead, the approach was combined with a computer search to obtain
a cycle of length 315(= 6!/2−45) for n = 6, which is presented below, answering a question
of [9], and improving the previous record M6 ≥ 57 [9] by more than a factor of 5. The case
n = 6 is in some respects harder than larger n: the forbidden vertices form a larger fraction
of the total, and A5 has only two generators, reducing available choices. (On the other
hand, the search space is of course relatively small). Thus, this result also lends support
to the belief that Mn ≥ (1 − o(1))n!/2 as n → ∞.
The search space was reduced by quotienting the graph S6 by a group of order 3 to
obtain a Schreier graph, giving a cycle in which the sequence of generators is repeated 3
times. The cycle uses the sequence of generators (τk(i) ) where (k(i))315
i=1 is the sequence
64 55^
35^
3^
35555^
3555^
3555^
3^
35555^
35555^
3555^
35555^
3^
3555^
35555^
3^
3
3
64 555^
3^
35^
355^
3^
355^
3^
35^
3555^
35555^
3555^
3555^
3^
35555^
3555^
35555^
3^
35 .
(Here, commas are omitted, the superscript indicates that the sequence is repeated three
times, and 3’s are marked as an aid to visual clarity).

PERFECT SNAKE-IN-THE-BOX CODES

13

References
[1] H. L. Abbott and M. Katchalski. On the snake in the box problem. J. Combin. Theory
Ser. B, 45(1):13–24, 1988.
[2] J. Baylis. Error-correcting codes, a mathematical introduction. Chapman and Hall
Mathematics Series. Chapman & Hall, London, 1998.
[3] R. C. Compton and S. G. Williamson. Doubly adjacent Gray codes for the symmetric
group. Linear and Multilinear Algebra, 35(3-4):237–293, 1993.
[4] S. J. Curran and J. A. Gallian. Hamiltonian cycles and paths in Cayley graphs and
digraphs – a survey. Discrete Mathematics, 156(1):1–18, 1996.
[5] R. Duckworth and F. Stedman. Tintinnalogia, or, the art of ringing. London, 1667.
www.gutenberg.org/ebooks/18567.
[6] R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. J.
Assoc. Comput. Mach., 30(3):514–550, 1983.
[7] D. Griffiths. Twin bob plan composition of Stedman Triples: Partitioning of graphs
into Hamiltonian subgraphs. Research Report 94(37), Univ. of Sydney, School of Math.
and Stat., 1994. www.maths.usyd.edu.au/res/CompAlg/Gri/2bob-sted.html.
[8] A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215–245, 2012.
[9] M. Horovitz and T. Etzion. Constructions of snake-in-the-box codes for rank modulation. IEEE Trans. Inform. Theory, 60(11):7016–7025, 2014.
[10] A. Jiang, R. Mateescu, M. Schwartz, and J. Bruck. Rank modulation for flash memories. IEEE Trans. Inform. Theory, 55(6):2659–2673, 2009.
[11] J. R. Johnson. Universal cycles for permutations. Discrete Math., 309(17):5264–5270,
2009.
[12] M. G. Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81–93, 1938.
[13] D. E. Knuth. The art of computer programming. Vol. 4, Fasc. 2. Addison-Wesley,
Upper Saddle River, NJ, 2005. Generating all tuples and permutations.
[14] A. Mazumdar, A. Barg, and G. Zémor. Constructions of rank modulation codes. IEEE
Trans. Inform. Theory, 59(2):1018–1029, 2013.
[15] I. Pak and R. Radoičić. Hamiltonian paths in Cayley graphs. Discrete Mathematics,
309(17):5501–5508, 2009.
[16] R. A. Rankin. A campanological problem in group theory. Proc. Cambridge Philos.
Soc., 44:17–25, 1948.
[17] E. Rapaport-Strasser. Cayley color groups and Hamilton lines. Scripta Math., 24:51–
58, 1959.
[18] C. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605–629, 1997.
[19] R. G. Swan. A simple proof of Rankin’s campanological theorem. Amer. Math.
Monthly, 106(2):159–161, 1999.
[20] W. H. Thompson. A note on Grandsire Triples. Macmillan and Bowes, Cambridge,
1886. Reprinted in W. Snowdon, Grandsire, London 1905.
[21] A. T. White. Fabian Stedman: the first group theorist? Amer. Math. Monthly,
103(9):771–778, 1996.
[22] A. Williams. Hamiltonicity of the Cayley digraph on the symmetric group generated
by σ = (12 · · · n) and τ = (12), 2013. arXiv:1307.2549.

14

ALEXANDER E. HOLROYD

[23] D. Witte and J. A. Gallian. A survey: Hamiltonian cycles in Cayley graphs. Discrete
Math., 51(3):293–304, 1984.
[24] Y. Yehezkeally and M. Schwartz. Snake-in-the-box codes for rank modulation. IEEE
Trans. Inform. Theory, 58(8):5471–5483, 2012.
[25] Y. Zhang and G. Ge. Snake-in-the-box codes for rank modulation under Kendall’s
τ -metric, 2015. arXiv:1506.02740.
Alexander E. Holroyd, Microsoft Research, 1 Microsoft Way, Redmond, WA 98052,
USA
E-mail address: holroyd at microsoft.com
URL: http://research.microsoft.com/~holroyd/

