Longer snake paths and better asymptotic bounds found in hypercubes
Constructing longer snakes and improved asymptotic bounds in hypercubes
Discrete Mathematics
Summary
This paper deals with the problem of finding very long paths called snakes inside hypercubes, a type of high-dimensional network structure. Longer snakes mean better lower bounds on how long such paths can be in larger hypercubes. The authors present new snakes that exceed previous length records in dimensions 13 to 20, and then use them to prove improved general lower bounds for any dimension 21 or higher. Their approach involves combining multiple paths with careful overlaps to build even longer ones without shortcuts.
What this means in practice
- •For network designers: Design fault-tolerant routing schemes that exploit long snake paths to avoid errors in hypercube-like network topologies.
- •For error correction engineers: Improve code constructions inspired by snake-in-the-box codes for detecting and correcting errors in communication systems.
A theory result. No direct application yet.
Authors
Tom Taylor
Abstract
We give snakes that are longer than the previous best known in dimensions 13 through 20 and improve the general lower bound for every dimension $d \geq 21$. Our explicit snakes reach 371,711 edges in dimension 20. Twenty compatible paths in that cube allow generalisation to give snakes of length at least $(17/48)2^d$ for every $d \geq 21$. Their controlled overlaps allow copies to be joined across the layers of a larger cube without creating shortcuts. Four additional paths give the same bound for coils. We explain the construction, prove the joining rule, and then count its length. The finite paths and their required intersections are independently verifiable.