TOPICS
Search

Coil-in-the-Box Problem

The coil-in-the-box problem asks for the longest induced cycle in the hypercube graph Q_n. A coil is an induced cycle, so two nonconsecutive vertices of the cycle cannot be adjacent in Q_n. Its length is its number of vertices (Östergård and Pettersson 2014).

Let S_n be the maximum coil length. Byrnes et al. (2026) proved

S_n<=2^(n-1)(8n(n-1)(5n-14))/(40n^3-131n^2+4n+136-(5n-14)|_3n/4_|)

for n>=13, where |_x_| is the floor function. A second linear programming bound gives

S_n<=2^(n-1)(1-1/(30sqrt(3n))+O(n^(-1))),

where O denotes big-O notation. Together the bounds improve the earlier upper bounds for every n>=13.

See also

Hypercube Graph, Induced Cycle

Explore with Wolfram|Alpha

References

Byrnes, K. M.; Harley, E. T.; and Spinu, F. "Linear Programming Upper Bounds for the Coil-in-the-Box Problem." 27 Oct 2026. https://arxiv.org/abs/2610.36461.Östergård, P. R. J. and Pettersson, V. H. "On the Maximum Length of Coil-in-the-Box Codes in Dimension 8." Disc. Appl. Math. 179, 193-200, 2014. https://doi.org/10.1016/j.dam.2014.07.010.

Cite this as:

Weisstein, Eric W. "Coil-in-the-Box Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Coil-in-the-BoxProblem.html

Subject classifications