Snake

A simple circuit in the $d$-Hypercube which has no chords (i.e., for which all snake edges are edges of the Hypercube). Klee (1970) asked for the maximum length $s(d)$ of a $d$-snake. Klee (1970) gave the bounds

$${7\over 4(d-1)}\leq {s(d)\over 2^d} {1\over 2}-{1-12/2^{-d}\over 7d(d-1)^2+2}$$ (1)

for $d\geq 6$ (Danzer and Klee 1967, Douglas 1969), as well as numerous references. Abbott and Katchalski (1988) show

$$s(d)\geq 77\cdot 2^{d-8},$$ (2)

and Snevily (1994) showed that

$$s(d)\leq 2^{d-1}\left({1-{1\over 20d-41}}\right)$$ (3)

for $d\leq 12$, and conjectured

$$s(d)\leq 3\cdot 2^{d-3}+2$$ (4)

for $d\leq 5$. The first few values for $s(d)$ for $d=1$, 2, ..., are 2, 4, 6, 8, 14, 26, ... (Sloane's A000937).

See also Hypercube

References

Abbott, H. L. and Katchalski, M. ``On the Snake in the Box Problem.'' J. Combin. Th. Ser. B 44, 12-24, 1988.

Danzer, L. and Klee, V. ``Length of Snakes in Boxes.'' J. Combin. Th. 2, 258-265, 1967.

Douglas, R. J. ``Some Results on the Maximum Length of Circuits of Spread $k$ in the $d$-Cube.'' J. Combin. Th. 6, 323-339, 1969.

Evdokimov, A. A. ``Maximal Length of a Chain in a Unit $n$-Dimensional Cube.'' Mat. Zametki 6, 309-319, 1969.

Guy, R. K. ``Unsolved Problems Come of Age.'' Amer. Math. Monthly 96, 903-909, 1989.

Kautz, W. H. ``Unit-Distance Error-Checking Codes.'' IRE Trans. Elect. Comput. 7, 177-180, 1958.

Klee, V. ``What is the Maximum Length of a $d$-Dimensional Snake?'' Amer. Math. Monthly 77, 63-65, 1970.

Sloane, N. J. A. Sequence A000937/M0995 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Snevily, H. S. ``The Snake-in-the-Box Problem: A New Upper Bound.'' Disc. Math. 133, 307-314, 1994.