A Census of New Snake-in-the-Box Records
This incremental advance provides new lower bounds for a classic combinatorial problem, benefiting researchers in graph theory and related fields.
The authors improved the lower bounds on the maximum length of induced paths (snakes) in hypercube graphs for dimensions 9 through 13, surpassing previous best-known lengths with new record-length paths provided in a verifiable dataset.
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.