Reinforced Generation of Combinatorial Structures: Ramsey Numbers

Dit artikel introduceert AlphaEvolve, een op een groot taalmodel gebaseerd agent dat code mutaties uitvoert en daarmee de ondergrenzen voor vijf klassieke Ramsey-getallen heeft verbeterd, terwijl het tevens bestaande resultaten succesvol reproduceerde en matchte.

De kern

De Grote Zoektocht naar de Perfecte Partij: Een Verhaal over Ramsey-getallen en AI

Stel je voor dat je een gigantische feestzaal organiseert. Je wilt weten: hoeveel mensen moet je minimaal uitnodigen om te garanderen dat er ofwel een groep van 3 vrienden is die elkaar allemaal kennen, ofwel een groep van 13 mensen die elkaar allemaal niet kennen?

In de wiskunde noemen we dit een Ramsey-getal. Het is een soort "wiskundige garantie". Als je minder mensen uitnodigt dan dit getal, kun je de zaal zo inrichten dat je geen van die twee groepen hebt. Maar zodra je dat ene extra persoon toevoegt, is het onmogelijk om die groepen te vermijden.

Het probleem is: voor veel combinaties weten we dit getal niet precies. We weten alleen dat het ergens tussen twee waarden ligt. De auteurs van dit paper hebben een nieuwe manier gevonden om de ondergrens (het minimum aantal mensen) te verhogen. Ze hebben bewezen dat voor bepaalde combinaties je één persoon meer nodig hebt dan men eerder dacht.

De Magische Robot: AlphaEvolve

Hoe hebben ze dit gedaan? Ze hebben niet urenlang met pot en papier getwijfeld. Ze hebben een slimme AI-agent ingeschakeld, genaamd AlphaEvolve.

Stel je AlphaEvolve voor als een meester-kok die continu nieuwe recepten uitvindt.

• Het doel: Een recept vinden dat een perfecte "feestzaal" (een grafiek) maakt zonder dat er ongewenste groepjes (cliques of onafhankelijke sets) ontstaan.
• De methode: De AI begint met een heel simpel, misschien wel foutief recept. Dan zegt ze: "Laten we dit ingrediënt een beetje aanpassen." Ze probeert duizenden variaties.
• De evolutie: Als een recept bijna goed is, maar nog niet perfect, houdt de AI het vast en probeert ze het nog iets te verbeteren. Als een recept slecht is, gooit ze het weg. Dit noemen we evolutie: de beste oplossingen overleven en worden steeds beter.

In plaats van dat een mens een specifiek algoritme schrijft om dit probleem op te lossen, heeft de mens de AI alleen de opdracht gegeven: "Zoek zelf de beste manier om deze grafieken te bouwen." De AI heeft dan zelf de code geschreven om die zoektocht uit te voeren.

De Grote Doorbraken

De onderzoekers hebben met deze AI-agent de volgende "feestzaal-garanties" verbeterd:

• Voor een groep van 3 vrienden en 13 vreemden: vroeger dachten ze dat 60 mensen genoeg waren om een groepje te garanderen. Nu weten we dat je 61 nodig hebt.
• Voor 3 vrienden en 18 vreemden: van 99 naar 100.
• En nog een paar andere combinaties, zoals voor 4 vrienden en 13, 14 of 15 vreemden.

Het klinkt misschien als kleine stapjes (alleen 1 of 2 mensen meer), maar in de wereld van de wiskunde is dit als het vinden van een nieuwe planeet. Het betekent dat we de grenzen van wat mogelijk is, net iets verder hebben geschoven.

Waarom is dit zo speciaal?

Vroeger hadden wiskundigen voor elk specifiek probleem een heel eigen, handgemaakte "zoekmachine" gebouwd. Het was alsof je voor elke nieuwe stad een nieuwe auto moest bouwen.

Met AlphaEvolve hebben ze één meester-robot gemaakt die voor alle deze problemen een nieuwe, eigen zoekmachine kan bouwen.

• Soms begint de AI met een willekeurige groep mensen.
• Soms gebruikt ze slimme wiskundige patronen (zoals een cirkel waar iedereen met zijn buurman praat).
• Soms combineert ze verschillende strategieën op manieren die een mens misschien nooit zou bedenken.

De Analogie van de Schatzoeker

Stel je voor dat je op zoek bent naar een schat (het perfecte getal) op een eiland dat vol zit met gaten (foutieve grafieken).

• De oude manier: Mensen liepen met een kompas en een kaart die ze zelf hadden getekend. Ze wisten precies waar ze moesten graven, maar ze kwamen vaak vast te zitten in een gat.
• De nieuwe manier (AlphaEvolve): Je laat een robot los. De robot probeert duizenden verschillende manieren om te graven. Als hij in een gat valt, krabt hij zich op het hoofd en probeert hij een andere plek. Als hij iets goudkleurigs ziet, bouwt hij daar een huisje en probeert hij dat huisje nog groter te maken.

Deze robot heeft niet alleen de schat gevonden, maar heeft ook bewezen dat de eerdere schatkaarten (de oude wiskundige resultaten) net iets te optimistisch waren.

Conclusie

Dit paper laat zien dat kunstmatige intelligentie niet alleen goed is voor het herkennen van katten op foto's of het schrijven van e-mails. Het kan ook helpen om de grenzen van de wiskunde te verleggen. De AI heeft bewezen dat we voor bepaalde complexe problemen nog niet alles weten, en dat er ruimte is voor nog grotere "feestzalen" zonder ongewenste groepjes.

Het is een bewijs dat als je een slimme robot de juiste vragen stelt, hij soms antwoorden kan vinden die zelfs de slimste mensen in decennia niet hadden kunnen bedenken.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het werk "Reinforced Generation of Combinatorial Structures: Ramsey Numbers" in het Nederlands.

Titel: Versterkte Generatie van Combinatorische Structuren: Ramsey-getallen

Auteurs: Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta (UC Berkeley & Google DeepMind)
Datum: 10 maart 2026

---

1. Het Probleem: Ramsey-getallen

Het paper richt zich op het klassieke probleem van Ramsey-getallen, aangeduid als $R(r, s)$. Dit is het kleinste aantal $n$ zodat elke ongerichte graaf met $n$ knopen ofwel een clique (volledige subgraaf) van grootte $r$ bevat, ofwel een onafhankelijke verzameling (subgraaf zonder kanten) van grootte $s$.

• Huidige staat: Voor kleine waarden van $r$ en $s$ zijn de exacte waarden bekend, maar voor veel andere combinaties bestaan er grote gaten tussen de bekende onder- en bovengrenzen.
• Doel: Het verbeteren van de ondergrenzen. Als men een graaf kan construeren met $n$ knopen die geen clique van grootte $r$ en geen onafhankelijke verzameling van grootte $s$ bevat, dan is bewezen dat $R(r, s) \geq n + 1$.
• Uitdaging: Traditioneel worden deze ondergrenzen berekend met behulp van op maat gemaakte zoekalgoritmen die specifiek zijn ontworpen voor één paar $(r, s)$. Er is geen universele methode die voor alle gevallen werkt.

2. Methodologie: AlphaEvolve

De auteurs gebruiken AlphaEvolve, een agent gebaseerd op Large Language Models (LLM's), om zoekalgoritmen te evolueren in plaats van handmatig te ontwerpen.

• Meta-algoritme: AlphaEvolve onderhoudt een populatie van zoekalgoritmen (code-snippets).
• Evolutiecyclus:
  1. Selectie: Een "ouder"-algoritme wordt geselecteerd op basis van prestatie.
  2. Mutatie: Een LLM genereert een gemuteerde versie van de code.
  3. Executie: Het nieuwe algoritme voert een zoektocht uit en produceert twee grafen:
     • $G_1$: Een primaire graaf die de huidige staat van de kunst (SoTA) probeert te verbeteren.
     • $G_2$: Een "prospect" graaf die groter is, maar mogelijk nog overtredingen (cliques of onafhankelijke verzamelingen) bevat.
  4. Scoren: De score wordt bepaald door de grootte van de geldige graaf ($G_1$), met een zware bonus voor het overschrijden van de huidige ondergrens. Daarnaast wordt $G_2$ beloond als het aantal overtredingen laag is ten opzichte van een willekeurig verwachte baseline. Dit stuurt de zoektocht naar de randen van de oplossingruimte.
• Initiatie strategieën: Het systeem start vaak met een lege graaf of specifieke wiskundige structuren (zoals Paley-graaf of circulaire graaf) en evolueert zoekprocedures die deze structuren uitbreiden.

3. Belangrijkste Bijdragen en Resultaten

Het paper presenteert verbeterde ondergrenzen voor vijf klassieke Ramsey-getallen. Daarnaast werden bestaande ondergrenzen voor alle bekende exacte waarden herontdekt en gematcht.

Verbeterde Ondergrenzen:

• $R(3, 13)$: Verhoogd van 60 naar 61.
• $R(3, 18)$: Verhoogd van 99 naar 100.
• $R(4, 13)$: Verhoogd van 138 naar 139.
• $R(4, 14)$: Verhoogd van 147 naar 148.
• $R(4, 15)$: Verhoogd van 158 naar 159.

Algoritmische Innovaties:
De door AlphaEvolve ontdekte algoritmen voor deze resultaten vertonen unieke kenmerken die verschillen van eerdere menselijke benaderingen:

1. Hybride Initiatie: Het gebruik van specifieke algebraïsche structuren (zoals cubic residue-graaf of Paley-graaf) als startpunt, gevolgd door stochastische zoektochten.
2. Gecombineerde Heuristieken: In plaats van één simpele methode (zoals gesimuleerde afkoeling), keten de gevonden algoritmen meerdere heuristieken (bijv. Tabu-search, genetische algoritmen, en lokale zoektochten) aan elkaar.
3. Geavanceerde Optimalisatie:
   • Adaptieve straffen: Dynamische aanpassing van gewichten voor het tellen van driehoeken versus onafhankelijke verzamelingen.
   • Delta-updates: Efficiënte berekening van veranderingen in het aantal cliques bij het omdraaien van een rand, zonder de hele graaf opnieuw te scannen.
   • Strategische "Kicks": Mechanismen om uit lokale minima te ontsnappen door willekeurige randflips toe te passen wanneer de zoektocht stagneert.

4. Vergelijking met Eerdere Werk

• Verschil in aanpak: Eerdere werken (zoals Exoo et al.) gebruikten vaak specifieke, handmatig ontworpen heuristieken of gesimuleerde afkoeling voor één specifiek probleem. AlphaEvolve automatiseert het ontdekken van de heuristiek zelf.
• Resultaat: Hoewel sommige initiatie-strategieën (zoals het gebruik van algebraïsche graafstructuren) overeenkomen met eerdere werk, zijn de daaropvolgende optimalisatiestrategieën vaak fundamenteel anders en soms compleet nieuw (bijv. voor $R(4, 10)$).
• Efficiëntie: De gevonden algoritmen zijn vaak sneller of effectiever omdat ze specifiek zijn "getraind" op de structuur van het specifieke Ramsey-probleem, in plaats van een generieke zoektocht.

5. Betekenis en Toekomstperspectief

• Automatisering van Wiskundig Ontdekken: Dit werk toont aan dat LLM-based agents niet alleen bestaande theorieën kunnen samenvatten, maar actief nieuwe zoekalgoritmen kunnen genereren die leiden tot nieuwe wiskundige resultaten op het gebied van extremale combinatoriek.
• Universele Meta-algoritme: In tegenstelling tot eerdere benaderingen waarbij voor elk Ramsey-getal een nieuw script nodig was, fungeert AlphaEvolve als één meta-algoritme dat zoekprocedures genereert voor een breed scala aan $(r, s)$-paren.
• Beperkingen: De huidige focus ligt op ondergrenzen (het construeren van voorbeelden). Het verbeteren van bovengrenzen (het bewijzen dat een grotere graaf onmogelijk is) vereist een fundamenteel andere aanpak (zoals formele verificatie) en is niet opgelost door deze methode.

Conclusie:
Dit paper markeert een mijlpaal in het gebruik van AI voor wiskundig onderzoek. Door AlphaEvolve in te zetten, hebben de auteurs niet alleen de ondergrenzen voor vijf belangrijke Ramsey-getallen verbeterd, maar ook aangetoond dat geautomatiseerde code-evolutie complexe, menselijke zoekstrategieën kan overtreffen en nieuwe, efficiëntere methoden kan ontdekken voor het vinden van extremale combinatorische objecten.