Geodesic
Circuit codes and the Snake-in-the-Box Problem
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

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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 $n9$ 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.
Keywords: snake-in-the-box, $n$-dimensional cube, combinatorics, symbolic sequences, upper and lower bounds.
Mots-clés : circuit codes 
@article{UZKU_2014_156_3_a5,
     author = {A. A. Evdokimov},
     title = {Circuit codes and the {Snake-in-the-Box} {Problem}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {55--65},
     publisher = {mathdoc},
     volume = {156},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a5/}
}
TY  - JOUR
AU  - A. A. Evdokimov
TI  - Circuit codes and the Snake-in-the-Box Problem
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2014
SP  - 55
EP  - 65
VL  - 156
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a5/
LA  - ru
ID  - UZKU_2014_156_3_a5
ER  - 
%0 Journal Article
%A A. A. Evdokimov
%T Circuit codes and the Snake-in-the-Box Problem
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2014
%P 55-65
%V 156
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a5/
%G ru
%F UZKU_2014_156_3_a5
A. A. Evdokimov. Circuit codes and the Snake-in-the-Box Problem. 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. http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a5/