Linear Programming Upper Bounds for the Coil-in-the-Box Problem

Source abstract

Let $S_n$ denote the maximum length of a coil in the $n$-dimensional hypercube $Q_n$, i.e., a simple cycle whose induced subgraph has no additional chords. We combine classical square-counting identities and structural properties of maximum coils with new valid combinatorial inequalities into a parameterized linear program whose optimal value provides an upper bound for $S_n$. For $n\ge13$, we construct two analytic dual feasible solutions. Their objective values yield upper bounds on $S_n$, and the smaller value is the exact optimum of the parameterized LP. One dual solution results in the bound $$S_n\le 2^{n-1} \frac{8n(n-1)(5n-14)} {40n^3-131n^2+4n+136-(5n-14)\lfloor3n/4\rfloor},$$ which improves upon the upper bounds in Lukito, Lukito-van Zanten, and Zémor for $13\le n\le19853$. The second yields the upper bound $$S_n\le 2^{n-1}\left( 1-\frac1{30\sqrt{3n}}+O(n^{-1}) \right),$$ improving upon the asymptotic upper bound of Zémor. Taken together, the two bounds improve upon the upper bounds for $S_n$ in Lukito, Lukito-van Zanten, and Zémor for every $n\ge13$.