TOPICS
Search

Snake

A snake is an Eulerian path in the d-hypercube that has no chords (i.e., any hypercube edge joining snake vertices is a snake edge). Klee (1970) asked for the maximum length s(d) of a d-snake. Klee (1970) gave the bounds

7/(4(d-1))<=(s(d))/(2^d)1/2-(1-12/2^(-d))/(7d(d-1)^2+2)
(1)

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

s(d)>=77·2^(d-8),
(2)

and Snevily (1994) showed that

s(d)>=2^(d-1)(1-1/(20d-41))
(3)

for d<=12, and conjectured

s(d)>=3·2^(d-3)+2
(4)

for d<=5. The first few values for s(d) for d=1, 2, ..., are 2, 4, 6, 8, 14, 26, ... (OEIS A000937).

See also

Apple Surface, Hypercube, Snake Eyes, Snake Lemma, Snake Oil Method, Snake Polyiamond

Explore with Wolfram|Alpha

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.Emelianov, P. "Snake-in-the-Box." http://mix.nsk.ru/epg/snake.html.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.Guy, R. K. "Monthly Unsolved Problems." Amer. Math. Monthly 94, 961-970, 1989.Guy, R. K. and Nowakowski, R. J. "Monthly Unsolved Problems, 1696-1995." Amer. Math. Monthly 102, 921-926, 1995.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 "The On-Line Encyclopedia of Integer Sequences."Snevily, H. S. "The Snake-in-the-Box Problem: A New Upper Bound." Disc. Math. 133, 307-314, 1994.Solov'jeva, F. I. "An Upper Bound for the Length of a Cycle in an n-Dimensional Cube." Diskret. Analiz. 45, 1987.

Referenced on Wolfram|Alpha

Snake

Cite this as:

Weisstein, Eric W. "Snake." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Snake.html

Subject classifications