New Upper Bounds for the Classical Ramsey Numbers $R(4,4,4)$, $R(3,4,5)$ and $R(3,3,6)$

Dit artikel presenteert nieuwe, strengere bovengrenzen voor de klassieke Ramsey-getallen $R(4,4,4)$, $R(3,4,5)$ en $R(3,3,6)$ die de tot nu toe beste schattingen, die voornamelijk op een standaard ongelijkheid waren gebaseerd, verbeteren.

De kern

Wiskundige Vrienden en de Onmogelijke Feestjes: Een Uitleg van het Nieuwe Ramsey-Bewijs

Stel je voor dat je een gigantisch feestje organiseert. Je hebt een enorme groep mensen uitgenodigd en je wilt ze allemaal met elkaar laten praten. Maar er is een probleem: je hebt maar drie soorten drankjes (rood, blauw en groen) en je wilt voorkomen dat er een groepje mensen is die allemaal hetzelfde drankje drinkt en zich zo goed vermaakt dat ze een eigen, gesloten clubje vormen.

In de wiskunde noemen we dit een Ramsey-getal. Het is het kleinste aantal mensen dat je nodig hebt om te garanderen dat, hoe je de drankjes ook verdeelt, er altijd wel een groepje is dat zich "te goed" vermaakt in één kleur.

De auteur van dit artikel, Luis Boza, heeft een nieuwe manier gevonden om te voorspellen hoeveel mensen je maximaal nodig hebt voor drie specifieke, lastige scenario's. Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. De oude manier: De "Schatting"

Voor decennia gebruikten wiskundigen een simpele, maar saaie formule om deze aantallen te schatten. Het was alsof je probeerde te raden hoe zwaar een olifant is door te zeggen: "Oké, een olifant is zwaarder dan een koe, en een koe is zwaarder dan een hond, dus de olifant is... eh, heel zwaar."

Deze formule gaf een bovengrens (een maximum), maar vaak was die grens te hoog. Het was alsof je zei: "Je hebt maximaal 1000 mensen nodig," terwijl je in werkelijkheid misschien maar 900 nodig had. De wiskundigen wisten dat ze beter konden doen, maar ze hadden geen betere manier om dat te bewijzen.

2. De nieuwe truc: De "Drie-Kleuren-Check"

Boza heeft een slimme nieuwe truc bedacht. Hij kijkt niet alleen naar het totale aantal mensen, maar ook naar de restantjes als je door 3 deelt.

Stel je voor dat je een taart hebt die je in stukken wilt snijden. De oude formule zei: "De taart is groot genoeg voor 100 mensen." Boza kijkt echter naar de restjes: "Als we de taart in drieën delen, blijft er altijd een stukje over dat niet perfect past. Dat betekent dat de taart eigenlijk iets kleiner is dan we dachten!"

Zijn nieuwe regel (Theorema 2.1) werkt als volgt:

• Als je de berekening doet en het getal is niet precies 1 meer dan een veelvoud van 3 (bijvoorbeeld 10, 11, 13, maar niet 10, 13, 16... wacht, 10 is 1 meer dan 9, dus 10 is 1 mod 3. Laten we het zo zeggen: als het getal een bepaalde "ritme" mist in de rij van 3, 6, 9, 12...), dan kun je de schatting met één verlagen.
• Het is alsof je merkt dat je de laatste stoel op een feestje toch niet nodig hebt, omdat de geometrie van de tafel het niet toelaat dat iedereen tegelijk zit.

3. De drie grote doorbraken

Met deze nieuwe "ritme-check" heeft Boza drie belangrijke getallen verbeterd:

• R(4, 4, 4): Dit gaat over een feestje met 3 kleuren, waarbij we zoeken naar een groepje van 4 mensen die allemaal dezelfde kleur hebben.

  • Oude grens: 230 mensen.
  • Nieuwe grens: 229 mensen.
  • Betekenis: Je hoeft dus 1 persoon minder uit te nodigen om te garanderen dat er een groepje van 4 is.

• R(3, 4, 5): Hier zoeken we naar een groepje van 3 in kleur 1, 4 in kleur 2 en 5 in kleur 3.

  • Oude grens: 158 mensen.
  • Nieuwe grens: 157 mensen.

• R(3, 3, 6): Twee groepjes van 3 en één van 6.

  • Oude grens: 92 mensen.
  • Nieuwe grens: 91 mensen.

4. Waarom is dit belangrijk?

Je zou kunnen denken: "Oké, één persoon minder, wat maakt dat uit?"

In de wereld van de wiskunde is dit als het vinden van de laatste puzzelstukjes. Het toont aan dat we de fundamentele regels van "chaos en orde" beter begrijpen. Het laat zien dat de oude, simpele formules niet het hele verhaal vertellen. Boza heeft laten zien dat er een verborgen structuur zit in deze getallen, net zoals er een verborgen ritme zit in muziek dat je pas hoort als je goed luistert.

Samenvattend:
Luis Boza heeft een nieuwe, slimme manier gevonden om te tellen hoeveel mensen je nodig hebt op een feestje om te voorkomen dat iedereen in één kleur zit. Door te kijken naar de "restjes" bij het delen door 3, heeft hij bewezen dat we voor drie specifieke situaties één persoon minder nodig hebben dan we dachten. Het is een kleine stap voor de getallen, maar een grote sprong voor ons inzicht in hoe de wiskunde van groepen en kleuren in elkaar zit.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "New Upper Bounds for the Classical Ramsey Numbers R(4, 4, 4), R(3, 4, 5) and R(3, 3, 6)" van Luis Boza, geschreven in het Nederlands.

Titel: Nieuwe bovengrenzen voor de klassieke Ramsey-getallen $R(4, 4, 4)$, $R(3, 4, 5)$ en $R(3, 3, 6)$

1. Probleemstelling

Het paper richt zich op het bepalen van de klassieke multikleur Ramsey-getallen $R(k_1, \dots, k_r)$. Dit getal is gedefinieerd als het kleinste gehele getal $N$ zodanig dat elke $r$-kleurige kleuring van de randen van de volledige graaf $K_N$ minstens één monochromatische clique $K_{k_i}$ van kleur $i$ bevat.

Hoewel exacte waarden voor veel kleine gevallen bekend zijn (bijv. $R(3,3)=6$, $R(3,4)=9$), zijn de waarden voor grotere parameters, en zeker voor $r \ge 3$ kleuren, extreem moeilijk te bepalen. Voor dergelijke gevallen zijn de beste bekende bovengrenzen tot nu toe bijna uitsluitend afgeleid uit een standaard ongelijkheid (Theorema 1.1), die een recursieve relatie gebruikt tussen Ramsey-getallen met verschillende parameters. Het paper onderzoekt of deze standaardgrenzen kunnen worden verbeterd voor specifieke gevallen.

2. Methodologie

De auteur bouwt voort op de bekende recursieve bovengrens, gedefinieerd als:
$$P(k_1, \dots, k_r) = 2 - r + \sum_{i=1}^{r} R(k_1, \dots, k_i-1, \dots, k_r)$$
Volgens Theorema 1.1 geldt $R(k_1, \dots, k_r) \le P(k_1, \dots, k_r)$. De ongelijkheid is strikt als de rechterkant even is en ten minste één term in de som even is.

De kern van de nieuwe methodologie ligt in Theorema 2.1, dat een criterium biedt om de bovengrens met 1 te verlagen ($R \le P - 1$) onder specifieke voorwaarden die te maken hebben met modulariteit (modulo 3). De redenering is als volgt:

1. Aanname: Stel dat $R(k_1, \dots, k_r) = P(k_1, \dots, k_r)$. Dit impliceert het bestaan van een kleuring van $K_{P-1}$ zonder monochromatische cliques.
2. Graafanalyse: Voor een willekeurige hoekpunt $v$ in zo'n graaf $G$, wordt het aantal buren met kleur $i_0$ genoteerd als $d_{i_0}(v)$. Uit Lemma 1.2 volgt dat als $n = P-1$, de graaf regulair is in elke kleur en het aantal buren exact gelijk is aan $R(\dots, k_{i_0}-1, \dots) - 1$.
3. Telling van driehoeken: Het paper analyseert het aantal driehoeken van kleur $i_0$ in de graaf. Het aantal driehoeken dat een hoekpunt $v$ bevat, wordt berekend op basis van de randen in de subgraaf $G[N_{i_0}(v)]$.
4. Modulair Argument: De totale som van driehoeken over alle hoekpunten moet een veelvoud van 3 zijn (omdat elke driehoek 3 keer wordt geteld). De auteur toont aan dat onder de voorwaarden van Theorema 2.1:
   • $P(k_1, \dots, k_r) - 1$ niet deelbaar is door 3.
   • De factoren die het aantal driehoeken bepalen, ook niet deelbaar zijn door 3.
   • Dit leidt tot een contradictie, omdat het product van niet-door-3-deelbare getallen niet deelbaar kan zijn door 3.
5. Conclusie: De aanname dat $R = P$ is onjuist. Daarom moet $R \le P - 1$.

De voorwaarden voor dit theorema zijn:

• $P(k_1, \dots, k_r) \not\equiv 1 \pmod 3$.
• Er bestaat een $i_0$ met $k_{i_0} \ge 4$ zodanig dat de onderliggende Ramsey-waarde gelijk is aan de onderliggende $P$-waarde en deze niet $\equiv 1 \pmod 3$.
• Een gerelateerde term met $k_{i_0}-2$ is ook niet $\equiv 1 \pmod 3$.

3. Belangrijkste Bijdragen en Resultaten

De auteur past Theorema 2.1 toe op specifieke klassieke Ramsey-getallen om nieuwe, strengere bovengrenzen te verkrijgen die niet uit de standaard recursie volgen:

• $R(4, 4, 4) \le 229$:
  De standaardgrens was $R_3(4) \le 230$. De auteur toont aan dat $P_3(4) = 230$ en dat aan alle voorwaarden van Theorema 2.1 wordt voldaan (o.a. omdat $R(3,4,4)=77 \not\equiv 1 \pmod 3$). Hierdoor wordt de bovengrens verlaagd naar 229.

• $R(3, 4, 5) \le 157$:
  De standaardgrens was 158. Door de relatie met $R(3,3,5)=57$ en $R(3,4,4)=77$ te analyseren, wordt aangetoond dat $P(3,4,5)=158$ niet $\equiv 1 \pmod 3$, wat leidt tot de verbetering naar 157.

• $R(3, 3, 6) \le 91$:
  De standaardgrens was 92. Met gebruikmaking van $R(3,3,5)=57$ en $R(3,6)=18$, wordt bewezen dat $P(3,3,6)=92$, wat leidt tot de nieuwe bovengrens van 91.

• $R(3, \dots, 3, 4) \le 608.152.553$ (met 10 keer '3'):
  Voor het geval met 11 kleuren ($r=11$,其中 10 keer $k=3$ en 1 keer $k=4$), wordt een zeer grote numerieke bovengrens verbeterd van 608.152.554 naar 608.152.553. Dit vereist een uitgebreide keten van eerdere resultaten en recursieve toepassingen.

4. Betekenis en Conclusie

Dit paper is significant omdat het een van de weinige gevallen is waarin de klassieke, decennia oude bovengrenzen voor Ramsey-getallen met $r \ge 3$ kleuren zijn verbeterd zonder gebruik te maken van complexe computerberekeningen of constructieve tegenvoorbeelden, maar puur door een verfijning van de theoretische ongelijkheden via modulariteit.

• Theoretische Vooruitgang: Het paper toont aan dat de standaard recursieve formule $P(k_1, \dots, k_r)$ niet altijd de scherpst mogelijke bovengrens is, zelfs niet wanneer de bekende strikte ongelijkheid (voor even getallen) niet van toepassing is.
• Beperking: De auteur merkt op dat verdere verbeteringen voor andere combinaties (zoals $R(3, \dots, 3, 5)$ of $R(3, \dots, 3, 4, 4)$) met $r \le 10$ niet mogelijk zijn met deze specifieke methode, omdat de voorwaarden van Theorema 2.1 niet worden vervuld.
• Impact: De resultaten sluiten de kloof tussen bekende onder- en bovengrenzen voor deze specifieke getallen iets in en bieden een nieuwe analytische tool voor toekomstig onderzoek in de Ramsey-theorie.

Samenvattend introduceert Boza een krachtig modulariteitsargument dat de bekende bovengrenzen voor $R(4,4,4)$, $R(3,4,5)$ en $R(3,3,6)$ respectievelijk met 1 verlaagt, wat een zeldzame en waardevolle verbetering is in dit gebied van de combinatoriek.