No label defined (Q4501025)

A snake-in-the-box code in an \(n\)-dimensional cube \(Q_n\) is a simple cycle without chords such that vertices at cycle distance greater than 1 never have Hamming distance 1. \textit{F.~I.~Solov'eva} gave the following upper bound for the length \(s(n)\) of a longest snake in \(Q_n\): \[ s(n)\leq 2^{n-1} - \frac{2^{n-1}}{20n-41} \] for \(n\geq 12\), see [Metody Diskretn. Anal. 45, 71-76 (1987; Zbl 0707.05040)]. The best known upper bound is given by \textit{G.~Zémor} in [Combinatorica 17, No. 2, 287-298 (1997; Zbl 0886.05084)] \[ s(n)\leq 2^{n-1}\biggl(1 - \frac{1}{89\sqrt{n}}+O\Bigl(\frac{1}{n}\Bigr)\biggr). \] Combining Zémor's and Solov'eva's methods, the authors obtain a new upper bound for \(11\leq n\leq 15603\). \{No comparison is presented between the improvement obtained in the article under review and the new bounds announced by \textit{A.~Lukito} [see this volume, pp. 183-186 (1998; Zbl 0951.94016)].\}. For the entire collection see [Zbl 0918.00043].