A Census of New Snake-in-the-Box Records
2026-07-16 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors studied a math puzzle called the snake-in-the-box problem, which looks for the longest 'snake' path without shortcuts inside a special network called a hypercube. For smaller cases (up to dimension 8), the best answers were known, but the authors found longer snakes for dimensions 9 through 13. This means they improved the known minimum length the longest snakes can have. They also shared their results in a way that others can check with computers.
snake-in-the-box problemhypercube graphinduced pathchordless pathdimensionlongest path problemgraph theorylower boundcomputer verification
Authors
Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov
Abstract
The snake-in-the-box problem, introduced by Kautz in 1958, asks for the longest induced (chordless) path, called a snake, in the hypercube graph $Q_n$. The maximum length $a(n)$ is known in each dimension $n \leq 8$. We give snakes that are longer than the previous best-known in every dimension from $9$ to $13$, improving the lower bound on $a(n)$. All record-length paths are provided in a computer-verifiable dataset.