New Snake-in-the-Box Records via Snakepit Surgery and Learned Construction

Abstract:The snake-in-the-box problem asks for a longest induced path in the hypercube graph $Q_n$. We find a length-191 snake in dimension $n=9$, the lowest dimension where the maximum is unknown, improving the previous record of 190 that had stood for 14 years. We also establish new lower bounds in dimensions 10-13. To find these records, we introduce snakepits, collections of disjoint snakes, to expand the search space and open new routes between snakes. This motivates our new Snakepit-in-the-Box benchmark, which seeks maximal edge counts when allowing multiple components. Finally, we introduce Beam Anchor, a search-supervised learned constructor algorithm that finds 100 inequivalent length-190 snakes in dimension 9.

Updated to include detailed information about methods. 23 pages, 4 figures

Discrete Mathematics (cs.DM); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Combinatorics (math.CO)

arXiv:2607.15270 [cs.DM]

(or arXiv:2607.15270v3 [cs.DM] for this version)

https://doi.org/10.48550/arXiv.2607.15270 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.