Op 15 maart zorgden intrigerende aankondigingen van seminars voor gerommel op het gebied van combinatoriek, de wiskundige studie van tellen. Drie medewerkers waren van plan om de volgende dag gecoördineerde lezingen te houden. Julian Sahasrabudhe zou wiskundigen in Cambridge, Engeland toespreken, terwijl Simon Griffiths zou het nieuws delen in Rio de Janeiro en Marcelo Campos in São Paulo. Alle drie de toespraken droegen identieke titels en cryptische samenvattingen van twee zinnen die verwezen naar "recente vooruitgang op een oud probleem van Erdős." Terwijl Paul Erdős, een in 1996 overleden Hongaarse wiskundige, poseerde honderden problemen tijdens zijn carrière hadden combinatoristen al snel door waar het trio over wilde praten. Er deden geruchten de ronde over iets dat het Ramsey-getal wordt genoemd, een van de moeilijkste grootheden om te berekenen in de hele wiskunde.

Ramsey-getallen hebben geleid tot een hele discipline genaamd Ramsey-theorie, die zoekt naar onontkoombare patronen in een enorm scala aan systemen.

Stel dat u probeert alle gehele getallen over een aantal buckets te verdelen en dat u wilt voorkomen dat reeksen van gelijkmatig verdeelde getallen in een van de buckets worden geplaatst. Ramsey-theorie laat zien dat je zult falen (tenzij je oneindig veel emmers hebt). De theorie kan worden toegepast op bijna alles wat je kunt tellen. De centrale les is dat "je geen volledig chaotisch systeem kunt creëren", zegt Benny Sudakov, een wiskundige aan het Zwitserse Federale Instituut voor Technologie Zürich.

Het Ramsey-getal kwantificeert hoe groot een paradigmatisch voorbeeld moet zijn voordat bepaalde patronen onvermijdelijk ontstaan. Maar ondanks de centrale ligging heeft niemand het Ramsey-getal voor iedereen kunnen berekenen, behalve voor de eenvoudigste gevallen. Het beste dat ze hebben kunnen doen, is grenzen (of grenzen) vinden voor wat het zou kunnen zijn. Zelfs toen was de bovengrens die Erdős en een medewerker bijna een eeuw geleden voor het eerst hadden vastgesteld, nauwelijks verschoven.

Vervolgens kondigden de onderzoekers tijdens de seminars van 16 maart, en in een paper die later die avond werd gepost, aan dat ze de bovengrens van het Ramsey-getal met een exponentieel bedrag hadden verbeterd.

"Ik was gevloerd," zei Yuval Wigderson, een wiskundige aan de Universiteit van Tel Aviv, bij het horen van het nieuwe resultaat. "Ik stond letterlijk een half uur tot een uur te trillen."

De partijlijnen

Ramsey-theorie stelt meestal vragen over de gehele getallen of over grafieken. Een grafiek verwijst in deze context naar verzamelingen punten die knooppunten worden genoemd, verbonden door lijnen die randen worden genoemd en die eigenschappen kunnen hebben zoals lengte of - zoals in het geval van de Ramsey-getallen - kleur.

Een volledige grafiek is zowel gecompliceerd als eenvoudig: elk knooppunt is verbonden met elk ander knooppunt. Het Ramsey-getal beschrijft hoeveel knooppunten een volledige graaf moet bevatten om gedwongen te worden een bepaalde structuur te hebben. Stel dat de randen van een volledige grafiek een van twee kleuren krijgen toegewezen: rood of blauw. En stel dat u de randen probeert te kleuren op een manier die voorkomt dat een groep knooppunten wordt verbonden met randen van dezelfde kleur. In 1930 bewees Frank Ramsey dat als een grafiek groot genoeg is, het onmogelijk wordt om te voorkomen dat er ontstaat wat wiskundigen een monochromatische kliek noemen: een groep knooppunten waarvan de gemeenschappelijke randen allemaal rood of allemaal blauw zijn.

Hoe groot moet een grafiek precies zijn voordat er een monochromatische kliek ontstaat? Het antwoord hangt af van de grootte van de kliek. Ramsey toonde aan dat er een getal bestaat, nu het Ramsey-getal genoemd, dat het minimale aantal knooppunten vertegenwoordigt waarvoor een monochromatische kliek van een bepaalde grootte moet bestaan, ongeacht hoe de randen gekleurd zijn.

Maar de grootte van het Ramsey-nummer is moeilijk vast te stellen. In 1935, vijf jaar nadat Ramsey had aangetoond dat het bestaat, gaven Erdős en George Szekeres een nieuwe, strakkere bovengrens voor hoe groot het Ramsey-getal is voor een kliek van een bepaalde grootte. Maar sindsdien hebben wiskundigen de berekening van Erdős en Szekeres nauwelijks kunnen verbeteren.

Om een ​​betere intuïtie te krijgen voor wat dit betekent, kunnen we een klassiek voorbeeld bekijken, waarin knooppunten gasten op een feest vertegenwoordigen. Kleur de rand tussen twee willekeurige gasten rood als ze elkaar eerder hebben ontmoet, en blauw als ze elkaar nog niet hebben ontmoet. Je kunt elke kliekgrootte kiezen die je wilt — nodig genoeg mensen uit voor het feest, en je kunt er niet omheen een groep mensen uit te nodigen die elkaar allemaal kennen (een kliek in meerdere betekenissen van het woord) of een groep mensen uit te nodigen die nog nooit eerder ontmoet.

"Het eenvoudigste dat je in een grafiek kunt hebben, is een monochromatische kliek," zei Maria Tsjoednovski, een wiskundige aan Princeton University. “Het is eigenlijk verbazingwekkend dat je in elke enorme grafiek een grote daarvan kunt vinden. Het is helemaal niet duidelijk.”

De eerste paar Ramsey-getallen zijn relatief eenvoudig te berekenen. Laten we zeggen dat je de grootte wilt weten van de kleinste grafiek die onvermijdelijk een kliek van grootte twee moet bevatten, of R(2) voor wiskundigen. Aangezien een complete graaf met twee knooppunten slechts twee knooppunten zijn die verbonden zijn door een rand, en die rand rood of blauw moet zijn, is R(2) 2. Meer in het algemeen is R(k), of het Ramsey-nummer van k, is het minimale aantal knooppunten waarboven een graaf niet kan voorkomen dat er een kliek van grootte in zit k.

Het is niet zo moeilijk om aan te tonen dat het Ramsey-getal voor een kliek van grootte 3, of R(3), 6 is (zie afbeelding). Maar het was pas in 1955 dat R(4) vastgepind werd op 18. R(5) blijft onbekend - het is minstens 43 en niet groter dan 48. Hoewel deze getallen klein zijn, is het uitzoeken van alle mogelijke kleuringen onmogelijk. van de vraag, zei David Conlon van het California Institute of Technology. Overweeg het aantal kleuringen op een volledige grafiek met 43 knooppunten. “Je hebt 903 randen; elk daarvan kan op twee manieren worden gekleurd, 'legde hij uit. “Dus je krijgt er 2⁹⁰³, die gewoon astronomisch groot is.”

Naarmate de kliek groter wordt, wordt de taak om het Ramsey-nummer vast te pinnen alleen maar moeilijker. Erdős grapte dat een totale oorlog met wiskundig veeleisende buitenaardse wezens gemakkelijker zou zijn dan proberen bereken R(6), die ergens tussen de 102 en 165 ligt. Het bereik van onzekerheid groeit snel: volgens schattingen samengesteld door Stanisław Radziszowski, R(10) kan zo klein zijn als 798 en zo groot als 23,556. Maar de doelen van wiskundigen reiken veel verder dan het Ramsey-getal van 10. Ze willen een formule die een goede schatting geeft van R(k), zelfs - of vooral - wanneer k is extreem groot.

"Ik ken geen persoon in de combinatoriek die niet op zijn minst een beetje over dit probleem heeft nagedacht," zei Wigderson. "Dit probleem is, denk ik, heel bijzonder."

Bevel in de rechtbank

Frank Ramsey was een eclectische, briljante figuur die stierf toen hij 26 jaar oud was. Slechts enkele weken voordat hij stierf, de Proceedings van de London Mathematical Society gepubliceerde de krant waarin hij Ramsey-nummers introduceerde. Dat werk ging niet eens over grafieken, maar over een probleem in de wiskundige logica. Ramsey bewees dat een bewering die aan bepaalde voorwaarden voldoet, in ieder geval een deel van de tijd waar moet zijn. Een van die voorwaarden was dat er een groot "universum" van scenario's was om de bewering in te testen. Als opstap naar dit resultaat toonde Ramsey aan dat het Ramsey-getal eindig is.

Vijf jaar later toonden Erdős en Szekeres aan dat het Ramsey-nummer van k is minder dan 4^k. En 12 jaar daarna, Erdős liet zien dat het groter is dan ongeveer $latex sqrt{2}^k$. Om dat te doen, berekende hij de kans dat een grafiek met willekeurig gekleurde randen een monochromatische kliek bevat. Deze "probabilistische" techniek werd enorm invloedrijk in de grafentheorie. Het sloot ook R(k) tussen twee exponentieel groeiende doelpalen: $latex sqrt{2}^k$ en $latex 4^k$.

Naarmate de decennia verstreken, probeerden talloze wiskundigen de kloof tussen de mogelijke waarden van het Ramsey-getal te verkleinen. Sommigen slaagden: in 1975, Joel Spencer verdubbelde de ondergrens. En een serie papers van Conlon, Andreas Thomasson en Ashwin Saho de bovengrens naar beneden geduwd met een factor van ongeveer $latex 4^{log(k)^2}$ tegen 2020. Maar vergeleken met de afmetingen van de grenzen op het Ramsey-getal waren deze aanpassingen klein. Elke reductie tot de 4 in de formule R( van Erdős en Szekeres daarentegenk) < 4^k zou een exponentiële verbetering zijn, snel groeiend als k Wordt groter.

"Het lijkt gewoon een schattige kleine vraag," zei Rob Morris, een wiskundige bij IMPA, het Braziliaanse Instituut voor Zuivere en Toegepaste Wiskunde, in Rio de Janeiro, die samen met Campos, Griffiths en Sahasrabudhe co-auteur was van het nieuwe resultaat. “Het is een beetje subtiel om te waarderen. Maar mensen vinden het echt belangrijk.” Dit is mogelijk een understatement. "Als ze het in 1936 hadden bewezen, zouden mensen hebben gezegd: oké, dus wat maakt het uit?" zei Béla Bollobás, de promovendus van Morris en Sahasrabudhe aan de Universiteit van Memphis. "Sindsdien is bewezen dat het een heel groot probleem is, omdat er in de loop der jaren enkele duizenden artikelen zijn geschreven over verschillende varianten van het Ramsey-probleem." Als Liana Yepremyan, een wiskundige aan de Emory University, zei: "De Ramsey-getallen creëren die brug tussen combinatoriek en waarschijnlijkheid en geometrie."

Game Theory

 In augustus 2018 was Sahasrabudhe een postdoctoraal onderzoeker onder Morris bij IMPA. De twee hoopten toen een nieuw project te starten met Griffiths, die lesgeeft aan de nabijgelegen Pauselijke Katholieke Universiteit een artikel van Conlon hun aandacht getrokken. De paper schetste een mogelijke strategie voor het verkrijgen van een exponentiële verbetering van het Ramsey-getal. Griffiths, Morris en Sahasrabudhe begonnen met het idee te spelen.

"In het begin was het heel spannend", herinnert Sahasrabudhe zich. Het kostte hen slechts ongeveer een maand, zei hij, om een ​​schets van hun argument op te stellen.

Hun plan was om voort te bouwen op de ideeën die werden gebruikt in het oorspronkelijke bewijs van Erdős en Szekeres dat $latex R(k) < 4^k$. Om te bewijzen dat het Ramsey-getal maximaal $latex 4^k$ is, stel je voor dat je een spel speelt op een volledige grafiek met $latex 4^k$ knopen. Het spel heeft twee spelers. Eerst kleurt je tegenstander elke rand rood of blauw, in de hoop de randen zo te kleuren dat er geen monochromatische kliek van k knooppunten.

Zodra je tegenstander klaar is met kleuren, is het jouw taak om te zoeken naar een monochromatische kliek. Als je er een vindt, win je.

Om dit spel te winnen, kun je een eenvoudige strategie volgen. Het helpt om (metaforisch) na te denken over het sorteren van uw knooppunten in twee emmers. De knooppunten in de ene bucket vormen een blauwe kliek en de knooppunten in de andere een rode kliek. Sommige knooppunten worden verwijderd, om nooit meer iets van te horen. In het begin zijn beide emmers leeg en is elk knooppunt een kandidaat om in een van beide te gaan.

Begin met elk knooppunt dat je aanspreekt. Kijk dan naar de verbindingsranden. Als de helft of meer van de randen rood zijn, verwijder dan alle blauwe randen en de knooppunten waarmee ze verbonden zijn. Zet dan je oorspronkelijke keuze in de “rode” emmer. Alle rode randen van dit knooppunt zijn nog springlevend en klampen zich vast aan de rest van de grafiek vanuit de emmer. Als meer dan de helft van de randen blauw is, verwijder je analoog de rode randen en knooppunten en stop je deze in de blauwe emmer.

Herhaal dit totdat je geen knooppunten meer hebt. (Aangezien de grafiek compleet is, is elk overgebleven knooppunt op elk punt verbonden met beide buckets totdat het in een van hen wordt geplaatst.)

Als je klaar bent, kijk dan in de emmers. Omdat een knooppunt pas in de rode emmer ging nadat zijn blauwe buren waren geëlimineerd, zijn alle knooppunten in de rode emmer met elkaar verbonden door rode randen - ze vormen een rode kliek. Evenzo vormt de blauwe emmer een blauwe kliek. Als uw oorspronkelijke grafiek ten minste $latex 4^k$-knooppunten heeft, is het mogelijk om te bewijzen dat een van deze buckets ten minste k knooppunten, wat een monochromatische kliek in de originele grafiek garandeert.

Dit argument is slim en elegant, maar het laat je twee kliekjes bouwen - een blauwe en een rode - ook al heb je er maar één nodig. Het zou efficiënter zijn om altijd rood te gaan, legde Conlon uit. Bij deze strategie zou je bij elke stap een knooppunt kiezen, de blauwe randen wissen en het in de rode emmer gooien. De rode emmer zou dan snel vollopen en je zou een rode kliek verzamelen k knopen in de helft van de tijd.

Maar je strategie moet werken voor elke rood-blauwe kleuring, en het is moeilijk te weten of je altijd een knooppunt met veel rode randen kunt vinden. Dus als je de suggestie van Conlon volgt, loop je het risico een knooppunt tegen te komen waaraan bijna geen rode randen zijn bevestigd. Dat zou je dwingen om een ​​groot deel van de grafiek in één keer te verwijderen, waardoor je moet klauteren om je kliek op te bouwen voordat je geen knooppunten meer hebt. Om de suggestie van Conlon uit te voeren, moesten Griffiths, Morris en Sahasrabudhe bewijzen dat dit risico te vermijden was.

Een Open Boek Examen

Bij het updaten van hun gameplay volgden Griffiths, Morris en Sahasrabudhe een iets meer omslachtige route. In plaats van direct een monochromatische kliek op te bouwen door knooppunten in hun rode en blauwe emmers te gooien, concentreerden ze zich eerst op het bouwen van een structuur die een rood boek wordt genoemd.

In de grafentheorie bestaat een boek uit twee delen: er is een monochromatische kliek, de 'ruggengraat' genoemd, en een tweede, afzonderlijke cluster van knooppunten die de 'pagina's' worden genoemd. In een rood boek zijn alle randen die knooppunten in de rug verbinden rood, evenals de randen die de rug met de pagina's verbinden. De randen die knooppunten binnen de pagina's verbinden, kunnen echter elke combinatie van kleuren zijn. Conlon had in zijn paper uit 2018 opgemerkt dat als je een rode kliek op de pagina's van een boek kunt vinden, je deze kunt combineren met de ruggengraat om een ​​grotere rode kliek te krijgen. Hiermee kun je een zoektocht naar een grote rode kliek ontleden in twee eenvoudigere zoekopdrachten. Zoek eerst een rood boek. Zoek dan naar een kliek op de pagina's van het boek.

Griffiths, Morris en Sahasrabudhe wilden het spelwinnende algoritme aanpassen zodat het een rood boek bouwde in plaats van een rode kliek. Hoewel ze dit plan slechts enkele weken na hun project hadden vastgesteld, zou het jaren duren om het te laten werken. Ze moesten nog steeds de dreiging afwenden al hun rode randen te verliezen.

"We zaten heel lang vast", zegt Campos, die in 2021 bij het project kwam.

In januari kwamen de vier wiskundigen overeen om over te schakelen naar een andere versie van het probleem. Die versie klinkt ingewikkelder, maar bleek makkelijker.

Al die tijd was het team gefocust op het Ramsey-nummer R(k), ook bekend als het "diagonale" Ramsey-getal. Een grafiek van grootte R(k) moet bevatten k knooppunten, allemaal verbonden door randen van dezelfde kleur, maar het maakt niet uit of die kleur rood of blauw is. Aan de andere kant, het "off-diagonale" Ramsey-getal R(k, l) meet hoe groot een grafiek moet zijn voordat deze een rode kliek met bevat k knooppunten, of een blauwe kliek met l knooppunten. In plaats van door te gaan met het weghakken van het diagonale probleem, besloot de groep de off-diagonale versie te proberen. Dit bleek onthullend.

"Lange tijd voelde het alsof elke deur waar je op duwde ofwel met bouten dicht was, of in ieder geval vrij moeilijk om er doorheen te komen", zei Griffiths. “En na die verandering had je gewoon het gevoel dat elke deur open stond. Op de een of andere manier leek alles gewoon te werken.” In de off-diagonale versie vonden ze een manier om een ​​aantal blauwe randen in één keer te verwijderen volgens een bepaald protocol, waardoor de dichtheid van rode randen toenam, en leidde tot een verbeterde grens aan het off-diagonale Ramsey-getal. Deze methode, een "densiteitstoename" -argument genoemd, werd eerder gebruikt om op te lossen andere belangrijke problemen in de combinatoriek, maar het was niet gebruikt bij het probleem met het Ramsey-nummer.

De vier wiskundigen gebruikten vervolgens de nieuwe grens op het niet-diagonale Ramsey-getal om de weg vrij te maken voor het diagonale resultaat. Begin februari hadden ze eindelijk de limiet op het Ramsey-getal verlaagd met een exponentiële factor, een prestatie waar wiskundigen al bijna een eeuw naar op zoek waren. En ze deden het door dezelfde redenering te moderniseren die Erdős en Szekeres in 1935 naar voren hadden gebracht.

Epsilon, Epsilon

Na de gesprekken op 16 maart begonnen de aanwezigen de geruchten te bevestigen. Foto's van Sahasrabudhe's toespraak circuleerden via telefoontjes en privéberichten - zelfs in een vage maar suggestieve post op de blog van de wiskundige Gil Kalai. Campos, Griffiths, Sahasrabudhe en Morris beweerden te hebben aangetoond dat $latex R(k) < 3.993^k$. Die avond, de vier auteurs plaatsten hun paper online, waardoor wiskundigen het nieuwe bewijs zelf kunnen zien.

"Ik denk dat velen van ons in wezen niet hadden verwacht zo'n verbetering in ons leven te zien," zei Matija Bucic, een wiskundige aan Princeton University en het Institute for Advanced Study. "Ik vind het een absoluut geweldig resultaat."

Veel experts hopen dat, nu de exponentiële barrière is opgeheven, er snel meer vooruitgang zal volgen. De auteurs van het nieuwe artikel hebben hun methode met opzet niet tot het uiterste gedreven, om te voorkomen dat hun betoog wordt vertroebeld met onnodige details. "Ik ben erg geïnteresseerd in hoe ver de methode eigenlijk kan gaan, want ik heb geen idee," zei Campos.

“Het is een buitengewoon ingenieus, absoluut prachtig bewijs en een echte doorbraak. Dus nu verwacht ik dat de sluisdeuren open gaan”, zei Bollobás. “Ik ben ervan overtuigd dat over drie jaar de discussie gaat over mogelijke verbeteringen. Kunnen we 3.993 verbeteren naar 3.9? Misschien naar 3.4? En hoe zit het met 3?

Het nieuwe bewijs komt binnen op 56 pagina's en het zal weken duren voordat elk detail volledig is geverifieerd door de combinatorische gemeenschap. Maar collega's zijn optimistisch. “Deze groep auteurs, het zijn zeer serieuze mensen. En het zijn mensen die heel erg goed zijn in heel technische dingen,' zei Wigderson.

Als het om zijn medewerkers gaat, is Griffiths het daarmee eens. “Het is een voorrecht om met briljante mensen te werken, nietwaar? En ik denk dat ik daar erg dankbaar voor ben', zei hij. "Als ze het aan mij hadden overgelaten, had ik misschien nog vijf jaar nodig gehad om de details goed te krijgen."