Snake
المؤلف:
Abbott, H. L. and Katchalski, M
المصدر:
"On the Snake in the Box Problem." J. Combin. Th. Ser. B 44
الجزء والصفحة:
...
13-5-2022
1267
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
