|
%I #78 Oct 02 2022 10:30:02
%S 0,1,2,4,7,13,26,50,98
%N Maximum length of a simple path with no chords in the n-dimensional hypercube, also known as snake-in-the-box problem.
%C Some confusion seems to exist in the distinction between n-snakes and n-coils. Earlier papers and also A000937 used "snake" to mean a closed path, which is called n-coil in newer notation, see Harary et al. a(8) is conjectured to be 97 by Rajan and Shende. [The true value, however, is 98. See Ostergard and Ville, 2014. - _N. J. A. Sloane_, Apr 06 2014]
%C Longest open achordal path in n-dimensional hypercube.
%C After 50, lower bounds on the next terms are 97, 186, 358, 680, 1260. - Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005
%C The length of the longest known snake (open path) in dimension 8 (as of December, 2009) is 98. It was found by B. Carlson (confirmed by W. D. Potter) and soon to be reported in the literature. Numerous 97-length snakes are currently published. - W. D. Potter (potter(AT)uga.edu), Feb 24 2009
%D B. P. Carlson, D. F. Hougen: Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes. In: Proc. 12th Annu. Conf. Genetic and Evolutionary Computation, pp. 791-798 (2010). [Shows a(8) >= 98. - _N. J. A. Sloane_, Apr 06 2014]
%D D. Casella and W. D. Potter, "New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Coils". Submitted to IEEE Conference on Evolutionary Computing, 2005.
%H David Allison, Daniel Paulusma, <a href="https://arxiv.org/abs/1603.05119">New Bounds for the Snake-in-the-Box Problem</a>, arXiv:1603.05119 [math.CO], 16 Jun 2016.
%H D. A. Casella and W. D. Potter, <a href="https://www.researchgate.net/publication/221439264_New_Lower_Bounds_for_the_Snake-in-the-Box_Problem_Using_Evolutionary_Techniques_to_Hunt_for_Snakes">New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Snakes</a>, 18th International FLAIRS Conference (2005).
%H F. Harary, J. P. Hayes and H. J. Wu, <a href="https://doi.org/10.1016/0898-1221(88)90213-1">A survey of the theory of hypercube graphs</a>, Comput. Math. Applic., 15 (1988) 277-289.
%H S. Hood, D. Recoskie, J. Sawada, D. Wong, <a href="https://doi.org/10.1007/s10878-013-9630-z">Snakes, coils, and single-track circuit codes with spread k</a>, J. Combin. Optim. 30 (1) (2015) 42-62, Table 2 (lower bounds for n<=17)
%H K. J. Kochut, <a href="http://cobweb.cs.uga.edu/~potter/CompIntell/kochut.pdf">Snake-In-The-Box Codes for Dimension 7</a>, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 20, pp. 175-185, 1996.
%H Patric R. J. Östergård, Ville H. Pettersson, <a href="https://doi.org/10.1007/s00373-014-1423-3">Exhaustive Search for Snake-in-the-Box Codes</a>, Graphs and Combinatorics 31, 1019-1028 (2015), shows a(8)=98.
%H Ville Pettersson, <a href="https://aaltodoc.aalto.fi/handle/123456789/17688">Graph Algorithms for Constructing and Enumerating Cycles and Related Structures</a>, Doctoral Dissertation, 2015.
%H Potter, W. D., <a href="https://web.archive.org/web/20200217135138/http://ai1.ai.uga.edu/sib/sibwiki/doku.php/records">A list of current records for the Snake-in-the-Box problem.</a> [Archived version.]
%H Potter, W. D., R. W. Robinson, J. A. Miller, K. J. Kochut and D. Z. Redys, <a href="https://www.researchgate.net/publication/2577776_Using_The_Genetic_Algorithm_to_Find_Snake-In-The-Box_Codes">Using the Genetic Algorithm to Find Snake In The Box Codes</a>, Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, pp. 421-426, Austin, Texas, 1994.
%H Dayanand S. Rajan, Anil M. Shende, <a href="https://www.researchgate.net/publication/2525975_Maximal_and_Reversible_Snakes_in_Hypercubes">Maximal and Reversible Snakes in Hypercubes.</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Snake-in-the-box">Snake-in-the-box</a>.
%H Gilles Zémor, <a href="https://doi.org/10.1007/BF01200911">An upper bound on the size of the snake-in-the-box</a>, Combinatorica 17.2 (1997): 287-298.
%e a(3)=4: Path of a longest 3-snake starts at 000 and then visits 100 101 111 011.
%e a(4)=7: Path of a longest 4-snake: 0000 1000 1010 1110 0110 0111 0101 1101.
%e See figures 1 and 2 in Rajan-Shende.
%Y Cf. A000937 = length of maximum n-coil.
%Y Row maxima of A357499.
%K hard,more,nonn
%O 0,3
%A _Hugo Pfoertner_, Oct 11 2004
%E a(8) from Patric R. J. Östergård and V. H. Pettersson (2014). - _N. J. A. Sloane_, Apr 06 2014
%E a(0) prepended by _Pontus von Brömssen_, Oct 02 2022
| 