Snake

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

(1)

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

(2)

and Snevily (1994) showed that

(3)

for , and conjectured

(4)

for . The first few values for  for , 2, ..., are 2, 4, 6, 8, 14, 26, ... (OEIS A000937).

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  in the -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 -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 -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 -Dimensional Cube." Diskret. Analiz. 45, 1987.