🔢 mathematics

A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erd\H{o}s-Gyárfás Conjecture

Dit artikel stelt vast dat elk simpel kubisch bipartiet tegenvoorbeeld van de vermoeden van Erdős-Gyárfás ten minste 60 knopen moet hebben, een resultaat dat is bewezen via een gecertificeerde uitputtende berekening die alle dergelijke grafen met 58 of minder knopen elimineert.

Oorspronkelijke auteurs: Julius Tranquilli

Gepubliceerd 2026-08-05

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Julius Tranquilli

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een wereld voor die volledig bestaat uit verbindingen, waar stippen (vertices) door lijnen (edges) met elkaar verbonden zijn om ingewikkelde webben te vormen. Dit is het speelveld van de grafentheorie, een tak van de wiskunde die bestudeert hoe dingen met elkaar in relatie staan. In deze wereld is een "kubische bipartiete graaf" een heel specifiek soort web: het is een tweezijdige structuur waarbij elke stip precies met drie anderen verbonden is, en de stippen kunnen worden verdeeld in twee teams zodat geen twee stippen op hetzelfde team elkaar ooit raken.

Wiskundigen zijn al lang gefascineerd door een puzzel genaamd de Erdős–Gyárfás-conjectuur. Het stelt een eenvoudige maar hardnekkige vraag: als je een web bouwt waarbij elke stip minstens drie verbindingen heeft, moet er dan altijd een lus (een cyclus) zijn waarvan de lengte een macht van twee is? Denk aan machten van twee als de "magische getallen" van het raster: 4, 8, 16, 32, enzovoort. De conjectuur suggereert dat je, ongeacht hoe je je web draait en wendt, een lus van 4, 8 of 16 verbindingen niet kunt vermijden. Hoewel dit bewezen is voor sommige speciale soorten webben, blijft het algemene geval een mysterie. Het oplossen ervan zou ons helpen begrijpen wat de fundamentele regels zijn van hoe netwerken worden opgebouwd, van computercircuits tot sociale groepen.

Kom nu een nieuw hoofdstuk in dit verhaal tegen. Een onderzoeker genaamd Julius Tranquilli heeft een enorme, computergestuurde stap gezet in het oplossen van deze puzzel, specif으로 voor die tweezijdige, drievoudig verbonden webben. Het artikel, getiteld "A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős–Gyárfás Conjecture," doet niet alleen een gok; het voert een gecertificeerde, uitputtende zoektocht uit om te bewijzen dat elk web dat klein genoeg is om binnen een bepaalde omvang te passen, één van die magische lussen moet bevatten.

Hier is de grote onthulling: het artikel bewijst dat als je probeert een kubische bipartiete graaf te bouwen met 58 knopen of minder, je simpelweg niet kunt voorkomen dat er een lus van lengte 4, 8 of 16 ontstaat. Het is wiskundig onmogelijk om een "tegenvoorbeeld" (een web dat de regel breekt) te construeren dat kleiner is dan 60 knopen. Voor dit werk lag de best bekende limiet op 30 knopen. Dit nieuwe resultaat verdubbelt die veiligheidszone en duwt de grens van 30 helemaal naar 60.

Hoe hebben ze het gedaan? De auteur gebruikte een slimme truc om het probleem te vertalen. Ze veranderden het graafprobleem in een ander soort puzzel met betrekking tot "incidentieconfiguraties", die lijken op verzamelingen blokken waar punten samen gegroepeerd zijn. Ze realiseerden zich dat als een graaf de verboden lussen vermijdt, het een specifieal zesstaps-patroon (een 6-cyclus) moet bevatten. Door dit patroon te behandelen als een "wortel" of een startzaadje, konden ze de rest van de graaf stap voor stap laten groeien.

Vervolgens ontketenden ze een digitaal leger van zoekalgoritmen. Stel je een boom voor die in een computer groeit, waarbij elke tak een andere manier vertegenwoordigt om een nieuwe verbinding aan de graaf toe te voegen. De computer liet deze boom groeien tot een limiet van 29 "punten" (wat overeenkomt met 58 vertices in de oorspronkelijke graaf). De computer controleerde elke mogelijke tak om te zien of hij een volledige graaf kon laten groeien zonder een 4-, 8- of 16-lus te creëren. Het resultaat? Elke pad liep dood. De computer vond dat, ongeacht hoe je het probeerde te bouwen, de regels van het spel een lus dwongen te verschijnen lang voordat je de 60-knopen grens bereikte.

Om er zeker van te zijn dat de computer geen fout maakte, heeft de auteur de code niet slechts één keer gedraaid. Ze bouwden twee volledig verschillende zoekprogramma's met verschillende methoden om te controleren op de verboden lussen. Ze maakten ook een "certificaat" aan—een digitaal bonnetje dat iedereen kan controleren om het werk te verifiëren. Beide programma's kwamen perfect overeen: nul voltooiingen. Er werden geen succesvolle grafen gevonden.

Het artikel keek ook naar de "diepste" delen van de zoekboom, de punten waar de computer het dichtst bij een oplossing was. Het vond 337 staten waar de graaf bijna compleet was maar nog enkele verbindingen miste. Deze staten smolten samen tot slechts zes verschillende vormen. Toen de auteur deze zes vormen analyseerde, vond hij dat de resterende verbindingen die nodig waren om de graaf te voltooien, onvermijdelijk een verboden lus zouden creëren. Het was alsof je een puzzel probeert af te maken, om er vervolgens achter te komen dat het laatste stukje dat je nodig hebt, het plaatje zou breken.

Dus, wat betekent dit? Het betekent dat als er een tegenvoorbeeld voor de Erdős–Gyárfás-conjectuur bestaat in de wereld van kubische bipartiete grafen, het een gigantisch beest moet zijn met minstens 60 knopen. De "kleine" monsters zijn opgejaagd en als onmogelijk bewezen. Hoewel de conjectuur zelf niet volledig is opgelost (we weten nog steeds niet of een gigantisch tegenvoorbeeld van 60+ knopen bestaat), heeft dit artikel het speelveld vrijgemaakt van alle kleine mogelijkheden en de lat aanzienlijk hoger gelegd voor iedereen die hoopt op een mazen in de wet te vinden in de regels van deze wiskundige webben.

Technische Samenvatting: Een ondergrens van 60 knopen voor kubische bipartiete tegenvoorbeelden van de Erdős–Gyárfás-conjectuur

Probleemstelling
De Erdős–Gyárfás-conjectuur stelt dat elke eindige simpele graaf met een minimale graad van ten minste drie een simpele cyclus bevat waarvan de lengte een macht van twee is (d.w.z. 4, 8, 16, 32, ...). Hoewel de conjectuur open blijft voor algemene grafen, is deze geverifieerd voor specifieke beperkte klassen. Dit artikel richt zich op de klasse van simpele kubische bipartiete grafen. Vooraf aan dit werk was de gevestigde ondergrens voor de orde (het aantal knopen) van een potentieel tegenvoorbeeld in deze klasse $n \ge 30$ (gebaseerd op de berekening van Markström uit 2004) of $n \ge 32$ (gebaseerd op een publieke SAT-gebaseerde berekening uit 2026). Het doel was om te bepalen of een tegenvoorbeeld kon bestaan met minder dan 60 knopen.

Methodologie
Het bewijs maakt gebruik van een combinatie van structurele graaftheoretische reducties en een gecertificeerde, exhaustieve computercerzoek. De methodologie verloopt in drie hoofdfasen:

Structurele Reductie (Moore-grens en Incidentie-translatie):
- De auteur past eerst een edge-rooted Moore-grensargument toe om aan te tonen dat elke simpele kubische bipartiete graaf met maximaal 58 knopen die cycli van lengte 4 ( $C_4$ ) en 8 ( $C_8$ ) vermijdt, noodzakelijkerwijs een cyclus van lengte 6 ( $C_6$ ) moet bevatten.
- De graaf wordt vervolgens getranslateerd naar een incidentiestructuur. Een kubische bipartiete graaf wordt gerepresenteerd als de Levi-graaf van een symmetrische $v_3$ -configuratie (een lineaire 3-uniforme, 3-reguliere $v$ -punts verzameling).
- Onder deze translatie komt een $C_6$ in de graaf overeen met een Berge-driehoek (drie blokken die tweeledig snijden in verschillende punten) in de configuratie.
- De afwezigheid van $C_4$ en $C_8$ in de graaf vertaalt zich naar de configuratie die lineair is (geen twee blokken delen meer dan één punt) en geen Berge-cycli van lengte 4 of 8 bevat.
Rooted Search en Normalisatie:
- Door een Berge-driehoek vast te leggen en symmetrie-reducties toe te passen, demonstreert de auteur dat er tot isomorfie slechts twee verschillende rooted extensies (banen) mogelijk zijn voor het blok dat door een specifiek punt in de driehoek loopt.
- Dit reduceert het probleem tot een restricted-growth search op deze twee specifieke root-banen. De zoektocht genereert configuraties door punten en blokken toe te voegen in lexicografische volgorde, waarbij een "punt-cap" van 29 wordt gehandhaafd (aangezien $2v \le 58 \implies v \le 29$ ).
- De zoektocht breekt een tak af als er een verboden Berge-cyclus (lengte 4 of 8) wordt gecreëerd of als een staat wordt bereikt waarin geen verdere blokken kunnen worden toegevoegd zonder de restricties te schenden.
Gecertificeerde Exhaustieve Computatie:
- Twee onafhankelijke implementaties van de zoektocht werden uitgevoerd met verschillende algoritmen voor de $C_{16}$ oracle (detectie van cycli van lengte 16):
  - Implementatie A: Gebruikt een eenvoudige pad-Depth-First Search (DFS).
  - Implementatie B: Voegt volledige lijsten van 7-randige half-paden samen.
- Beide zoektochten maakten gebruik van een statisch getuige-certificaat systeem. Een streaming checker reconstrueert de zoekboom, valideert positieve cyclus-getuigen en verifieert dat er geen voltooide configuratie (waarbij alle punten een graad 3 hebben) bestaat binnen de cap van 29 punten.
- De zoektocht werd geverifieerd tegen bekende censusgegevens voor kleinere configuraties ( $v \le 13$ ) om de correctheid van de generator te waarborgen.

Belangrijkste Resultaten

Stelling 1: Elke simpele kubische bipartiete graaf met $|V(G)| \le 58$ bevat een simpele cyclus van lengte 4, 8 of 16.
Corollary 2: Elk simpel kubisch bipartiet tegenvoorbeeld voor de Erdős–Gyárfás-conjectuur moet minimaal 60 knopen hebben.
Zoekstatistieken: De exhaustieve zoektocht besloeg twee root-banen met in totaal 21.493 staten en 1.762.368 pogingen tot extensie. Cruciaal is dat er nul voltooiingen werden gevonden in beide banen.
Terminale Obstructie: De zoektocht identificeerde 337 overlevende staten op de maximale diepte (19 blokken, waarbij alle 29 punten worden gebruikt). Deze staten klonterden samen in zes isomorfie-klassen (kernels). Analyse van de "compatible-pair grafen" voor deze kernels toonde aan dat zij bossen zijn (driehoekvrij), wat bewijst dat een 20e blok niet aan een van deze staten kan worden toegevoegd zonder een $C_4$ , $C_8$ of $C_{16}$ te creëren.

Betekenis en Claims
Het artikel claimt de gevestigde ondergrens voor kubische bipartiete tegenvoorbeelden te hebben verhoogd van $n \ge 30$ (of $n \ge 32$ ) naar $n \ge 60$ .

Sterkte van het resultaat: Het resultaat wordt in een sterkere vorm gepresenteerd dan een loutere verificatie van de conjectuur; het bewijst dat een van de eerste drie relevante macht-van-twee cycluslengtes (4, 8 of 16) wordt afgedwongen in deze klasse voor grafen tot 58 knopen. Er wordt expliciet vermeld dat een 32-cyclus niet vereist is om deze ondergrens vast te stellen.
Verificatie: Het resultaat wordt ondersteund door een "gecertificeerde exhaustieve computatie" bestaande uit twee aparte implementaties met verschillende oracles en een statische certificaat-checker, wat garandeert dat het resultaat geen artefact is van een enkele softwarefout.
Beperkingen: Het artikel stelt expliciet dat de berekening geen zijde van grootte 30 (60 knopen) onderzoekt en daarom de existentie van een tegenvoorbeeld bij exact 60 knopen niet uitsluit. Het werk stelt de grens vast binnen de klasse tot 58 knopen.

Artefacten
De auteur biedt volledige reproduceerbaarheid, inclus_ief broncode, certificaten, logs en verificatieprogramma's, gearchiveerd op Zenodo (DOI: 10.5281/zenodo.21695513) en een GitHub-repository. Het artikel onthult ook dat OpenAI-tools (ChatGPT en Codex) hebben geassisteerd bij de codeontwikkeling, de formulering van de structurele aanpak en het opstellen van het manuscript, maar dat de wiskundige argumenten en het bewijsmateriaal rusten op de behouden code, logs en certificaten.

Technische Samenvatting: Een ondergrens van 60 knopen voor kubische bipartiete tegenvoorbeelden van de Erdős–Gyárfás-conjectuur

Meer zoals dit