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

Technische Samenvatting: Een Census van Nieuwe Snake-in-the-Box Records

Probleemdefinitie
Het artikel behandelt het "snake-in-the-box"-probleem, oorspronkelijk geformuleerd door Kautz in 1958 in de context van foutdetecterende codes. Het probleem zoekt naar het langste geïnduceerde (chordloze) pad, een "snake" genoemd, binnen de hyperkubusgraaf $Q_n$. In $Q_n$ representeren vertices binaire strings van lengte $n$, en edges verbinden strings die in precies één coördinaat verschillen. Een snake wordt gedefinieerd als een sequentie van onderscheidende vertices waarbij opeenvolgende vertices aangrenzend zijn, en geen twee niet-consequente vertices aangrenzend zijn. De maximale lengte van een dergelijk pad wordt aangeduid met $a(n)$.

Het artikel beschouwt ook gerelateerde structuren: "coils" (geïnduceerde cycli in $Q_n$) met maximale lengte $b(n)$, en "symmetric coils" (coils waarbij de tweede helft van de cyclus de eerste helft spiegelt via een vaste XOR-operatie), met maximale lengte $c(n)$. Terwijl exacte waarden voor $a(n)$ en $b(n)$ bekend zijn voor dimensies $n \le 8$, en $c(n)$ bekend is voor $n \le 7$, blijft het probleem onopgelost voor $n \ge 9$ (en $n \ge 8$ voor symmetrische coils), waarbij alleen ondergrenzen zijn vastgesteld via diverse computationele zoektochten.

Methodologie en Benadering
De auteurs maken gebruik van aanhoudende computationele inspanningen om naar langere snakes, coils en symmetrische coils te zoeken in dimensies 9 tot en met 13. De tekst details geen specifieke nieuwe algoritmische architectuur, maar positioneert het werk als een vooruitgang ten opzichte van eerdere methoden, die onder meer genetische algoritmen, populatiegebaseerde evolutionaire zoektochten, permutatiegebaseerde constructies en Monte-Carlo boomzoektochten hebben omvatten.

De benadering van de auteurs richt zich op het genereren en verifiëren van record-lengte paden. Zij maken gebruik van een standaard notatie waarbij een snake wordt gerepresenteerd door een transitie-sequentie — de geordende lijst van 0-geïndexeerde coördinaatindices die langs het pad worden omgeklapt. Om de geldigheid van hun bevindingen te waarborgen, verstrekken de auteurs een computer-verifieerbare dataset. Zij voeren ook een census uit van de oplossingsruimte, waarbij het aantal inequivalente snakes wordt geteld bij record-lengtes. Equivalentie wordt bepaald door de symmetrieën van $Q_n$, die $n!$ coördinaatpermutaties, $2^n$ translaties (XORing) en padreversie omvatten.

Belangrijkste Bijdragen en Resultaten
De primaire bijdrage van het artikel is de vaststelling van nieuwe ondergrenzen voor $a(n)$, $b(n)$ en $c(n)$ in dimensies 9 tot en met 13, die alle eerder bekende records overtreffen.

• Snake Lengtes ($a(n)$): De auteurs presenteren snakes die langer zijn dan de eerder bekende best-known in elke dimensie van 9 tot en met 13.

  • $n=9$: Een nieuwe lengte van 191 (verbetering van de vorige 190). De auteurs identificeerden 1.311 inequivalente snakes van deze lengte.
  • $n=10$: Een nieuwe lengte van 379 (verbetering van de vorige 376).
  • $n=11$: Een nieuwe lengte van 746 (verbetering van de vorige 737).
  • $n=12$: Een nieuwe lengte van 1.476 (verbetering van de vorige 1.465).
  • $n=13$: Een nieuwe lengte van 2.922 (verbetering van de vorige 2.900).
  • De verbeteringen variëren van +1 tot +22 ten opzichte van de vorige records.

• Coil Lengtes ($b(n)$): Het artikel rapporteert verbeterde ondergrenzen voor de langste coils in dimensies 9, 10 en 11, met nieuwe lengtes van respectievelijk 192, 374 en 732.

• Symmetric Coil Lengtes ($c(n)$): Verbeterde ondergrenzen worden geboden voor dimensies 10 en 11, met nieuwe lengtes van 370 en 726.

De auteurs bieden een concreet voorbeeld van een lengte-191 snake in $Q_9$, waarbij de volledige transitie-sequentie wordt vermeld. Zij merken op dat, onder miljoenen gesamplede lengte-191 snakes, exact 131 symmetrieklassen werden gevonden voor $n=9$, wat leidde tot een conjectuur dat er geen andere klassen bestaan, hoewel zij geen dergelijke volledigheidsclaim maken voor $n \ge 10$.

Significantie en Claims
Het artikel claimt significantie primair door de empirische vooruitgang van de bekende grenzen voor het snake-in-the-box-probleem. Door snakes te bieden die strikt langer zijn dan enige eerder bekende in dimensies 9 tot en met 13, hebben de auteurs de ondergrenzen op de maximale mogelijke lengte van geïnduceerde paden in hyperkubussen aangescherpt.

Het werk dient als een "census" van deze nieuwe records en biedt een uitgebreide dataset die ook de specifieke transitie-sequenties bevat voor alle onderscheidende record-lengte snakes die zijn gevonden. Deze dataset wordt in een computer-verifieerbaar formaat publiekelijk beschikbaar gesteld, waardoor onafhankelijke verificatie van de resultaten mogelijk is. De auteurs kaderen hun werk als een voortzetting van de computationele lijn gevestigd door eerdere onderzoekers (zoals Ace, Echols, Meyerson en anderen), waarbij zij de grens van wat computationeel haalbaar is in dit combinatorische optimalisatieprobleem verleggen, zonder te beweren dat zij het probleem voor deze dimensies hebben opgelost of de optimaliteit van hun nieuwe grenzen hebben bewezen.