Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

Dit paper weerlegt Jain's tweede conjectuur over eenheidsvectorstromen door twee tegenvoorbeelden te construeren die waarden uit de verzameling $\{-5, 5\}$ vereisen, wat relevant is voor de implicaties op Tutte's 5-stroomconjectuur.

De kern

Stel je voor dat je een heel ingewikkeld legpuzzel hebt, maar dan niet op een plat vlak, maar op een bol (zoals een voetbal of een aardbol). Dit is het verhaal van het artikel dat we net hebben gelezen, vertaald naar gewoon Nederlands met een paar leuke vergelijkingen.

Het Grote Doel: De "Vijf-Kleuren" Droom

Wiskundigen zijn al heel lang op zoek naar een manier om elke mogelijke netvorm (een "graf" in wiskundetaal) te kleuren of te vullen met getallen, zonder dat er twee aangrenzende delen hetzelfde zijn of dat er een "stroom" stopt. Een beroemde wiskundige, Tutte, droomde er al van in de jaren '50: "Elk net zonder losse draden kan worden gevuld met 5 verschillende stroomsterktes."

Om dit te bewijzen, dacht een andere wiskundige, K. Jain, dat hij een slimme truc kon gebruiken. Hij stelde twee regels op:

1. De Regels: Je moet een bol kunnen bedekken met pijlen (vectoren) die allemaal even lang zijn.
2. De Magische Kaart: Je moet een manier vinden om elk punt op die bol een getal toe te wijzen (van -4 tot +4), zodat als je drie punten kiest die een perfect gelijkzijdig driehoekje vormen op de bol, hun getallen bij elkaar opgeteld precies nul zijn.

Als deze twee regels waar zijn, dan is Tutte's droom (de 5-stroom) ook waar. Het was een mooie, elegante oplossing.

De Wending: De Puzzel is Gebroken

Nikolay Ulyanov, de auteur van dit artikel, zegt: "Wacht even, dat laatste stukje klopt niet."

Hij heeft twee nieuwe, heel specifieke puzzels ontworpen. Stel je voor dat je een groep vrienden hebt die op een grote dansvloer (de bol) staan. Je vraagt ze om in groepjes van drie te dansen, waarbij ze een getal moeten roepen. De regel is: als ze een perfect driehoekje vormen, moet de som van hun getallen nul zijn.

Ulyanov heeft twee groepen vrienden ontworpen (de eerste met 50 punten, de tweede met 36 punten) die zo gekozen zijn dat ze onmogelijk kunnen dansen met alleen de getallen -4, -3, -2, -1, 1, 2, 3 en 4.

Het is alsof je probeert een muur te bouwen met alleen bakstenen van 4 verschillende maten, maar de architect heeft een ontwerp gemaakt waarbij je per se een baksteen van maat 5 nodig hebt om het dak te dekken.

Hoe deed hij dit? (De "Magische" Bouwstenen)

Ulyanov gebruikte twee slimme methoden om deze onmogelijke groepen te bouwen:

1. De Uitgebreide Icosidodecaëder (De 50-punten puzzel):
   Hij begon met een bekend geometrisch figuur (een ico-si-do-de-ca-eder, klinkt als een alien-schip, maar is gewoon een bol met 30 hoekpunten). Hij nam elk punt en liet er een klein rondje omheen ontstaan. Vervolgens liet hij deze rondjes elkaar snijden. Het resultaat? Een nieuwe, dikkere verzameling van 50 punten.

   • Het probleem: Toen hij probeerde de getallen -4 tot +4 toe te wijzen, botste het. De regels voor de driehoekjes maakten het onmogelijk. Hij moest per se de getallen -5 en +5 gebruiken.

2. De Wiskundige Wortel-Constructie (De 36-punten puzzel):
   Hier gebruikte hij een andere techniek, gebaseerd op het nemen van wortels uit getallen (zoals √3 of √5). Hij zocht naar punten die precies op de bol pasten en die samen driehoekjes vormden.

   • Het resultaat: Ook hier bleek dat de "magische kaart" van Jain faalde. Je kon de driehoekjes niet laten "summen tot nul" zonder de extra grote getallen (±5) te gebruiken.

Wat betekent dit voor de wiskunde?

Het artikel is een soort "rekenfout" die is ontdekt in een theorie die er mooi uitzag.

• De conclusie: Jain's tweede idee (dat je altijd met getallen tot 4 kunt werken) is onwaar.
• De gevolgen: Omdat deze twee ideeën samen Tutte's droom moesten bewijzen, is die droom nu weer even verder weg. We weten nu dat we voor sommige specifieke situaties op de bol waarschijnlijk toch "grote getallen" (zoals 5) nodig hebben.

De "Icebreaker" (De goede nieuws)

Voordat hij de fouten liet zien, liet hij ook een voorbeeld zien waar het wel werkt. Hij gebruikte een bekend figuur (de Petersen-graf) en liet zien dat daar de getallen -4 tot +4 prima werkten. Dit was als een proefje om te laten zien dat hij de regels goed begreep voordat hij de regels brak.

Samenvattend in één zin

De auteur heeft bewezen dat een bepaalde wiskundige theorie over het verdelen van getallen op een bol niet voor elk mogelijk patroon werkt, omdat hij twee specifieke patronen heeft gevonden waarvoor je per se een "grootere" getal (5) nodig hebt dan de theorie toeliet.

Het is alsof je dacht dat je elke muur kon bouwen met alleen bakstenen tot maat 4, maar Ulyanov heeft twee muren ontworpen die alleen staan als je een baksteen van maat 5 gebruikt. De theorie moet nu worden aangepast.

Technische samenvatting

Titel: Graph Puzzles II.1: Tegenvoorbeelden voor Jain's tweede conjectuur over eenheidsvectorstromen

Auteur: Nikolay Ulyanov
Datum: 24 maart 2026 (preprint)

---

1. Probleemstelling en Context

Het paper adresseert een fundamenteel probleem in de grafentheorie en meetkunde, specifiek gerelateerd aan nowhere-zero flows (stromen zonder nulwaarden) op grafen. De kern ligt bij twee conjectures van K. Jain:

1. Conjecture 1.1 (Unit Vector Flows): Elke brugvrije graaf heeft een stroom waarbij elke rand wordt toegewezen een 3-dimensionale vector met een eenheidsnorm (een punt op de 2-sfeer $S^2$).
2. Conjecture 1.2 ($S^2$ nz5-flow): Er bestaat een afbeelding $q: S^2 \to \{-4, -3, -2, -1, 1, 2, 3, 4\}$ met de volgende eigenschappen:
   • Antipodale punten (punten die elkaar op de sfeer tegenoverstaan) hebben waarden die elkaars tegengestelde zijn ($q(-p) = -q(p)$).
   • De som van de waarden van drie punten die op een grootcirkel equidistant liggen, is nul.

De Implicatie: Als beide conjectures waar zijn, zouden ze gezamenlijk de beroemde Tutte's 5-flow conjecture bewijzen (die stelt dat elke brugvrije kubische graaf een nowhere-zero 5-flow toelaat).

Het doel van dit paper is om Conjecture 1.2 te weerleggen door te tonen dat er eindige deelverzamelingen van $S^2$ bestaan waarvoor een dergelijke labeling met waarden $\{-4, \dots, 4\}$ onmogelijk is, en waarbij waarden $\pm 5$ (een nowhere-zero 6-flow) noodzakelijk zijn.

---

2. Methodologie

De auteur gebruikt een combinatie van meetkundige constructies, grafentheorie en computationele verificatie via Boolean Satisfiability (SAT) solvers.

A. Meetkundige Constructies

De auteur construeert twee specifieke eindige deelverzamelingen van punten op de eenheidssfeer $S^2$:

1. Expansie van het Icosidodecaëder: Een uitbreiding van de 30 hoekpunten van een Icosidodecaëder (een Archimedisch lichaam) tot een set van 50 punten.
2. Wortel-arithmetische constructie: Een nieuwe constructie gebaseerd op lineaire combinaties van wortels van gehele getallen, resulterend in een set van 36 punten.

B. Formele Verificatie (SAT)

Voor beide sets wordt het labelingsprobleem geëncodeerd als een SAT-probleem:

• Variabelen: Voor elk punt (en zijn antipode) worden binaire variabelen geïntroduceerd voor de toegestane waarden $\{-4, \dots, 4\}$.
• Constraints:
  • Exactly-one: Elk punt krijgt precies één waarde.
  • Antipodal: $q(-p) = -q(p)$.
  • Triple-sum: Voor elke drie punten op een grootcirkel moet $q(a) + q(b) + q(c) = 0$.
• Solver: De gegenereerde CNF-formules worden opgelost met PicoSAT/pycosat. Als de formule onbevredigbaar (unsatisfiable) is, betekent dit dat geen enkele geldige labeling bestaat binnen de gegeven waarden.
• Validatie: De resultaten zijn bovendien geverifieerd met exacte rekenkunde en formeel bewezen in Lean 4 (met de bv_decide tactic).

---

3. Belangrijkste Bijdragen en Resultaten

Het paper levert twee concrete tegenvoorbeelden die Conjecture 1.2 weerleggen:

Tegenvoorbeeld 1: 50-punten expansie van het Icosidodecaëder

• Constructie: Uitgaande van de 30 punten van een Icosidodecaëder, worden voor elk punt kleine cirkels gedefinieerd. Snijpunten van deze cirkels (gebaseerd op punten op een sferische afstand van $2\pi/5$) genereren 20 nieuwe punten.
• Structuur: De resulterende set van 50 punten vormt 40 grootcirkel-drietallen.
• Grafische Interpretatie: Na kwotiëntering door antipoden ontstaat een structuur die een combinatie is van de Petersen-graaf en een Möbius-ladder.
• Resultaat: De SAT-oplosser toont aan dat de CNF-formule (200 variabelen, 19765 clausules) onbevredigbaar is voor waarden $\{-4, \dots, 4\}$. Een labeling is alleen mogelijk als waarden $\pm 5$ worden toegestaan.

Tegenvoorbeeld 2: 36-punten constructie

• Constructie: Gebaseerd op een set van coördinaten gegenereerd door uitdrukkingen van de vorm $\sqrt{|w_1\sqrt{v_1} + w_2\sqrt{v_2}|}$. Na iteratief verwijderen van punten die in te weinig drietallen voorkomen, blijft een samenhangende component van 36 punten over met 13 drietallen.
• Resultaat: Ook hier is de SAT-formule (144 variabelen, 6710 clausules) onbevredigbaar voor de set $\{-4, \dots, 4\}$. Een oplossing bestaat wel voor waarden tot $\pm 5$ (een nowhere-zero 6-flow).

---

4. Significatie en Conclusies

• Wederlegging van Conjecture 1.2: Het paper bewijst definitief dat Jain's tweede conjectuur onwaar is. Er bestaan eindige deelverzamelingen van $S^2$ die een nowhere-zero 5-flow (waarden $\le 4$) niet toelaten, ondanks dat ze voldoen aan de meetkundige eisen.
• Impact op Tutte's Conjecture: Omdat de implicatie "Conjecture 1.1 + Conjecture 1.2 $\implies$ Tutte's 5-flow" niet langer geldig is via deze route, moet er een andere methode worden gevonden om Tutte's conjectuur te bewijzen, of moet Conjecture 1.1 worden herschreven.
• Open Vragen:
  • Kan men een subset vinden die zelfs waarden $\pm 6$ of hoger vereist? (Tot nu toe is $\pm 5$ het maximum).
  • Wat is de kleinste mogelijke contra-voorbeeld?
  • Is het mogelijk om een (mogelijk oneindige) subset van $S^2$ te vinden met specifieke algebraïsche eigenschappen die wel een 5-flow toelaat en bruikbaar is voor het bewijs van Tutte's conjectuur?
• Observatie over Modulo-flows: De auteur merkt op dat er in hun experimenten geen verschil is waargenomen tussen nowhere-zero $k$-flows en modulo-$k$ flows; beide vereisten dezelfde minimale $k$.

Beschikbaarheid: De code voor de constructies, SAT-encoding en Lean 4-verificatie is openbaar beschikbaar via een GitHub-repository.

Dit werk markeert een belangrijke stap in het begrijpen van de beperkingen van vectorstromen op grafen en de meetkunde van de sfeer, en dwingt de wiskundige gemeenschap om nieuwe benaderingen te zoeken voor het bewijs van klassieke stromingsconjectures.