A Census of New Snake-in-the-Box Records

2026/07/16 by Paul Orland, Lucas Fagan, Michele Tarquini +7 · 1 voice
#cs.DM #math.CO

paper · pdf

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 ≤ 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.

Discussions

• Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov: A Census of New Snake-in-the-Box Records https://arxiv [bsky, 0 points, 0 comments]

Related

• New Bounds for the Snake-in-the-Box Problem
• Long induced paths in a configuration model
• Constructions of Snake-in-the-Box Codes for Rank Modulation
• A greedy approximation algorithm for the longest path problem in undirected graphs
• Constructing circuit codes by permuting initial sequences