Planar-Toroidal Decomposition of $K_{12}$

Dit artikel bewijst dat de volledige graaf $K_{12}$ niet kan worden ontbonden in een planaire en een toroidale graaf, en identificeert via een computersimulatie de 123 unieke paren van planaire en toroidale subgrafen die de maximale mogelijke randaantallen benaderen.

De kern

Het Grote Knoop-Oplossingsprobleem: Waarom 12 Punten niet in Twee Vlakke Werelden passen

Stel je voor dat je een enorme, ingewikkelde knoop hebt gemaakt met 12 punten die allemaal met elkaar verbonden zijn. In de wiskunde noemen we dit een "compleet grafiek" ($K_{12}$). De vraag die wiskundigen al decennia stellen, is: Kunnen we deze ene grote knoop opknippen in twee kleinere stukken, zodat elk stuk op een heel specifieke manier kan worden getekend zonder dat lijnen elkaar kruisen?

Laten we de regels van dit spel even uitleggen met een paar creatieve vergelijkingen:

1. De Twee Werelden: Het Vlak en de Torus

Stel je twee verschillende oppervlakken voor waarop je deze stukken mag tekenen:

• De Vlakke Wereld (Planair): Dit is als een gewoon vel papier of een platte tennisbal. Als je een lijn tekent van punt A naar punt B, mag die lijn geen andere lijn kruisen. Het is alsof je een platte kaart tekent; als twee wegen elkaar kruisen, moet er een brug of tunnel zijn, maar in deze wiskundige wereld zijn bruggen niet toegestaan. Alles moet plat liggen.
• De Torus-Wereld (Torus): Dit is een oppervlak met één gat, zoals een dons (een reep) of een zwemband. Op zo'n oppervlak kun je lijnen tekken die "rondom" gaan. Een lijn die over de rand van je vel papier zou vallen, komt aan de andere kant weer terug. Dit geeft je meer ruimte om lijnen te laten kruisen zonder dat ze echt "botsen".

2. De Uitdaging van 1978

In 1978 vroegen twee wiskundigen, Anderson en White zich af: "Is het mogelijk om die grote knoop van 12 punten zo op te knippen dat het ene stuk perfect op een vel papier past (zonder kruisingen) en het andere stuk perfect op een donut (zonder kruisingen)?"

Als dit zou lukken, zou het betekenen dat we een heel nieuw soort wiskundige structuur hebben ontdekt. Maar als het niet lukt, betekent dat dat er een fundamentele limiet is aan hoe we deze knopen kunnen verdelen.

3. Het Onderzoek: Een Digitale Schatzoeker

De auteurs van dit paper, Allan Bickle en Russell Campbell, hebben zich voorgenomen om dit mysterie op te lossen. Ze hebben twee methoden gebruikt:

• De Theoretische Sleutels: Ze hebben eerst gekeken naar de "regels van het spel". Ze berekenden hoeveel lijnen er maximaal op een vel papier passen en hoeveel op een donut. Ze keken naar de hoekpunten en de driehoekjes die erin zitten. Het was alsof ze probeerden een slot te openen door te kijken naar de vorm van de sleutel, zonder de deur daadwerkelijk open te breken. Ze ontdekten dat veel mogelijke combinaties al onmogelijk waren, maar ze konden niet bewijzen dat alle combinaties onmogelijk waren.
• De Digitale Schatzoeker (De Computer): Omdat de theorie niet genoeg was, deden ze wat moderne wiskundigen doen: ze lieten een computer het werk doen. Er zijn 7.595 unieke manieren om 12 punten op een vlakke manier te verbinden (zoals 7.595 verschillende platte puzzels).
  • De computer nam elke puzzel, keek naar het "spiegelbeeld" (de lijnen die ontbreken in de grote knoop), en probeerde dat spiegelbeeld op de donut te tekenen.
  • Het was een enorme klus. Het duurde bijna 60 dagen voor de computer om alle mogelijke combinaties te checken, zelfs als ze probeerden om twee lijntjes weg te laten om het makkelijker te maken.

4. Het Grote Nieuws: Het Is Onmogelijk!

Het resultaat? Het is onmogelijk.

Er bestaat geen enkele manier om die grote knoop van 12 punten op te knippen in één stuk dat op een vel papier past en één stuk dat op een donut past. De auteurs hebben bewezen dat als je probeert dit te doen, het stuk dat op de donut moet passen, altijd te veel lijnen heeft of de verkeerde vorm heeft.

Maar er is een kleine "maar":
Ze vonden wel 123 unieke gevallen waarin het bijna lukte. Als je in die gevallen twee extra lijntjes uit het donut-stuk verwijdert, dan kan het wel. Het is alsof je een tekening hebt die net niet in het kader past, maar als je twee hoekjes afsnijdt, past hij wel.

5. Waarom is dit belangrijk?

Je zou kunnen denken: "Oké, 12 punten op een donut. Wie geeft daar om?"

Maar dit is als het vinden van een nieuwe wet in de natuurkunde. Het helpt ons begrijpen hoe complexe netwerken (zoals het internet, sociale netwerken of circuits op een chip) kunnen worden opgebouwd.

• Het weerlegt een oude gok (een "conjecture") dat voor elke grootte van een knoop er wel een manier zou zijn om hem op te knippen in een vlak en een torus-stuk. Voor 12 punten geldt dit niet.
• Het laat zien dat er grenzen zijn aan hoe we complexe systemen kunnen verdelen over verschillende "lagen" of oppervlakken.

Kortom:
De auteurs hebben met een combinatie van slimme redenering en een enorme hoeveelheid rekenkracht bewezen dat je die specifieke 12-punten-knoop niet kunt splitsen in een "vlakke" en een "donut" versie. Het is een geslaagde zoektocht die een deur in de wiskunde dichtde, maar tegelijkertijd een raam openzette voor nieuwe vragen over hoe we complexe netwerken kunnen ontwerpen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Planar-Toroidal Decomposition of K12" van Allan Bickle en Russell Campbell, vertaald en samengevat in het Nederlands.

Titel: Planair-Toroidale Decompositie van $K_{12}$

Auteurs: Allan Bickle en Russell Campbell
Publicatie: Discrete Mathematics and Theoretical Computer Science, Vol. 28:2 #3 (2026)

---

1. Probleemstelling

Het artikel adresseert een open vraag uit de grafentheorie die voor het eerst in 1978 door Anderson en White werd gesteld: Bestaat er een decompositie van de volledige graaf $K_{12}$ in twee deelgrafen, waarbij de ene deelgraaf planair is en de andere toroidaal (op een torus in te bedden)?

Dit probleem is gerelateerd aan het bepalen van de waarde $N(\gamma, \gamma')$, gedefinieerd als de grootte van de kleinste volledige graaf die niet in twee delen kan worden opgesplitst die respectievelijk in een oppervlak met $\gamma$ handvatten en een oppervlak met $\gamma'$ handvatten in te bedden zijn.

• Het is bekend dat $N(0,0) = 9$ (planair-planair).
• Het is bekend dat $N(1,1) = 14$ (toroidaal-toroidaal).
• De vraag was of $N(0,1) = 12$ of $13$. Als$K_{12}$wel in zo'n paar zou kunnen worden opgesplitst, zou$N(0,1) > 12$ zijn.

De auteurs testen ook een conjecture van Bickle en White (2013) die stelt dat voor alle $n \geq 11$ de ondergrens voor de som van het genus van een graaf en zijn complement wordt bereikt. Voor $n=12$ impliceert deze conjecture dat een decompositie van $K_{12}$ in een planair en een toroidaal deel mogelijk zou moeten zijn.

2. Methodologie

De auteurs hanteren een hybride aanpak die theoretische argumenten combineert met een uitgebreide computergestuurde zoektocht.

A. Theoretische Benaderingen

De auteurs ontwikkelen drie theoretische filters om het zoekruimte van mogelijke planaire deelgrafen van $K_{12}$ te verkleinen. Er zijn in totaal 7595 unieke maximale planaire grafen van orde 12.

1. Vertexgraden (Degree Sequences):
   • Voor een decompositie $(G, \bar{G})$ van $K_{12}$ moet $G$ planair zijn (maximaal 30 kanten) en $\bar{G}$ toroidaal (maximaal 36 kanten). Omdat $K_{12}$ 66 kanten heeft, moeten beide deelgrafen hun maximale aantal kanten hebben.
   • Lemma's worden afgeleid over de graden van de vertices. Bijvoorbeeld, als een vertex in $G$ graad 8 heeft, moeten de drie niet-buren in $G$ een onafhankelijke set vormen in $G$ (en dus een clique vormen in $\bar{G}$).
   • Door de formule van Goodman voor het aantal driehoeken te gebruiken, kunnen bepaalde graadsequenties direct worden uitgesloten omdat ze leiden tot een onmogelijk aantal driehoeken in de complementen.
2. Aantal Driehoeken:
   • Een maximale planaire graaf van orde 12 heeft precies 20 driehoekige gebieden (triangulatie). Een toroidale triangulatie heeft 24 driehoekige gebieden.
   • Als het complement van een planaire graaf minder dan 24 niet-scheidende driehoeken heeft, kan het niet toroidaal zijn.
3. Scheidende Mengen (Separating Sets):
   • De auteurs analyseren de gevolgen van het verwijderen van scheidende driehoeken of 4-cycli.
   • Ze tonen aan dat bepaalde configuraties (zoals het verwijderen van een driehoek die overblijvende subgrafen van orde 3 en 6 achterlaat) leiden tot subgrafen zoals $K_{3,6}$ of $K_{3,3,3}$ die niet in een torus kunnen worden ingebed zonder kruisingen, of die in strijd zijn met de planariteit van $G$.

B. Computergestuurde Zoektocht

Omdat de theoretische filters niet alle 7595 gevallen uitsluiten, voeren de auteurs een brute-force zoektocht uit:

1. Data: Ze gebruiken de lijst van 7595 maximale planaire grafen (triangulaties) van orde 12.
2. Filtering: Grafen met een maximale graad $\Delta > 8$ worden direct verwijderd (gebaseerd op Lemma 2.2).
3. Zoekalgoritme:
   • Eerst wordt gecontroleerd of het complement van een planaire graaf direct een torus-embeddable is. Resultaat: Geen enkele gevonden.
   • Vervolgens wordt gezocht naar situaties waarbij het complement van de planaire graaf precies één kant mist om toroidaal te zijn. Resultaat: Geen enkele gevonden.
   • Tot slot wordt gezocht naar situaties waarbij het complement precies twee kanten mist om toroidaal te zijn.
4. Implementatie: De zoektocht werd uitgevoerd met aangepaste C/C++ code. De zoektocht naar twee ontbrekende kanten duurde ongeveer 59 dagen.
5. Validatie: Isomorfe embeddings werden verwijderd om unieke paren te identificeren.

3. Belangrijkste Resultaten

De studie levert de volgende definitieve conclusies op:

1. Nee, een decompositie bestaat niet: Er bestaat geen decompositie van $K_{12}$ in een planaire graaf en een toroidale graaf.
   • Dit betekent dat $N(0, 1) = 12$. De kleinste volledige graaf die niet in een planair en een toroidaal deel kan worden opgesplitst, is $K_{12}$.
2. Refutatie van de Conjecture: De conjecture van Bickle/White (2013) die stelde dat de ondergrens voor $\gamma(G) + \gamma(\bar{G})$ voor alle $n \geq 11$ wordt bereikt, wordt weerlegd voor $n=12$. Voor $n=12$ zou de som 1 moeten zijn (planair + toroidaal), maar dit is onmogelijk.
3. Nabijheid van de oplossing: Hoewel een exacte decompositie niet bestaat, vonden de auteurs 123 unieke paren $(G, H)$ waarbij:
   • $G$ een planaire graaf van orde 12 is.
   • $H$ een subgraaf is van het complement van $G$.
   • $H$ toroidaal is.
   • Het aantal kanten in $H$ is precies twee minder dan het aantal kanten in $G$ (ofwel: het complement van $G$ heeft twee kanten te veel om toroidaal te zijn).
   • Dit betekent dat $K_{12}$ "bijna" kan worden opgesplitst; men hoeft slechts twee kanten uit het complement van een planaire graaf te verwijderen om een toroidale graaf te krijgen.

4. Significatie en Bijdrage

• Oplossen van een langdurig probleem: Het artikel sluit definitief een vraag af die sinds 1978 open stond in de topologische grafentheorie.
• Methodologische vooruitgang: De combinatie van theoretische limieten (graden, driehoeken, scheidende sets) met een geavanceerde computergestuurde zoektocht biedt een blauwdruk voor het oplossen van soortgelijke decompositieproblemen voor andere waarden van $N(\gamma, \gamma')$.
• Data en Reproduceerbaarheid: De auteurs hebben alle relevante data openbaar gemaakt, inclusief:
  • De lijst van 123 unieke paren met twee ontbrekende kanten.
  • Visualisaties van de planaire triangulaties en hun complementen op de torus.
  • Scripts en instructies om de 7595 planaire grafen te genereren (via Sulanke's Surftri).
  • De code en datasets zijn beschikbaar via een GitHub-repository, wat de reproduceerbaarheid en verdere onderzoeksmogelijkheden voor de gemeenschap vergroot.

Conclusie: Het artikel bewijst dat $K_{12}$ niet kan worden opgesplitst in een planair en een toroidaal deel, waardoor $N(0,1)=12$ wordt vastgesteld, en identificeert de specifieke structuren die het dichtst bij een dergelijke decompositie komen.