JACODESMATH / ISSN 2148-838X
J. Algebra Comb. Discrete Appl.
2(1) • 17-24
Received: 21 August 2014; Accepted: 21 November 2014
DOI 10.13069/jacodesmath.15518
Journal of Algebra Combinatorics Discrete Structures and Applications
Maximal induced paths and minimal percolating sets in
hypercubes
Research Article
Anil M. Shende∗
Roanoke College
Abstract: For a graph G, the r-bootstrap percolation process can be described as follows: Start with an initial
set A of "infected” vertices. Infect any vertex with at least r infected neighbours, and continue this
process until no new vertices can be infected. A is said to percolate in G if eventually all the vertices
of G are infected. A is a minimal percolating set in G if A percolates in G and no proper subset of A
percolates in G.
An induced path, P , in a hypercube Qn is maximal if no induced path in Qn properly contains P.
Induced paths in hypercubes are also called snakes.
We study the relationship between maximal snakes and minimal percolating sets (under 2-bootstrap
percolation) in hypercubes. In particular, we show that every maximal snake contains a minimal
percolating set, and that every minimal percolating set is contained in a maximal snake.
2010 MSC: 05C38, 68R10
Keywords: Hypercubes, Induced paths, Percolating sets
1. Introduction
The problem of finding longest induced paths (often called snakes in the literature) in hypercubes has
been studied since 1958 [5]. Definite values for the lengths of longest snakes in n-dimensional hypercubes
are known only for dimensions n ≤ 7 [1]. Several properties of maximal snakes have been found useful in
establishing better bounds on the lengths of longest snakes in hypercubes [1, 2].
The notion of r-bootstrap percolation in graphs has been studied since 1979 [3]. Riedl considers
the 2-bootstrap percolation process in hypercubes; in particular, he studies minimal percolating sets
(under 2-bootstrap percolation) in hypercubes and provides an expression for the size of largest minimal
percolating sets in hypercubes [4].
In this paper we show the relationship between maximal snakes and minimal percolating sets (under
2-bootstrap percolation) in hypercubes. In particular we show that every maximal snake contains a
minimal percolating set, and that every minimal percolating set is contained in a maximal snake.
∗ E-mail: shende@roanoke.edu
17
Minimal percolating sets in hypercubes
2. Notation
Most of the definitions and notation in this section are directly from [2] and [4].
We will label the vertices of an n-dimensional hypercube, Qn = (Vn, E) by the 2n distinct n-bit
labels such that the labels on two vertices differ in exactly one bit position if and only if the two vertices
are neighbours in Qn. The rightmost bit in a label will be called bit number 0 and the leftmost bit will
be called bit number (n−1). [n] denotes the set {0, . . . , n−1}. For any vertex v ∈ Vn, for each i ∈ [n],
(v)i will denote the bit in bit number i of the label for v. For each i ∈ [n], lni denotes the label that
has all zeroes except a 1 as bit number i. 0n denotes the label with all zeroes. Un will denote the set
{lni | i ∈ [n]}, i.e., the set of all vertices at unit distance from 0
n. For a bit b in a label, b will denote the
bit complement of b. We will use an asterisk to denote a wildcard in labels. A sequence of k asterisks in a
label will be denoted by (∗)k. Thus an n-bit label with one asterisk denotes two vertices; moreover, these
two vertices are adjacent, i.e., they are a 1-subcube of Qn. In general, for each k, 0 ≤ k ≤ n, a label with
k asterisks denotes a k-dimensional subcube. For example, the label (∗)201 is a 2-dimensional subcube
of Q4 such that all the vertices in the subcube have 1 for bit number 0 and 0 for bit number 1. For a
subcube S of Qn, dim(S) will denote the dimension of S. When vertices u and v differ in bit position
d, we will denote this as u
d←→ v. For any two vertices x, y ∈ Qn, Ham(u, v) denotes the Hamming
distance between x and y.
For a path P = v0, v1, . . . , vl, P̂ will denote the path v1, . . . , vl−1, i.e., the path P without its
endpoints. For a path P , we will use P to denote the sequence of vertices as well as the set of vertices.
An n-snake is an induced path in the n-dimensional, hypercubical, undirected graph. A maximal
n-snake, P , is an n-snake such that no other n-snake properly contains P .
The r-bootstrap percolation process in G = (V, E) is described as follows: Let A ⊆ V be a set of
“infected” vertices. Let A0 = A. Then, let At be the set of vertices in At−1 union the set of vertices
which have at least r neighbours in At−1. The set 〈A〉 = ∪iAi is the set of vertices infected by A. A set
A is said to percolate in G if 〈A〉 = V . A percolating set A is said to be minimal if for all v ∈ A, A\v
does not percolate in G.
In the case r = 2 and G = Qn = (Vn, E), the progress of the percolation process can be described
as follows: Given a set A ⊆ Vn, let A0 =
⋃
u∈A{ {u} }, i.e., the set of all the 0-subcubes represented by
the vertices in A. Then, choose a sequence of sets of subcubes A1, A2, . . . , Ak so that At is identical to
At−1 except that two subcubes B, C ∈ At−1 that are within distance 2, in Qn, of each other are replaced
by the subcube 〈B ∪ C〉, and so that Ak is a set of subcubes all of which are distance at least 3, in Qn,
from each other. Clearly, then, A percolates in Qn if Ak = {Vn}. A0, . . . , Ak is called an execution path
of the percolation process. In the rest of the paper, unless specified otherwise, “distance” will refer to
“distance in Qn”, and by “percolating” we will mean 2-percolating.
3. Maximal snakes percolate
Theorem 3.1. Every maximal n-snake is a percolating set.
Proof. The set of maximal n-snakes that have 0n as one of the end points, and ln0 as the next vertex
is equal to the set of all maximal n-snakes up to isomorphism [2]. Thus, without loss of generality, let P
be a maximal n-snake v0, v1, . . . , vk where v0 = 0n and v1 = ln0 . Since the snake is maximal, none of the
vertices lni , 1 ≤ i < n are on the snake (since 0
n is an end point of the snake and ln0 is on the snake), and
each of these vertices has at least two neighbours on the snake. (If not, then the snake could have been
extended from 0n and thus would not be maximal.) Thus, if all the vertices of the snake are infected,
then in one percolation step, each of the vertices, lni , 1 ≤ i < n, gets infected. Thus, each vertex in the
set Un = {lni | 0 ≤ i < n} is infected. By Proposition 7 in [4], U
n is a minimal percolating set in Qn for
n ≥ 2. Thus, every maximal n-snake is a percolating set.
18
A. M. Shende
4. Minimal percolating sets and snakes
Lemma 4.1. Suppose P = v0, v1, . . . , vl is an n-snake. Then, G′ = (Qn\P̂) is connected.
Proof. Let d1, d2, . . . , dl ∈ [n] such that for each i, 1 ≤ i ≤ l, vi−1
di←→ vi. Let NP (vi) be defined as:
NP (vi) = {u | u 6∈ P and Ham(u, vi) = 1 and (∀j ∈ [i])Ham(u, vj) > 1}.
It suffices to show that for each vertex u at distance 1 from P , there is a path in G′ from v0 to u,
i.e., for each i ∈ [l], for each vertex u in NP (vi), there is a path in G′ from v0 to u. (To show that there
is a path in G′ from vl to u, we can reverse the labeling of vertices on P and apply the argument below.)
We will use mathematical induction on i.
Base Case : i = 0. Every vertex in NP (v0) is a neighbour of v0, and thus the claim is trivially true.
Induction Hypothesis : For some k ∈ [n], for all k′, 0 ≤ k′ ≤ k, for each vertex u in NP (vk′), there is
a path in G′ from v0 to u.
To show that : For each vertex u in NP (vk+1), there is a path in G′ from v0 to u.
Let u′ be the vertex such that u
dk+1←→ u′. Clearly, then, u′ is a neighbour of vk, and u′ 6∈ P by
the definition of NP . (If u′ ∈ P , then, since P is an induced path, u′ = vk−1, a neighbour of
u, contradicting u ∈ NP (vk+1).) Thus, for some k′ ≤ k, u′ ∈ NP (v′k). Then, by the induction
hypothesis there is a path in G′ from v0 to u′ and thus, there is a path in G′ from v0 to u.
As a corollary of the above result we have
Corollary 1. Suppose P = v0, v1, . . . , vl is an n-snake. Then for each vertex w ∈ Vn\P , there exist
n-snakes, P1 and P2, in Qn\P̂ such that P1 has end points v0 and w, and P2 has end points vl and w.
Lemma 4.2. Every set A ⊆ Vn that is isomorphic to Un is contained in an n-snake, and both the end
points of the snake are in A.
Proof. For each i 6= j ∈ [n], let lnij denote the n-bit label that has ones in bit positions i and j and
zeroes everywhere else. Then, consider the path defined by the sequence of vertices
ln0 , l
n
01, l
n
1 , l
n
12, . . . , l
n
(n−2), l
n
(n−2)(n−1), l
n
(n−1)
It can easily be verified that this path is an n-snake. Moreover, Un is contained in this path and both
the end points of the path are in Un.
Lemma 4.3. Let A ⊆ Vn be a minimal percolating set in Qn such that A = B ∪ C where 〈B〉 = Qn−1
and C = {u} such that u 6∈ 〈B〉. Suppose P is a snake in 〈B〉 such that P contains each vertex in B,
and both the end points of P are in B. Then, there is a snake P ′ in Qn that contains each vertex in A,
and both the end points of P ′ are in A.
Proof. Suppose P = v0, v1, . . . , vk. We consider the two cases: u is at distance 1 in Qn from P , and u
is at distance greater than 1 in Qn from P .
Case 1 Suppose u is at distance 1 in Qn from P . Since u 6∈ 〈B〉, u is a neighbour of at most one vertex
in P .
19
Minimal percolating sets in hypercubes
If u is a neighbour of one of the two end points, say v0, of P, then P ′ is simply P extended by the
edge (v0, u). Clearly, P ′ is a snake in Qn that contains each vertex of A, and both the end points
of P ′ are in A.
Suppose u is a neighbour of an internal vertex vi in P, and vi
d←→ u. There are two cases to
consider: vi ∈ B and vi 6∈ B.
vi ∈ B Then, by the minimality of A, vi−1 6∈ A and vi+1 6∈ A. Since vi−1 6∈ A, it is not an end
point of P . Then, consider the vertices u1 and u2 such that vi−1
d←→ u1 and vi−2
d←→ u2.
(Note that vi−2 exists since vi−1 is not an end point of P .) u1 and u2 are not in 〈B〉, u1 is a
neighbour of u and u2 is a neighbour of u1. Let P ′ be the path P with the edges (vi−2, vi−1)
and (vi−1, vi) replaced by the path vi−2, u2, u1, u, vi. Then, P ′ is a snake in Qn that contains
each vertex of A, and both the end points of P ′ are in A.
vi 6∈ B Consider the vertices u1 and u2 such that vi−1
d←→ u1 and vi+1
d←→ u2. u1 and u2 are not
in 〈B〉, u1 is a neighbour of u and u2 is a neighbour of u, and u1 and u2 are not neighbours
(since they are neighbours, along the same direction d, of two vertices at distance 2 in P ,
and P is a snake). Let P ′ be the path P with the path vi−1, vi, vi+1 replaced by the path
vi−1, u1, u, u2, vi+1. Then, P ′ is a snake in Qn that contains each vertex of A, and both the
end points of P ′ are in A.
Case 2 Suppose u is at distance greater than 1 in Qn from P . Since 〈B〉 = Qn−1, there is one bit position
that has the same value for the labels on all the vertices in 〈B〉. Without loss of generality, let bit
position 0 for the labels on each vertex in 〈B〉 be 0. Let u′ be the vertex such that u 0←→ u′. Since
u 6∈ 〈B〉, u′ ∈ 〈B〉, and u′ 6∈ P . Then, by Corollary 1 there is a snake (vl =)w′0, w′1, . . . w′m(= u′)
in 〈B〉\P̂ . For each i, 0 ≤ i ≤ m, let wi be the vertex such that wi
0←→ w′i. Then, P
′ =
v0, . . . , vl, w0, w1, . . . , wm(= u) is a snake in Qn that contains each vertex of A, and both the end
points of P ′ are in A.
Lemma 4.4. Let A ⊆ Vn be a minimal percolating set in Qn such that A = B ∪ C where 〈B〉 = Qn−2
and C = {u} such that u 6∈ 〈B〉, and u is at distance 2 in Qn from 〈B〉. Suppose P is a snake in 〈B〉
such that P contains each vertex in B, and both the end points of P are in B. Then, there is a snake P ′
in Qn that contains each vertex in A, and both the end points of P ′ are in A.
Proof. Without loss of generality, let 〈B〉 = ∗∗ ·· · ∗ ∗00. Then, u is in the subcube ∗∗ ·· · ∗ ∗11. Let
v0 and vl be the end points of P . Consider the vertices u1 and u2 such that vl
0←→ u1 and u1
1←→ u2.
Clearly, u1 is in the subcube ∗∗ · · · ∗ ∗01, and u2 is in the subcube ∗∗ · · · ∗ ∗11. Moreover, since P is a
snake, u1 is at distance at least 2 from all the vertices in P , except vl, and u2 is at distance at least 2
in Qn from each vertex in P . Let Pu be a snake in the subcube ∗∗ · · · ∗ ∗11 from u2 to u. Clearly, each
vertex of Pu is at distance at least 2 from P . Now let P ′ be the path P extended by the edge (vl, u1),
followed by the edge (u1, u2) and then followed by Pu. It can be easily verified that P ′ is a snake in Qn,
and both the end points of P ′ are in A.
In what follows, we will use some additional notation: For a set C ⊆ [n], Qn|C denotes the subcube
bn−1 . . . b0 of Qn where for each i 6∈ C, bi is an asterisk, and for each i ∈ C, bi ∈{0, 1}.
Lemma 4.5. For n ≥ 6, suppose C, D, E ⊆ [n] such that |C| = 2, |D| = s ≥ 2, |E| = t ≥ 2, and
C, D and E are mutually exclusive. Let F = [n]\(C ∪ D ∪ E). Let P = v0, . . . , vl be a snake in the
(n − (s + 2))-dimensional subcube Qn|C∪D, characterised by the bits ci and di for i ∈ C and i ∈ D,
respectively. Then, for any vertex u in the subcube Qn|C∪D∪F , characterised by the bits ci, di, and (vl)i,
for i ∈ C, i ∈ D and i ∈ F , respectively, P can be extended to an (n − 2)-dimensional snake in the
subcube Qn|C, characterised by the bits ci for i ∈ C, with end points v0 and u.
20
A. M. Shende
(An example may help clarify the statement of the lemma. Let n = 8, C = {0, 1}, D = {2, 3} and
E = {4, 5, 6}. Thus, s = 2, t = 3 and F = {7}. Let Qn|C∪D be the subcube ∗∗∗∗ 1001. Suppose P is
a snake in this subcube with end points v0 = 00001001 and vl = 10111001. Then, for any vertex u in
the subcube 1∗∗∗0101, say the vertex 11010101, P can be extended to an (n−2)-snake in the subcube
∗∗∗∗∗∗01 such that the end points of this snake are v0 = 00001001 and u = 11010101.)
Proof. Without loss of generality, let C = {0, 1}, D = {2, . . . , s + 1} and E = {s + 2, . . . , s + t + 1}.
Then, F = {s + t + 2, . . . , n−1}. Let P = v0, . . . , vl be a snake in the subcube given by
(∗)n−(s+t+2) (∗)t bs+1 · · ·b2 b1b0,
and let u be a vertex in the subcube given by
(vl)n−1 · · ·(vl)(s+t+2) (∗)t bs+1 · · ·b2 b1b0.
Now consider the following
vl = (vl)n−1 · · ·(vl)(s+t+2) (vl)(s+t+1) · · ·(vl)(s+2) bs+1 · · ·b2 b1b0y H1
w = (vl)n−1 · · ·(vl)(s+t+2) (vl)(s+t+1) · · ·(vl)(s+2) bs+1 · · ·b2 b1b0y H2
u = (vl)n−1 · · ·(vl)(s+t+2) (u)(s+t+1) · · ·(u)(s+2) bs+1 · · ·b2 b1b0
where H1 is a shortest path between vl and w, and H2 is a shortest path between w and u. Since P
is a snake in the subcube S, each vertex vi, i < l differs from vl in at least one bit position ai where
ai 6∈ {0, . . . , (s + 1)}. Each vertex of H1, except the vertex vl, differs from vl in at least one bit position
j ∈ {0, . . . , (s + 1)}. Since s ≥ 2, the length of H1 is at least 2, and so each vertex of H2, differs from
each vertex of P in at least two bit positions. Moreover, each vertex h of H1, except w, differs from w in
at least one bit position jh 6∈ {(s + 2), . . . , (s + t + 1)}, and each vertex g of H2 differs from w in at least
one bit position jg ∈ {(s + 2), . . . , (s + t + 1)}. Thus, P concatenated with H1 concatenated with H2 is
a snake that has end points v0 and u, and is contained in the (n−2)-dimensional subcube given by
(∗)(n−(s+t+2)) (∗)t (∗)s b1b0.
The following lemma follows from the proof of Proposition 9 in [4]. Our proof is essentially the proof
from [4]; for completeness we provide the relevant parts of the proof here.
Lemma 4.6. Let A ⊆ Vn be a minimal percolating set in Qn. Then, there exists an execution path⋃
u∈A{{u}} = A0, . . . , Ak = {Vn}, where Ak−1 consists of exactly two subcubes S1 and S2 such that
dim(S1) ≥ dim(S2) and exactly one of the following is true:
C1 : dim(S1) = n−1, S2 = {v}, and v 6∈ S1.
C2 : dim(S1) = n−2 and S2 = {v} at distance 2 from S1.
C3 : dim(S1) ≤ n−4 and dim(S2) ≤ n−4, and S1 and S2 are at distance 2 from each other.
Proof. Since A percolates in Qn, for any execution path of the percolation process Ak = Vn, and
so Ak−1 must consist of exactly two subcubes, say S1 and S2, which together infect Qn. Amongst all
execution paths with dim(S1) ≥ dim(S2), choose one where dim(S1) is the largest. By minimality of A,
dim(S1) ≤ n−1. We consider the cases depending on dim(S1).
21
Minimal percolating sets in hypercubes
Case 1 dim(S1) = n−1. Then, by the minimality of A, there must be a single vertex v in A∩(Qn\S1)
such that A percolates in Qn. Thus, S2 = {v} in this case.
Case 2 dim(S1) = n − 2. By the choice of the execution path that has dim(S1) the largest possible,
there cannot be a vertex v in A∩S2 such that the distance of v from S1 is at most 1, since otherwise
S1 could be extended to a subcube of dimension n − 1. Thus, by the minimality of A, there must
be a single vertex v in A∩(Qn\S1) such that the distance of v from S1 is 2 and A percolates in Qn.
Case 3 dim(S1) = n−3. There cannot be a vertex of A∩S2 within distance 2 of S1, as this contradicts
the maximality of dim(S1) in our choice of execution path. Hence, A∩S2 is contained in a subcube
of Qn at distance 3 from S1, as the set of vertices which are at distance 3 from S1 is a subcube of
dimension (n − 3). Thus S1 and S2 are at distance (in Qn) 3 from each other, contradicting the
fact that A percolates. Hence, this case cannot occur.
Case 4 dim(S1) ≤ n−4. Then, by the maximality of dim(S1) in the choice of execution path, dim(S2) ≤
n−4. Moreover, since A percolates in Qn, S1 and S2 must be at distance 2 from each other.
Theorem 4.7. Every minimal percolating set A ⊆ Vn is contained in an n-snake.
Proof. We will use mathematical induction on the dimension n to show that every minimal percolating
set A ⊆ Vn is contained in an n-snake, and both the end points of the snake are in A.
Base cases n ≤ 3 : We will consider each of the three cases, n = 1, n = 2 and n = 3, separately.
For n = 1, it is easy to see that the only minimal percolating set is V1, and that is contained in the
unique 1-snake, and both the end points of the snake are in V1.
For n = 2, the only (up to isomorphism) minimal percolating set in Q2 is U2, and by Lemma 4.2,
this minimal percolating set is contained in a 2-snake, and both the end points of the snake are in
U2.
For n = 3, there are two (up to isomorphism) minimal percolating sets: U3 and the set
A = {000, 001, 111}. Lemma 4.2 asserts the existence of a 3-snake containing U3 and the 3-snake
000, 001, 011, 111 contains A. Moreover, in each case, both the end points of the snake are in the
minimal percolating set.
Induction Hypothesis : For some m ≥ 3, for all m′ ≤ m, every minimal percolating set A ⊆ Vm′ in
Qm′ is contained in an m′-snake, and both the end points of the snake are in A.
To show that : Every minimal percolating set A ⊆ Vm+1 in Qm+1 is contained in an (m + 1)-snake,
and both the end points of the snake are in A.
By Lemma 4.6, there exists an execution path
⋃
u∈A{u} = A0, . . . , Ak = Vm+1, where Ak−1
consists of exactly two subcubes S1 and S2 such that dim(S1) ≥ dim(S2), satisfying one of the
three mutually exclusive cases listed in the lemma. We show that in each case, A is contained in
an (m + 1)-snake. (C1, C2 and C3 refer to the three cases listed in the statement of Lemma 4.6.)
C1 In this case, by the induction hypothesis there is an m-snake in S1 that contains each vertex
in S1 ∩A, and both the end points of the snake are in S1 ∩A. Lemma 4.3 applies and asserts
that A is contained in an (m + 1)-snake, and both the end points of this snake are in A.
C2 In this case, by the induction hypothesis there is an (m − 1)-snake in S1 that contains each
vertex in S1 ∩A, and both the end points of the snake are in S1 ∩A. Lemma 4.4 applies and
asserts that A is contained in an (m + 1)-snake, and both the end points of this snake are in
A.
22
A. M. Shende
C3 In this case, there exist integers s and t such that
dim(S1) = ((m + 1)−s) ≤ ((m + 1)−4) and
dim(S2) = ((m + 1)− t) ≤ ((m + 1)−4).
Then, s ≥ 4 and t ≥ 4. Let D′, E′ ⊆ [(m+1)] such that S1 is the subcube Qn|D′, characterised
by pi for each i ∈ D′, and S2 is the subcube Qn|E′, characterised by ri for each i ∈ E′. Since
S1 and S2 are at distance 2 from each other, |D′ ∩ E′| = 2 and pi 6= ri for i ∈ (D′ ∩ E′). Let
C = D′ ∩ E′, D = D′\C, E = E′\C and F = [(m+1)]\(C ∪ D ∪ E). Clearly, then |C| = 2,
|D| = s ≥ 2, |E| = t ≥ 2, and |F| = (m + 1) − (s + t + 2). Without loss of generality, let
C = {0, 1}, D = {2, . . . , s + 1}, and E = {s + 2, . . . , s + t + 1}, and let p0 = p1 = 0 and
r0 = r1 = 1, i.e.,
S1 = (∗)(m+1)−(s+t+2) (∗)t ps+1 · · ·p2 00, and
S2 = (∗)(m+1)−(s+t+2) rs+t+1 · · ·rs+2 (∗)s 11.
By the induction hypothesis, there is an (m + 1)− (s + 2)-snake, P1 in S1 that contains each
vertex in S1 ∩A, and both the end points, say v0 and va, of P1 are in S1 ∩A, and there is an
(m + 1)−(t + 2)-snake, P2 in S2 that contains each vertex in S2 ∩A, and both the end points,
say w0 and wb, of P2 are in S2 ∩A.
By Lemma 4.5 P1 can be extended to a snake P∗1 with end points v0 and the vertex u1 given
by
u1 = (va)m . . . (va)(s+t+2) rs+t+1 · · ·rs+2 ps+1 · · ·p2 00.
Similarly, by Lemma 4.5 P2 can be extended to a snake P∗2 with end points w0 and the vertex
u2 given by
u2 = (wb)m . . . (wb)(s+t+2) rs+t+1 · · ·rs+2 ps+1 · · ·p2 11.
Now consider
u1 = (va)m . . . (va)(s+t+2) rs+t+1 · · ·rs+2 ps+1 · · ·p2 00
↓
ux = (va)m . . . (va)(s+t+2) rs+t+1 · · ·rs+2 ps+1 · · ·p2 01y P3
uy = (wb)m . . . (wb)(s+t+2) rs+t+1 · · ·rs+2 ps+1 · · ·p2 01
↓
u2 = (wb)m . . . (wb)(s+t+2) rs+t+1 · · ·rs+2 ps+1 · · ·p2 11
where P3 is a shortest path in the subcube
(∗)(m+1)−(s+t+2) rs+t+1 · · ·rs+2 ps+1 · · ·p2 01.
Each vertex of this subcube differs from P1 in at least s ≥ 2 bit positions, and differs from P2
in at least t ≥ 2 bit positions. By the reasoning of Lemma 4.5, P3 differs from P∗1 and P∗2 in
at least two bit positions. Thus, the concatenation of P∗1 with the edge (u1, ux) followed by
P3 is a snake. Similarly, the concatenation of P∗2 with the edge (u2, uy) is a snake. Moreover,
these two snakes concatenated together is a snake with end points v0 and w0, both of which
are in A.
23
Minimal percolating sets in hypercubes
5. Conclusions and open questions
As noted earlier, our interest in maximal snakes derives from properties of maximal snakes in lower
dimensions that are useful heuristics in generating long maximal snakes in higher dimensions. The
heuristics essentially seed the exhaustive search with an initial segment of the snake. Our hope is that
minimal percolating sets can prove to be better seeds and will speed up the exhaustive search somewhat.
Our intuition comes from the observation that 1) minimal pecolating set vertices are sprinkled throughout
the hypercube, and 2) at each step of the proofs above where we use a shortest path or any snake between
two vertices, we could use a suitable longest path instead.
We would also like to explore the possibility of stronger results that may characterize longest maximal
snakes in terms of minimal percolating sets. For example, we would like to consider questions such as
1. Is there a difference in the set of minimal percolating sets contained in a maximal, but not longest,
snake, and the set of minimal percolating sets contained in a longest snake?
2. In some dimensions, notably 4 and 6 of the known ones, there is a unique (up to isomorphism)
longest snake. Is there a stronger relationship between the longest snake and minimal percolating
sets in these dimensions?
References
[1] D. Kinny. A new approach to the snake-in-the-box problem., in Proceedings of the 20th European
Conference on Artificial Intelligence, ECAI-2012, 462-467, 2012.
[2] Dayanand S. Rajan and Anil M. Shende. Maximal and reversible snakes in hypercubes, in 24th Annual
Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, 1999.
[3] Eric Riedl. Largest and smallest minimal percolating sets in trees, The Electronic Journal of Combi-
natorics, 19, 2010.
[4] Eric Riedl. Largest minimal percolating sets in hypercubes under 2-bootstrap percolation, The Electronic
Journal of Combinatorics, 17, 2010.
[5] W. H. Kautz, Unit distance error checking codes, in IRE Transaction on Electronic Computers, 7,
179–180, 1958.
24
Introduction
Notation
Maximal snakes percolate
Minimal percolating sets and snakes
Conclusions and open questions
References