Circuit codes and the Snake-in-the-Box Problem

A. A. Evdokimov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 55-65

Résumé

The article is based on the materials of the plenary talk “Circuit Codes and the Snake-in-the-Box Problem: Modern State, Generalizations, and Applications” presented at the XVII International Conference “Problems of Theoretical Cybernetics”, Kazan Federal University, June, 2014. In this paper we discuss the current state of research on this well-known combinatorial problem and its generalizations. A survey on the lower and upper bounds for the maximal length of a snake and a cycle in the $n$-dimensional Boolean cube is given. We compare the known methods for construction of snakes and the upper bounds for their lengths. A table of strict values of the maximal lengths for $n<9$ and the bounds for $n=10,11$ and $12$ is presented. A simple construction for a snake of length $\mathrm{const}\cdot2^n$ with $\mathrm{const}>0.26$ is given. We analyze the properties of the constructions which influence the value of the constant. A survey of the results on circuit codes (that are generalizations of snakes) is given. Several unsolved tasks are considered.

Détail

Keywords: snake-in-the-box, $n$-dimensional cube, combinatorics, symbolic sequences, upper and lower bounds.
Mots-clés : circuit codes

Bibliographie

[1] Kautz W. H., “Unit-distance error-checking codes”, IRE Trans. Electron. Comp., EC-7:2 (1958), 179–180 | DOI

[2] Zhuravlev Yu. I., “Teoretiko-mnozhestvennye metody v algebre logiki”, Problemy kibernetiki, 8, Fizmatlit, M., 1962, 5–44

[3] Klee V., “What is the maximum length of a $d$-dimensional snake?”, Am. Math. Monthly, 77:1 (1970), 63–65 | DOI

[4] Vasilev Yu. L., “O dline tsikla v $n$-mernom edinichnom kube”, Dokl. AN SSSR, 148:4 (1963), 753–756 | MR | Zbl

[5] Danzer L., Klee V., “Length of snakes in boxes”, J. Combin. Theory, 2 (1967), 258–265 | DOI | MR | Zbl

[6] Evdokimov A. A., “O maksimalnoi dline tsepi v edinichnom $n$-mernom kube”, Matem. zametki, 6:3 (1969), 309–319 | MR | Zbl

[7] Evdokimov A. A., O maksimalnoi dline tsepi v $n$-mernom edinichnom kube i nekotorykh rodstvennykh zadachakh, Dis. $\dots$ kand. fiz.-matem. nauk, Novosibirsk, 1971, 60 pp.

[8] S. V. Yablonskii, O. B. Lupanov (red.), Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. I, Nauka, M., 1974, 313 pp. | Zbl

[9] Abbott H., Katchalski M., “On the snake in the box problem”, J. Combin. Theory Ser. B, 45:1 (1988), 13–24 | DOI | MR | Zbl

[10] Abbott H., Katchalski M., “On the construction of snake-in-the-box codes”, Utilitas Math., 40 (1991), 97–116 | MR | Zbl

[11] Wojciechowski J., “A new lower bound for snake-in-the-box codes”, Combinatorica, 9:1 (1989), 91–99 | DOI | MR | Zbl

[12] Evdokimov A. A., “Vlozhenie tsepei i tsiklov v giperkub. I”, Metody diskretnogo analiza v reshenii ekstremalnykh zadach, 50, In-t matematiki SO AN SSSR, Novosibirsk, 1990, 10–25 | MR

[13] Evdokimov A. A., “O numeratsii podmnozhestv konechnogo mnozhestva”, Metody diskretnogo analiza v reshenii kombinatornykh zadach, 34, In-t matematiki SO AN SSSR, Novosibirsk, 1980, 8–26 | MR

[14] Glagolev V. V., Evdokimov A. A., “O minimalnoi raskraske odnogo beskonechnogo grafa”, Diskretnyi analiz, 17, In-t matematiki SO AN SSSR, Novosibirsk, 1970, 9–17 | MR

[15] Evdokimov A. A., Perezhogin A. L., “Upravlyayuschie simvolnye posledovatelnosti v alfavite naimenshei moschnosti”, Materialy konf. “Diskretnyi analiz i issledovanie operatsii”, Izd-vo IM SO RAN, Novosibirsk, 2004, 84

[16] Wagner A. S., Embeedding Treesin the Hypercube, Ph. D. Diss., University of Toronto, Toronto, 1987, 118 pp.

[17] Deza M. M., Laurent M., Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer-Verlag, Berlin, 1997, 587 pp. | DOI | MR | Zbl

[18] Glagolev V. V., “Verkhnyaya otsenka dliny tsikla v $n$-mernom edinichnom kube”, Diskretnyi analiz, 6, In-t matematiki SO AN SSSR, Novosibirsk, 1966, 3–7 | MR

[19] Larman D. G., “On the right lower circular density of two-dimensional Jordan curves in the plane”, Math. Proc. Cambridge Phil. Soc., 64:1 (1968), 67–70 | DOI | MR | Zbl

[20] Douglas R. J., “Upper bounds on the length of circuits of even spread in the $d$-cube”, J. Combin. Theor., 7 (1969), 206–214 | DOI | MR | Zbl

[21] Zemor G., “An upper bound on the size of the snake-in-the-box”, Combinatorica, 17:2 (1997), 287–298 | DOI | MR | Zbl

[22] Deimer K., “Anew upper bound for the length of snakes”, Combinatorica, 5:2 (1985), 109–120 | DOI | MR | Zbl

[23] Solov'jeva F. I., “An upper bound for the length of a cycle in an $n$-dimensional unit cube”, Diskretnyi Analiz, 45, 1987, 71–76 (in Russian) | MR

[24] Snevily H. S., “The snake-in-the-box problem: A new upper bound”, Discrete Math., 133:1–3 (1994), 307–314 | DOI | MR | Zbl

[25] Emelyanov P. G., “O verkhnei otsenke dliny zmei v edinichnom $n$-mernom kube”, Diskretnyi analiz i issled. operatsii, 2:3 (1995), 10–17 | MR | Zbl

[26] Lukito A., van Zanten A. J., “A new non-asymptotic upper bound for snake-in-the-box codes”, J. Combin. Math. Combin. Comput., 39 (2001), 147–156 | MR | Zbl

[27] Korshunov A. D., “O verkhnei otsenke dliny “zmei” v $n$-mernom bulevom kube”, Materialy XIII Mezhdunar. konf. “Problemy teoreticheskoi kibernetiki”, Ch. I, Izd-vo tsentra prikl. issled. pri mekh.-matem. fak. MGU, M., 2002, 96–97

[28] Evdokimov A. A., Malyugin S. A., “Kod “zmeya v yaschike” i puti v reshetke na tore”, Matematika segodnya, Vischa shk., Kiev, 1987, 108–116 | MR

[29] Singleton R. C., “Generalized snake-in-the-box codes”, IEEE Trans. Electron. Comp., EC-15:4 (1966), 596–602 | DOI

[30] Leontev V. K., “O nekotorykh kombinatornykh zadachakh teoretiko-chislovogo soderzhaniya”, Matem. zametki, 86:3 (2009), 402–407 | DOI | MR | Zbl

[31] Kurlyandchik Ya. M., “O logarifmicheskoi asimptotike dliny maksimalnogo tsikla razbrosa $r>2$”, Diskretnyi analiz, 19, In-t matematiki SO AN SSSR, Novosibirsk, 1971, 48–55

[32] Evdokimov A. A., “Tsepnye kody s proizvolnym rasstoyaniem”, Dokl. AN SSSR, 228:6 (1976), 1273–1276 | MR | Zbl

[33] Korshunov A. D., “Nekotorye nereshennye zadachi diskretnoi matematiki i matematicheskoi kibernetiki”, Usp. matem. nauk, 64:5(389) (2009), 3–20 | DOI | MR | Zbl

[34] Kochut K. J., “Snake-in-the-box codes for dimension 7”, J. Combin. Math. Combin. Comput., 20 (1996), 175–185 | MR | Zbl

[35] Klee V., “A method for constructing circuit codes”, Journal of the ACM, 14:3 (1967), 520–528 | DOI | MR | Zbl

[36] Preparata F. P., Nievergelt J., “Difference-preserving codes”, IEEE Trans. Info. Theory, IT-20:5 (1974), 643–649 | DOI | MR | Zbl