🔢 mathematics

Exact Zarankiewicz Values On Two Finite Frontier Slices

Dit artikel presenteert een gecombineerd, op certificaten gebaseerd computerondersteund bewijs dat exacte Zarankiewicz-getallen vaststelt voor specifieke eindige snedes en een nabijgelegen grens van het Z(m,n,3,3)-probleem, gebruikmakend van baan-certificaten, deletie-lemma's en rigoureuze rekenkundige verificatie om waarden zoals Z(12,n,3,3)=6n voor 18≤n≤22 en Z(13,22,3,3)=137 te bevestigen.

Oorspronkelijke auteurs: Koyar Afrasyab

Gepubliceerd 2026-08-11

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Koyar Afrasyab

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 voor dat je een stadsplanner bent die het meest efficiënte wegennetwerk mogelijk probeert te bouwen. Je hebt twee groepen locaties: een verzameling "Hubs" aan de ene kant en een verzameling "Bestemmingen" aan de andere kant. Je doel is om zoveel mogelijk wegen (verbindingen) tussen hen te tekenen om het verkeer te laten stromen. Er is echter een strikte bestemmingswet: je bent verboden een specifiek, rommelig kruispatroon te bouwen. In de wiskundige taal is dit verboden patroon een "volledige bipartiete subgraaf", of simpel gezegd: je kunt niet een situatie hebben waarin drie Hubs allemaal verbonden zijn met dezelfde drie Bestemmingen. Als je dat doet, heb je de regel overtreden.

Dit puzzelstuk staat bekend als het Zarankiewicz-probleem. Het is een klassieke hersenkraker in de combinatorica, de tak van de wiskunde die gewijd is aan het tellen, ordenen en organiseren van zaken. Hoewel wiskundigen al manieren hebben gevonden om dit voor enorme, theoretische steden op te lossen, ligt de echte uitdaging bij deze "middelgrote" steden. Voor deze specifieke afmetingen is het aantal mogelijke wegenkaarten zo groot dat je ze niet allemaal met de hand kunt controleren, maar ze zijn ook te complex voor eenvoudige formules die werken voor oneindige steden. Het is een "Goldilocks-zone" van moeilijkheidsgraad: te groot voor een bewijs met pen en papier, maar te klein voor de "asymptotische" afkortingen die werken voor oneindige steden. Het oplossen van deze exacte getallen is belangrijk omdat ze de verborgen grenzen van efficiëntie in netwerken onthullen, van computerchips tot sociale mediaconnecties.

Ontmoet Koyar Afrasyab, een onderzoeker die zojuist een bijzonder hardnekkige set van deze middelgrote puzzels heeft gekraakt. Beschouw het probleem als een poging om het absolute maximum aantal wegen op een raster te tekenen zonder dat er dat verboden "drie-bij-drie" verkeersprobleem ontstaat. Het papier richt zich op twee specifieke "snedes" van dit probleem: rasters met 12 rijen en rasters met 13 rijen, gecombineerd met diverse aantallen kolommen.

De belangrijkste ontdekking is een lijst met exacte "snelheidslimieten" voor deze rasters. Voor een raster met 12 rijen en ergens tussen de 18 en 22 kolommen is het maximale aantal wegen (randen) dat je kunt hebben zonder de regel te breken exact $6n$ (waarbij $n$ het aantal kolommen is). Bijvoorbeeld, een 12-bij-18 raster kan precies 108 wegen bevatten, en een 12-bij-22 raster kan precies 132 wegen bevatten. Het artikel bewijst dit door aan te tonen dat als je slechts één weg extra zou toevoegen aan deze rasters, je onvermijdelijk dat verboden verkeersprobleem creëert.

Het meest dramatische deel van het verhaal heeft betrekking op een 13-bij-22 raster. Eerdere vermoedens suggereerden dat de limiet misschien wel zo hoog als 140 wegen zou zijn. Het door de computer ondersteunde bewijs van Afrasyab werkt als een zeef die elke onmogelijke rangschikking wegfiltert. Ze begonnen met de aanname dat iemand een raster met 138 wegen zou kunnen bouwen zonder de regels te breken. Door een slim proces van eliminatie—het controleren van de "profielen" van hoe de wegen met elk punt verbonden zijn—bewezen ze dat 138 onmogelijk is. Ze verkleinden het bereik totdat ze het ware plafond vonden: 137 wegen. Ze leverden zelfs een specifieke, geverifieerde kaart van 137 wegen die werkt, waarmee bewezen wordt dat je dat aantal kunt bereiken maar niet hoger kunt gaan.

Het artikel legt ook de kaart vast voor verschillende naburige rasters, waarbij de exacte limieten worden bepaald voor afmetingen zoals 13-bij-18, 14-bij-17 en 15-bij-18. Voor één lastige casus, een 16-bij-17 raster, bevestigt het bewijs dat je zeker 132 wegen kunt bouwen, maar de bovengrens is nog steeds een nauwe marge tussen 132 en 133.

Wat dit werk bijzonder maakt, is hoe het is gedaan. De auteur heeft niet alleen een "black-box" computerprogramma gedraaid dat zei "geen oplossing gevonden." In plaats daarvan creëerde hij een "certificaat-gebaseerd" bewijs. Stel je een detective voor die een spoor van broodkruimels achterlaat: voor elk onmogelijk scenario dat hij uitsloot, liet hij een wiskundig "bewijsstuk" (een certificaat) achter dat iedereen met een eenvoudige rekenmachine kan controleren om de fout te verifiëren. Het artikel bevat een digitaal pakket waarmee je een enkele opdracht kunt uitvoeren om de hele onderzoeksfase te herhalen, waarbij miljoenen van deze bewijsstukken worden gecontroleerd om er zeker van te zijn dat er geen fouten zijn gemaakt. Het is een rigoureus, transparant en volledig reproduceerbaar succes voor de wiskundige gemeenschap, dat "misschien"-antwoorden verandert in "absoluut zeker"-feiten.

Technische Samenvatting: Exacte Zarankiewicz-waarden op twee eindige frontiers

Probleemstelling
Het artikel behandelt het Zarankiewicz-probleem, dat streeft naar het maximale aantal randen, aangeduid als $Z(m, n, s, t)$ , in een bipartiete graaf met partities van grootte $m$ en $n$ die geen volledige bipartiete subgraaf $K_{s,t}$ bevat. Specifiek richt de auteur zich op de gevallen waarbij $s=t=3$ (het vermijden van $K_{3,3}$ ) voor matige eindige parameters. Hoewel de asymptotische theorie goed ontwikkeld is, blijven exacte waarden voor specifieke eindige dimensies moeilijk te bepalen vanwege extreme symmetrie en de hoge kosten van bewijsverificatie. Het artikel richt zich op een "eindige frontier" van eerder onopgeloste of gedeeltelijk opgeloste waarden, inclusclusief de strook $Z(12, n, 3, 3)$ voor $18 \le n \le 22$ , het specifieke geval $Z(13, 22, 3, 3)$ , en een cluster van nabijgelegen waarden rond $13 \times 18$ en $16 \times 17$ .

Methodologie
Het bewijs is computerondersteund maar strikt certificaat-gebaseerd, wat het onderscheidt van methoden die uitsluitend vertrouwen op mixed-integer linear programming (MILP) solvers die "infeasible" teruggeven of SAT-solvers zonder expliciete getuigen. De verificatie steunt op exacte gehele getallen en rationale rekenkunde (met behulp van Python's Fraction en standaardbibliotheken), waarbij floating-point optimalisatie alleen wordt gebruikt voor de initiële ontdekking van certificaten.

De methodologie hanteert een meerlagige reductiestrategie:

Globale Relaxatie en Graadprofielen: Voor het $13 \times 22$ geval gaat de auteur uit van een hypothetische matrix met 138 randen. Door de "straf"-functie $p(d) = \binom{d}{3} - 15d + 70$ geassocieerd met kolomgraden te analyseren, wordt de zoekruimte gereduceerd van alle mogelijke matrices naar slechts 83 onderscheidende graadprofielen (histogrammen van kolomgraden).
Farkas-certificaten: Voor 77 van deze 83 profielen construeert de auteur exacte rationale Farkas-certificaten. Deze certificaten bewijzen onhaalbaarheid door aan te tonen dat de lineaire beperkingen opgelegd door de $K_{3,3}$ -vrije conditie (specifiek dat elke rij-triple in maximaal 2 kolommen voorkomt) niet door een niet-negatieve gehele oplossing voor dat profiel kunnen worden voldaan.
Marked-Row en Leave Enumeratie: De resterende zes profielen worden uitgesloten met meer fijnmazige technieken. De auteur fixeert een "gemarkeerde rij", verwijdert deze, en analyseert de resulterende "leave multigraph" op de resterende 12 punten. Dit omvat:
- Congruentie-argumenten: Het gebruik van modulaire rekenkunde op rij-tekorten om specifieke configuraties uit te sluiten (bijv. profiel 6187391).
- Gram-matrix Beperkingen: Het controleren van rang- en determinantcondities van de incidentiematrix van residuele blokken.
- Exacte Enumeratie: Het exhaustief enumereren van residuele blokontwerpen en het toepassen van integer-geschaalde Farkas-certificaten op de resterende factorisatiesystemen.
Verwijderingslemma's en Getuigen: Voor de $12 \times n$ strook en de frontier closure gebruikt de auteur "verwijderingslemma's" (die $Z(m, n)$ relateren aan $Z(m, n-1)$ ) in combinatie met expliciete constructieve getuigen (matrices die de ondergrenzen bereiken) om exacte gelijkheden vast te stellen.

Belangrijkste Bijdragen en Resultaten
Het artikel levert een gecombineerd, certificaat-gebaseerd bewijs voor de volgende exacte waarden en grenzen:

De $12 \times n$ Strook: Bewijst $Z(12, n, 3, 3) = 6n$ voor $18 \le n \le 22$ . Dit wordt vastgesteld door een exact certificaat voor $Z(12, 18, 3, 3) = 108$ en daaropvolgende verwijderingsargumenten ondersteund door expliciete getuigen voor $n=19, 20, 21, 22$ .
Het $13 \times 22$ Geval: Bewijst $Z(13, 22, 3, 3) = 137$ . De bovengrens van 138 wordt geëlimineerd door de hierboven beschreven exhaustieve profielanalyse. Een ondergrens van 137 wordt bevestigd via een expliciete constructie (een $13 \times 22$ binaire matrix met 137 enen en geen $K_{3,3}$ ).
Frontier Closure: Stelt exacte waarden vast voor vier naburige cellen:
- $Z(13, 18, 3, 3) = 116$
- $Z(14, 17, 3, 3) = 118$
- $Z(14, 18, 3, 3) = 124$
- $Z(15, 17, 3, 3) = 126$
- $Z(15, 18, 3, 3) = 132$
Het $16 \times 17$ Interval: Rapporteert het interval $132 \le Z(16, 17, 3, 3) \le 133$ . De ondergrens wordt ondersteund door een nieuwe 132-rand getuige; de bovengrens van 133 is overgenomen uit eerdere literatuur (Collins et al.). Het artikel merkt expliciet op dat de exacte waarde voor deze specifieke cel niet binnen dit werk wordt bepaald.

Betekenis en Claims
De auteur beweert dat dit werk een volledig, reproduceerbaar en certificaat-gebaseerd bewijs biedt voor deze specifieke Zarankiewicz-waarden. De betekenis ligt in de rigoureuze scheiding tussen ontdekking (waar floating-point heuristieken kunnen worden gebruikt) en verificatie (die alleen exacte rekenkunde gebruikt).

Reproduceerbaarheid: Het artikel bevat een "one-command verification gate" die alle 5,7 miljoen exacte niet-negativiteitscontroles herhaalt, inclusclusief de regeneratie van graadprofielen, het afspelen van Farkas-certificaten en de exhaustieve enumeratie van residuele blokontwerpen.
Bescheidenheid: De auteur stelt expliciet dat deze resultaten moeten worden beschouwd als "nieuwe computerondersteunde bewijzen in afwachting van onafhankelijke reproductie en peer review". Het artikel claimt niet het algemene Zarankiewicz-probleem op te lossen of een universeel algoritme te bieden, maar demonstreert een taakverdeling voor eindige extreme problemen: het gebruik van grove globale relaxaties om de meeste gevallen te elimineren en het reserveren van exacte, computationeel intensieve enumeratie voor de weinige "moeilijke" residuele profielen.
Eerdere Literatuur: De auteur merkt op dat hoewel de 137-rand constructie voor $13 \times 22$ eerder is gerapporteerd, de exacte bovengrens een nieuwe bijdrage is. Evenzo worden de specifieke waarden voor de $12 \times n$ strook ( $n=18$ tot $21$) en de frontier closure waarden als nieuwe exacte resultaten gerapporteerd die niet te vinden zijn in de geïndexeerde literatuur tot de datum van het artikel (augustus 2026).

Het artikel concludeert door te benadrukken dat er geen ongeverifieerde DRAT-claims, SAT-timeouts of floating-point solver statussen worden gebruikt als premissen voor de stellingen, waardoor de wiskundige claims volledig rusten op expliciete eindige data en exacte rekenkunde.

Meer zoals dit