PaperlayerView exact revision on arXiv

Source-linked AI summary

Constructing longer snakes and improved asymptotic bounds in hypercubes

Tom Taylor

arXiv:2609.27483v1math.COcs.DM

TL;DR

Longer snakes are needed both to extend finite-dimensional records and improve bounds in higher-dimensional hypercubes. The paper constructs a reusable family of Q20 paths and joins their copies across layers; it proves a general coil-length bound of (17/48)2^d for d ≥21.

  • Problem

    The paper seeks a way to generalize beyond searched dimensions using paths whose overlaps stay controlled when copies are reused.

    Source: §3 · p. 3

  • Method

    The construction uses twenty specific Q20 paths, face projection, and a joining rule based on controlling which path pairs may reuse a tip.

    Source: §4 · p. 3, §4.1 · p. 3, §4.3 · pp. 5–6

  • Results

    For every d ≥21, the greatest coil length b(d) is at least (17/48)2^d.

    Source: §4.6 · p. 8

  • Takeaways & Limitations

    The fixed, checked path collection is the finite input for constructing snakes in every larger dimension.

    Source: §3 · p. 3, §4 · p. 3

    The optimum remains unknown, and the leading coefficient is the mean size of the twenty routes divided by 2^20.

    Source: §5 · p. 8

Abstract

from arXiv · show

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.

1 The problem and earlier work

A snake is an induced path in a hypercube, and the paper combines searches for long finite paths with a layer construction to improve bounds in higher dimensions.

1 The problem and earlier work

  • A snake is a vertex set whose induced graph is a single path, with any edge between nonconsecutive vertices called a chord or shortcut.A snake with L edges has L + 1 vertices, and exhibiting one proves a(d) ≥ L.Source: §1 · p. 1
  • Earlier work reached the leading coefficient 77/256 and used compatible paths joined in Gray-ordered layers [5; pp. 58–59].The paper also identifies computational record constructions and recent searches as part of the prior work.Source: §1 · p. 1
  • The paper extends record snakes through local iterations and repairs, then uses precisely overlapping Q20 snakes to construct longer snakes in all higher dimensions.The construction combines finite search with the layer method.Source: §1 · p. 1

2 The new bounds

The paper reports verified finite snake lengths and a general coil bound, alongside an improvement to the classical asymptotic coefficient.

2 The new bounds

  • Table 1 lists verified finite snake lengths and percentage growth over comparisons, with entries spanning dimensions 13–20.The listed comparison sources are Itty for d = 13 [4], Bernatonis for d = 14–17 [8], and Abbott–Katchalski values tabulated by Allison and Paulusma for d = 18–20 [3].Source: §2 · p. 1, Table 1 · p. 2
  • 17/48 ≈0.35417 improves the classical Abbott–Katchalski coefficient 77/256 ≈0.30078 by about 17.75%.Source: §2 · p. 2
  • For every d ≥21, the greatest coil length b(d) is at least (17/48)2^d.A coil is a cycle with no chord; removing one vertex yields a snake of length C −2, but snakes do not necessarily produce coils.Source: §2 · p. 2

3 Finding the finite paths

The paper seeks a finite family of Q20 paths with controlled overlaps, then uses verified joins and repairs to build and extend snakes.

3 Finding the finite paths

  • A lift places two paths in adjacent layers, and it forms one snake when they share exactly one vertex that is an endpoint of both.That shared endpoint supplies one joining edge, giving length L1 + L2 + 1 for paths of lengths L1 and L2.Source: §3 · p. 2
  • The iterative search flips a rarely used coordinate, repairs the second path to share only the chosen endpoint, joins the pair, and then improves the result.Failed repairs trigger retries; the process returns the longest verified snake in the highest dimension reached.Source: §3 · p. 3
  • Flipping a coordinate used q times creates exactly 2q shared vertices, while permitted bridges avoid other vertices of the first path and unwanted contacts with the second.Endpoint pivots preserve length but can expose a new extension.Source: §3 · p. 3
  • The Q12 and Q13 input paths have lengths 1,480 and 2,934 and were publicly posted by Itty; the higher-dimensional chain starts from Bernatonis paths extending an Orland et al. seed [7].Local rerouting and joining lower-dimensional snakes have precedents in Brown, Wynn and Echols [10].Source: §3 · p. 3
  • For coils, the search tries short closing paths between a snake’s endpoints, sometimes trimming a short section first.Source: §3 · p. 3
  • Controlled overlaps among a collection of Q20 paths are needed so copies can be joined across layers without unwanted edges.The paths are improved while preserving their required intersections, forming the finite input to the higher-dimensional proof.Source: §3 · p. 3

4 Generalising the construction to higher dimensions

Twenty compatible paths in Q20 are assembled across Gray-ordered layers, with controlled overlaps and tip assignments preventing shortcuts. Averaging valid constructions yields a length bound, and four additional paths extend the construction to coils.

4 Generalising the construction to higher dimensions

  • Write d = 20 + m and represent each vertex as an inner Q20 vertex paired with an outer Qm vertex; each fixed outer string defines a Q20 layer.The twenty paths are selected across the 2^m layers, and checked overlaps allow the joining rule to work in every dimension without further path search.Source: §4 · p. 3

4.1 The fixed collection of paths

  • Twenty induced paths in Q20 use two roots and five tips, with controlled intersections that determine which layer copies can be joined safely.Their average size is 371,401.2 vertices, about 35.42% of a Q20 layer; reusing paths of similar size suggests the same occupied fraction in larger cubes.Source: §4.1 · pp. 3–4

4.2 Joining copies across the layers

  • Gray ordering visits neighboring layers, but nonconsecutive neighboring layers also require checks to prevent unwanted crossings.Alternating I and O routes and choosing roots and tips according to the outer-layer positions specifies the intended joins.Source: §4.2 · pp. 4–5

4.3 Which pairs can reuse a tip

  • A proper coloring of the conflict graph H assigns tips so that the assembled path is induced.Pairs joined by an edge of H must use different tips; otherwise reusing a tip could create an extra crossing between their layers.Source: §4.3 · pp. 5–6

4.4 Why five tips suffice

  • The conflict graph H has an explicit proper coloring with five labels, allowing the construction to use its five available tips.The paper gives an arithmetic adjacency test for H and a self-contained coloring argument.Source: §4.4 · pp. 6–7

4.5 Counting the length

  • Among ten valid constructions formed by cycling tip assignments and exchanging root orders, at least one is at least as long as their average.The counting uses the twenty route sizes and rounds the resulting integer length up to prove the theorem.Source: §4.5 · pp. 7–8

4.6 Closing the construction into coils

  • For every d ≥21, b(d) ≥(17/48)2^d.Four additional verified paths to t5 satisfy the required intersection condition simultaneously with the original twenty paths, allowing the construction to close into coils.Source: §4.6 · p. 8

5 Verification and the remaining gap

The paper provides verified finite paths and a verifier, while the optimum remains unknown and the dimension-20 snake reaches 70.90% of the stated upper bound.

5 Verification and the remaining gap

  • The public repository provides twenty snake paths, four additional coil paths, expandable vertex lists, and a verifier.Source: §5 · p. 8
  • Huang’s degree argument gives an upper bound on snake length because a snake has maximum degree two.The supplied passages state a(d) ≤ 2d−1 −1 for d ≥ 5; the notation is preserved as supplied.Source: §5 · p. 8
  • An LLM coding assistant supported the search and programming under the author’s direction.Source: §5 · p. 8

A Endpoint pivots

An endpoint pivot replaces one path vertex while preserving the path length, changing which vertex can be extended. In the Q5 example, this makes a ten-edge snake possible when neither original endpoint could be extended.

A Endpoint pivots

  • The pivot deletes p_(j+1), adds an unused vertex v with exactly two prescribed neighbours, and reverses the retained suffix to form an induced path of the same length.The vertex count is unchanged, and the new endpoint is p_(j+2).Source: A Endpoint pivots · p. 10
  • Replacing 00110 with 10111 preserves nine edges and makes 01110 an endpoint, allowing 01010 to extend the snake to ten edges.Source: Figure 2 · p. 10

B Five-tip colouring

The construction inductively five-colours the conflict graph so that tips can be assigned without creating unwanted contacts. Its boundary palettes and reflection-based recolouring preserve a proper colouring at each enlargement.

B Five-tip colouring

  • The induction enlarges a block of positions from 1,…,M−1 to 1,…,2M−1, with the middle position assigned colour B.The middle’s neighbours occur at power-of-two distances, so boundary colours must leave a colour available for it.Source: B Five-tip colouring · p. 11
  • Boundary positions at distances 1, 2, 4, … use two three-colour palettes sharing exactly one colour, restoring the induction condition after each enlargement.The new palettes are {A, B, C} and {B, D, E}.Source: B Five-tip colouring · pp. 11–12
  • Reflection copies position x to 2M−x and recolours the copy by the permutation A→D, B→E, C→B, D→A, E→C.The reflected half retains its conflict pattern, while mirror positions receive different colours.Source: B Five-tip colouring · p. 11
  • Edges between halves occur only at mirror positions, and the middle’s neighbours avoid its colour, so the enlarged graph remains properly coloured.Source: B Five-tip colouring · pp. 11–12
  • The restored boundary palettes allow the construction to repeat for blocks of every required size using the same five colours.Source: B Five-tip colouring · p. 12

C The coil bound

Four additional paths support the general coil construction, which counts the assembled cycle from interior and boundary path contributions. The direct constructions for dimensions 21 through 23 each exceed the stated lower bound.

C The coil bound

  • Each direct construction for m=1, 2, 3 exceeds (17/48)2^d in its dimension.These cases retain endpoint tips and join the first and last Gray layers using distinct tips to prevent unwanted contacts.Source: C The coil bound · p. 13
  • For m≥4, the construction uses Ir0(t5) and Or1(t5), retaining t5 to provide the closing edge between the first and last Gray layers.The root rule and Lemma 1 exclude other unwanted contacts.Source: C The coil bound · p. 13
  • The cycle length is counted from (N−1)T interior-path vertices and 5S5 boundary-path vertices, with no vertices deleted.A cycle has as many edges as vertices; the supplied passage identifies d≥24 for the second line of the resulting bound.Source: C The coil bound · p. 13

D Comparison plots

The comparison-plot material is labeled “Longest recorded snakes by dimension” and includes labels for related work.

D Comparison plots

Loading 2609.27483v1…