Skip to content
DraconiticResearch
Search Sources API
181,686 studies31 sourcesUpdated 3 min ago
PreprintarXiv licencearXiv

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

  • Kevin M. Byrnes
  • Eric T. Harley
  • Florin Spinu
Open at sourcePDFDOICite

Abstract

Let Sn denote the maximum length of a coil in the n-dimensional hypercube Qn, 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 Sn. For n≥13, we construct two analytic dual feasible solutions. Their objective values yield upper bounds on Sn, and the smaller value is the exact optimum of the parameterized LP. One dual solution results in the bound Sn≤ 2n−1 (8n(n−1)(5n−14))/(40n3−131n2+4n+136−(5n−14)⌊3n/4⌋), which improves upon the upper bounds in Lukito, Lukito-van Zanten, and Zémor for 13≤ n≤19853. The second yields the upper bound Sn≤ 2n−1( 1−1/30√(3n)+O(n−1) ), improving upon the asymptotic upper bound of Zémor. Taken together, the two bounds improve upon the upper bounds for Sn in Lukito, Lukito-van Zanten, and Zémor for every n≥13.

Related

  1. Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity
    Xin Li, Yinan Li
    arXivPreprintarXiv licenceFull textGeneral mathematicsQuantum physics & quantum informationarXiv
  2. Linear programming bounds for binary and ternary LCD Codes
    Ming-Hsuan Kang, Maosheng Xiong
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Linear Programming Bounds for Locally Recovery Codes II
    Ming-Hsuan Kang, Maosheng Xiong
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. New Upper bounds on the Mondrian Art Problem
    Thomas Garrison, Chris Seiler, Aliaksei Semchankau
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Dynamic Programming for A Linear-Gaussian Dual Control Problem
    Ying Wang, Yuchao Li, Håkan Hjalmarsson
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{byrnes2026linear,
  title = {{Linear Programming Upper Bounds for the Coil-in-the-Box Problem}},
  author = {Kevin M. Byrnes and Eric T. Harley and Florin Spinu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.36461},
  eprint = {2610.36461},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36461},
}
RIS
TY  - UNPB
TI  - Linear Programming Upper Bounds for the Coil-in-the-Box Problem
AU  - Kevin M. Byrnes
AU  - Eric T. Harley
AU  - Florin Spinu
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.36461
UR  - https://arxiv.org/abs/2610.36461
AB  - 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≥13, 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≤ 2^n−1 (8n(n−1)(5n−14))/(40n^3−131n^2+4n+136−(5n−14)⌊3n/4⌋), which improves upon the upper bounds in Lukito, Lukito-van Zanten, and Zémor for 13≤ n≤19853. The second yields the upper bound S_n≤ 2^n−1( 1−1/30√(3n)+O(n^−1) ), 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≥13.
ER  -