Grid designs

Dit artikel onderzoekt wanneer de randen van een compleet graaf kunnen worden ontbonden in disjuncte kopieën van roostergoten, en bewijst met behulp van eindige velden dat zulke ontbindingen bestaan voor toroidale roosters $C_n \square C_n$ (waarbij $n$ een oneven priemgetal of het kwadraat daarvan is) en voor $P_4 \square P_4$, maar niet voor $P_3 \square P_3$.

De kern

Stel je voor dat je een raadsel oplost, zoals die populaire "Connections"-puzzels in de krant. Je hebt 16 woorden, en je moet ze in vier groepjes van vier verdelen. Maar hier is de twist: in de digitale versie van deze puzzels kun je op een knop drukken om de woorden te schudden (scramble).

De auteurs van dit artikel, een groep wiskundigen, stelden zich een heel specifieke vraag: "Kunnen we deze woorden zo schudden dat, na een paar keer, elk woord precies één keer naast elk ander woord staat?"

In de wiskundetaal noemen ze dit het vinden van een "ontwerp" (design) voor een rooster. Laten we dit uitleggen met een paar simpele analogieën.

1. Het Probleem: De Dansende Woorden

Stel je een dansvloer voor met 16 mensen (de woorden).

• Normaal: Ze staan in een vierkant rooster (4 bij 4). Iedereen heeft buren: links, rechts, boven en onder.
• Het doel: Je wilt een reeks danspassen (het schudden) bedenken. Na elke danspas staan de mensen in een nieuw rooster.
• De uitdaging: Je wilt dat na een paar rondes, elke persoon precies één keer naast elke andere persoon heeft gestaan. Geen dubbele ontmoetingen, geen gemiste ontmoetingen.

Als je dit doet met een 3x3 rooster (9 woorden), blijkt het onmogelijk. Het is alsof je probeert een puzzel te leggen waarbij er altijd één stukje overblijft of twee stukken elkaar dubbel raken. De wiskundigen hebben bewezen dat dit voor een 3x3 rooster nooit lukt.

Maar voor een 4x4 rooster (16 woorden)? Dat werkt! Ze hebben bewezen dat je precies 5 keer hoeft te schudden om alle mogelijke paren te laten ontmoeten.

2. De Oplossing: Wiskunde als een Magische Sleutel

Hoe hebben ze dit bewezen? Ze gebruikten geen gissen en proberen, maar een heel krachtig wiskundig gereedschap: eindige velden (finite fields).

Stel je dit voor als een magische rekenmachine met een heel klein aantal knoppen (in dit geval 16).

• In de gewone wereld hebben we oneindig veel getallen.
• In deze magische wereld van de wiskundigen "draaien" de getallen rond. Als je bij 16 telt, kom je weer terug bij 0. Het is als een klok, maar dan met 16 uur in plaats van 12.

De auteurs gebruikten de regels van deze magische rekenmachine om een perfect patroon te ontwerpen. Ze lieten zien dat als je de woorden op een slimme manier koppelt aan deze getallen, je automatisch een perfecte volgorde krijgt.

• Voor de torus (een donut-vormig rooster): Als je een rooster hebt dat aan de randen is verbonden (zoals een video-game waar je van links afloopt en rechts weer binnenkomt), werkt dit zelfs nog beter. Ze bewezen dat dit werkt voor roosters met een grootte die een oneven priemgetal is (zoals 3, 5, 7, 9, 11...).
• Voor het gewone rooster (zoals Connections): Dit is lastiger. Voor een 4x4 rooster (16 woorden) vonden ze een oplossing. Maar voor een 3x3 rooster (9 woorden) zagen ze dat de wiskunde "in de knoop" raakt en het onmogelijk maakt.

3. Waarom is dit belangrijk?

Je zou kunnen denken: "Wie geeft er om of woorden naast elkaar staan in een puzzel?"

Het antwoord is: Wiskundige schoonheid en efficiëntie.

• De "Connections"-puzzel: De makers van de puzzel gebruiken een willekeurige generator om te schudden. De wiskundigen zeggen: "Wacht, je kunt dit veel slimmer doen!" Als je hun methode gebruikt, kun je garanderen dat je na precies 5 schudden elke mogelijke combinatie hebt gezien. Je hoeft niet te gokken of te wachten tot je geluk hebt.
• Algemene principes: Dit soort problemen komen voor in veel meer dan alleen puzzels. Denk aan het plannen van toernooien, het testen van software, of het ontwerpen van communicatienetwerken waar iedereen precies één keer met elkaar moet praten zonder dat er storingen ontstaan.

Samenvatting in één zin

Deze paper laat zien dat je met slimme wiskunde (specifiek de regels van een magische rekenmachine met 16 knoppen) kunt bewijzen dat je een 4x4 woordpuzzel precies 5 keer kunt schudden zodat elk woord precies één keer naast elk ander woord staat, maar dat dit voor een 3x3 puzzel helaas onmogelijk is.

Het is een mooi voorbeeld van hoe abstracte wiskunde (getallen die rondlopen als een klok) kan worden gebruikt om een alledaags probleem (het schudden van een puzzel) op te lossen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Scrambling Connections Puzzles with Finite Fields" van Alon Danai et al., geschreven in het Nederlands.

Titel: Scrambling Connections Puzzles met Eindige Velden

Auteurs: Alon Danai, Joshua Kou, Andy Latto, Haran Mouli, en Jim Propp
Datum: 10 maart 2026

---

1. Probleemstelling

Het artikel adresseert een probleem in de grafentheorie en combinatorisch ontwerp, geïnitieerd door de "Connections"-puzzels van de New York Times. De kernvraag is of de randen van een compleet graaf $K_N$ (waarbij $N$ het aantal elementen is) kunnen worden ontbonden in een disjuncte vereniging van subgrafen die allemaal isomorf zijn met een specifiek rooster $G$.

In de context van de puzzel:

• Er zijn $N=16$ woorden in een $4 \times 4$-rooster.
• Een "scramble" (verwarren) van het rooster creëert een nieuwe configuratie van aangrenzende woordparen.
• Het doel is om te bepalen of er een reeks van $k$ scrambles bestaat zodanig dat elk mogelijk paar woorden precies één keer aangrenzend voorkomt.
• Wiskundig vertaalt dit zich naar het zoeken naar een $G$-ontwerp (G-design): een decompositie van $K_N$ in kopieën van $G$.

De auteurs onderzoeken twee soorten roosters $G$:

1. Torus-roosters: $C_n \square C_n$ (Cartesisch product van twee cyclusgrafen).
2. Ordinaire roosters: $P_n \square P_n$ (Cartesisch product van twee padgrafen).

De specifieke motivatie is het geval $N=16$ (een $4 \times 4$-rooster), waarbij men hoopt dat$K_{16}$kan worden ontbonden in 5 kopieën van$P_4 \square P_4$(aangezien$K_{16}$120 randen heeft en$P_4 \square P_4$24 randen;$120/24 = 5$).

---

2. Methodologie

De auteurs gebruiken voornamelijk algebraïsche methoden gebaseerd op eindige velden (finite fields) om de bestaansvoorwaarden en constructies voor deze ontwerpen te bewijzen.

• Toewijzing van Velden: De vertices van de complete graaf $K_{n^2}$ worden geassocieerd met de elementen van een eindig veld $\mathbb{F}_{n^2}$ (of $\mathbb{F}_{n^4}$ voor grotere gevallen).
• Basisconstructie: Voor een veld $\mathbb{F}_q$ en een basis $\{\alpha, \beta, \dots\}$, wordt een subgraaf gedefinieerd waarbij twee vertices verbonden zijn als hun verschil gelijk is aan $\pm \alpha$ of $\pm \beta$ (of andere basisvectoren).
• Symmetrie en Cyclische Groepen: De constructies maken gebruik van de multiplicatieve groep van het eindige veld. Door een generator $x$ van de groep te gebruiken, kunnen de benodigde subgrafen gegenereerd worden door cyclische verschuivingen (vermenigvuldiging met machten van $x$).
• Combinatorische Argumentatie: Voor negatieve resultaten (waar geen ontwerp bestaat) worden combinatorische redeneringen gebruikt, zoals het analyseren van graden van vertices en de positie van specifieke vertices (bijv. het middelpunt van een rooster) in de verschillende decomposities.

---

3. Belangrijkste Resultaten en Bijdragen

A. Torus-roosters ($C_n \square C_n$)

De auteurs bewijzen dat voor specifieke waarden van $n$ een $C_n \square C_n$-ontwerp bestaat.

• Stelling 1: Als $p$ een oneven priemgetal is, kan $K_{p^2}$ worden ontbonden in $(p^2-1)/4$ kopieën van $C_p \square C_p$.
  • Constructie: Gebruikmakend van $\mathbb{F}_{p^2}$ en een primitieve kwadratische polynoom. De vertices worden verbonden op basis van verschillen $\pm \alpha, \pm \beta$ waar $\{\alpha, \beta\}$ een basis vormt.
• Stelling 2: Als $p$ een oneven priemgetal is, kan $K_{p^4}$ worden ontbonden in $(p^4-1)/4$ kopieën van $C_{p^2} \square C_{p^2}$.
  • Constructie: Gebaseerd op $\mathbb{F}_{p^4}$. Hier wordt gebruikgemaakt van een decompositie van $C_p \square C_p \square C_p \square C_p$ in Hamilton-cycli (volgens Kotzig) om de gewenste torus-structuur te vormen.

B. Ordinaire Roosters ($P_n \square P_n$)

Voor de minder symmetrische pad-roosters zijn de resultaten gemengd:

• Negatief Resultaat (Stelling 3): $K_9$ kan niet worden ontbonden in 3 kopieën van $P_3 \square P_3$.
  • Redenering: Een analyse van de graden van het middelpunt van de roosters leidt tot een contradictie. Als men aanneemt dat een decompositie bestaat, moeten de middelpunten van de drie roosters in de hoekcellen van de andere roosters vallen, wat impliceert dat deze drie punten nergens aangrenzend zijn, wat onmogelijk is in een decompositie van $K_9$.
• Positief Resultaat (Stelling 4 - Het motiverende geval): $K_{16}$ kan worden ontbonden in 5 kopieën van $P_4 \square P_4$.
  • Constructie: Dit is het centrale resultaat. De auteurs construeren een expliciet ontwerp met behulp van het veld $\mathbb{F}_{16} \cong \mathbb{F}_2[x]/(x^4+x+1)$.
  • Ze definiëren 5 subgrafen $G_i$ gebaseerd op specifieke lineaire combinaties van de basisvectoren van het veld.
  • De constructie heeft een cyclische symmetrie van orde 5: het vermenigvuldigen van alle elementen in een rooster met $x^3$ (een generator) levert het volgende rooster in de reeks op.
  • Dit bewijst dat het theoretisch mogelijk is om een Connections-puzzel zo te scramblen dat na 5 stappen elk woordpaar precies één keer aangrenzend is.

---

4. Significatie en Toepassing

• Oplossing van een Praktisch Probleem: Het artikel beantwoordt de vraag of de "Scramble"-knop in de digitale Connections-puzzel theoretisch zo geoptimaliseerd kan worden dat na slechts 5 pogingen alle mogelijke woordparen zijn gepresenteerd. Het antwoord is bevestigend, hoewel de huidige implementatie van de New York Times een pseudorandom generator gebruikt die niet garandeert dat dit optimaal gebeurt (het zou 20-30 pogingen kunnen kosten).
• Wiskundige Uitbreiding: Het werk breidt het klassieke "problème de ronde" (Lucas/Walecki) uit van paden en cycli naar Cartesische producten van deze grafen. Dit vult een gat in de literatuur over $G$-ontwerpen voor roostergrafen.
• Algebraïsche Combinatoriek: De paper demonstreert de kracht van eindige velden bij het construeren van complexe combinatorische ontwerpen die anders moeilijk te vinden zouden zijn (zoals het $P_4 \square P_4$-ontwerp, dat eerder alleen via computers zoeken door Ed Kirkby was gevonden).
• Toekomstige Richtingen: De auteurs identificeren open vragen, zoals het geval $P_7 \square P_7$ en $C_{15} \square C_{15}$, en suggereren onderzoek naar hogere dimensies ($C_n \square C_n \square \dots$) en gemengde producten ($C_m \square P_n$).

Conclusie

De auteurs hebben bewezen dat voor torus-roosters $C_n \square C_n$ met $n$ een oneven priemgetal of het kwadraat daarvan, een perfecte decompositie van de complete graaf bestaat. Voor ordinaire roosters $P_n \square P_n$ hebben ze aangetoond dat $P_3 \square P_3$ onmogelijk is, maar dat $P_4 \square P_4$ wel mogelijk is. Dit laatste resultaat biedt een algebraïsche oplossing voor het optimaliseren van woordscrambling in puzzels, waarbij de structuur van eindige velden wordt gebruikt om een perfecte afdekking van alle paren te garanderen.