A note on Ramsey numbers for minors

Dit artikel bepaalt de asymptotische gedragsgrenzen voor Ramsey-getallen gerelateerd aan de Hadwiger-getallen van monochromatische grafieken in een complete graaf met twee of meer kleuren.

De kern

Samenvatting: Een wiskundig avontuur over kleuren, netwerken en onontkoombare patronen

Stel je voor dat je een gigantisch feest organiseert met honderden gasten. Je wilt dat iedereen elkaar ontmoet, dus je laat iedereen met iedereen handdrukken. Nu doe je een spelletje: je geeft elke handdruk een kleur, bijvoorbeeld rood of blauw.

De vraag die deze paper beantwoordt is: Hoe groot moet het feest zijn voordat je gegarandeerd een groep mensen vindt die allemaal met elkaar handdrukken in dezelfde kleur, en die groep is zo sterk verbonden dat je ze kunt "samenvoegen" tot één super-persoon?

Hier is de uitleg, vertaald naar alledaagse taal:

1. Het Spel: Ramsey-getallen en "Minors"

In de wiskunde bestaat er een beroemd spelletje genaamd Ramsey-theorie. De regel is simpel: als je genoeg mensen hebt en je kleurt hun connecties willekeurig, dan moet er vroeg of laat een patroon ontstaan dat je niet kunt vermijden.

Normaal gesproken zoek je naar een groepje dat er precies hetzelfde uitziet (een "clique"). Maar in dit artikel kijken we naar iets iets flexibels: de Hadwiger-getal (of "minor").

• De Analogie: Stel je hebt een groep mensen die allemaal met elkaar praten (een clique). Een "minor" is alsof je een paar mensen uit de groep laat vertrekken en een paar anderen samenvoegt tot één "super-persoon". Als je na al dat samenvoegen en verwijderen nog steeds een groep overhoudt die met elkaar praat, dan heb je een "minor" gevonden.
• Het doel: De auteurs willen weten: Hoe groot moet het feest (het aantal gasten $n$) zijn, zodat je altijd een groep vindt die, na wat samenvoegen, een groep van $k$ super-persoonnetjes vormt, en dat allemaal in één kleur?

2. De Grote Vraag: Hoeveel gasten zijn er nodig?

De auteurs, geleid door Maria Axenovich, hebben een formule gevonden die vertelt hoeveel gasten je nodig hebt. Ze kijken naar twee situaties:

• Situatie A (Kleuren met 2 kleuren): Je gebruikt alleen rood en blauw.
• Situatie B (Kleuren met $\ell$ kleuren): Je gebruikt veel meer kleuren (bijvoorbeeld regenboogkleuren).

Ze ontdekten dat het aantal gasten dat je nodig hebt, groeit met de grootte van de groep die je zoekt ($k$), maar niet lineair. Het is een beetje zoals het vullen van een badkuip: als je de kuip groter maakt, heb je niet alleen meer water nodig, maar de vorm van de kuip verandert ook.

De formule die ze vonden ziet er ongeveer zo uit:
$$\text{Aantal gasten} \approx \text{Een constante} \times k \times \sqrt{\log(k)}$$

Wat betekent dit?

• Als je een groep van 10 super-persoonnetjes wilt, heb je een bepaald aantal gasten nodig.
• Als je een groep van 100 wilt, heb je veel meer gasten nodig, maar niet exponentieel meer. De $\sqrt{\log(k)}$-term zorgt ervoor dat het getal "behoedzaam" groeit.

3. De "Magische" Constante

De auteurs hebben een heel specifieke getal gevonden, laten we hem $\beta$ noemen (ongeveer 0,265).

• Voor twee kleuren is het aantal gasten ongeveer $1,031 \times k \times \sqrt{\log k}$.
• Voor veel kleuren ($\ell$) is het aantal gasten ongeveer $2 \times \beta \times \ell \times k \times \sqrt{\log k}$.

Dit betekent dat als je meer kleuren gebruikt, het feest groter moet zijn om die onontkoombare groep te vinden. Het is alsof je met meer kleuren de "rode" en "blauwe" patronen kunt verspreiden, waardoor het moeilijker wordt om een grote, eenduidige groep te vinden.

4. Hoe hebben ze dit bewezen? (De Wiskundige Magie)

De auteurs gebruiken twee hoofdstijlen om hun bewijs te leveren:

• De "Willekeurige Feest" Strategie (Ondergrens):
  Stel je voor dat je een feest organiseert waar elke handdruk willekeurig rood of blauw is. Ze tonen aan dat als het feest te klein is, je met grote kans geen grote groep vindt die samengevoegd kan worden. Dit bewijst dat je minimaal zoveel gasten nodig hebt. Ze gebruiken hier een wiskundig model van een "willekeurig netwerk" (Erdős-Rényi grafiek).

• De "Dichtheids" Strategie (Bovengrens):
  Hier kijken ze naar het tegenovergestelde. Als het feest groot genoeg is, dan moet er in de "meest populaire" kleur (bijvoorbeeld rood) zo veel connecties zijn, dat het onmogelijk is om geen grote groep te vinden. Ze gebruiken een bekend resultaat van de wiskundige Thomason: als een netwerk genoeg verbindingen heeft, kun je er altijd een grote "minor" uit halen. Ze hebben dit resultaat verfijnd om de exacte grens te vinden.

5. Kleine Feestjes (Speciale Gevallen)

Voor heel kleine groepen (bijvoorbeeld $k=3$ of $k=4$) hebben ze de exacte antwoorden gevonden:

• Voor een groep van 3 (een driehoekje) heb je 5 gasten nodig bij 2 kleuren.
• Voor een groep van 4 heb je 7 gasten nodig.
  Ze hebben dit bewezen door alle mogelijke kleurpatronen voor deze kleine aantallen handmatig te checken. Het is als het oplossen van een Sudoku: je probeert elke combinatie om te zien of je de patroon kunt vermijden.

6. Waarom is dit belangrijk?

Dit artikel vult een gat in de wiskunde. Er is al veel onderzoek gedaan naar de Hadwiger-vermoeden (een beroemd probleem dat zegt dat als een netwerk complex genoeg is, je er een grote clique uit kunt halen). Maar niemand had eerder expliciet gekeken naar wat er gebeurt als je de verbindingen in verschillende kleuren verdeelt.

De auteurs laten zien dat zelfs als je probeert de patronen te verspreiden over verschillende kleuren, de wiskunde er altijd voor zorgt dat op een bepaald punt een grote, sterke structuur ontstaat.

Kortom:
Of je nu een feest organiseert, een sociaal netwerk bouwt of een computerchips ontwerpt: als je genoeg elementen hebt en je probeert ze te "verkleuren", kun je niet voorkomen dat er een grote, sterk verbonden groep ontstaat. De auteurs hebben precies berekend hoe groot die groep moet zijn voordat dit onvermijdelijk gebeurt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "A note on Ramsey numbers for minors" van Maria Axenovich, geschreven in het Nederlands.

Titel: Aantekening over Ramsey-getallen voor minor

Auteur: Maria Axenovich (Karlsruhe Institute of Technology)
Datum: 12 maart 2026 (gepubliceerd op arXiv:2603.10510)

---

1. Probleemstelling en Context

Het paper onderzoekt een variant van het klassieke Ramsey-getal, specifiek gericht op de Hadwiger-getal (Hadwiger number) in plaats van de clique-grootte.

• Definitie: Laat $R_h(k; \ell)$ het kleinste gehele getal $n$ zijn zodanig dat elke $\ell$-kleurige randkleuring van de volledige graaf $K_n$ resulteert in een monochromatische subgraaf met een Hadwiger-getal van minstens $k$.
• Hadwiger-getal $h(G)$: Dit is de grootste $k$ zodanig dat de graaf $G$ een $K_k$-minor bevat. Een $K_k$-minor kan worden verkregen uit $G$ door een reeks randcontracties en vertexverwijderingen.
• Doel: Het paper beoogt de asymptotische gedrag van $R_h(k; \ell)$ te bepalen, met name voor het geval van twee kleuren ($\ell=2$) en voor een groot aantal kleuren ($\ell \to \infty$). Hoewel de Hadwiger-conjecture (die stelt dat $h(G) \ge \chi(G)$) veel bestudeerd is, was de specifieke Ramsey-variant voor minors tot nu toe niet expliciet in de literatuur behandeld.

2. Methodologie en Theoretische Basis

De auteur combineert bestaande resultaten uit de extremale grafentheorie en probabilistische methoden om nieuwe grenzen af te leiden. De kern van de bewijstechniek rust op de volgende pijlers:

1. Dichtheidsresultaten (Thomason): Het paper maakt gebruik van Thomason's asymptotische bepaling van de minimale gemiddelde graad $c(k)$ die nodig is om een $K_k$-minor te garanderen.
   • $c(k) = \beta k \sqrt{\log k} (1 + o(1))$, waarbij $\beta \approx 0.265656$.
2. Probabilistische Methode: Voor de ondergrenzen wordt gebruikgemaakt van willekeurige grafen $G(n, p)$ en willekeurige kleuringen. Het paper citeert Bollobás, Catlin en Erdős om te tonen dat willekeurige grafen een Hadwiger-getal hebben dat lager is dan $k$ bij bepaalde dichtheden.
3. Structuuranalyse en Connectiviteit: Voor de bovengrenzen wordt een verfijnde analyse uitgevoerd van de connectiviteit en de dichtheid van de grootste kleurgroep. De auteur onderscheidt gevallen op basis van:
   • Hoge connectiviteit (toepassing van Thomason's stelling 1.3).
   • Bestaan van geïnduceerde subgrafen met hoge minimale graad.
   • Het verwijderen van vertices met lage graad om een subgraaf met hoge dichtheid over te houden.
4. Packing en Decompositie: Voor de ondergrenzen bij veel kleuren ($\ell$) wordt gebruikgemaakt van stellingen over het packen van grafen in $K_n$ (Wilson's theorema en resultaten van Alon en Yuster) om een kleuring te construeren zonder monochromatische $K_k$-minors.

3. Belangrijkste Resultaten

Het paper presenteert scherpe asymptotische grenzen voor $R_h(k; \ell)$.

A. Het geval met twee kleuren ($\ell = 2$)

De auteur bewijst dat:
$$k \sqrt{\log k} (1 + o(1)) \le R_h(k; 2) \le 1.031 \cdot k \sqrt{\log k} (1 + o(1))$$

• Ondergrens: Verkregen door een willekeurige 2-kleuring van $K_n$ te beschouwen waarbij $n \approx k \sqrt{\log k}$. Met hoge waarschijnlijkheid heeft geen enkele kleur een $K_k$-minor.
• Bovengrens: Een eerste ruwe schatting gaf een constante van ongeveer $1.062$. Door een verfijnd argument te gebruiken dat rekening houdt met connectiviteit en het verwijderen van vertices met lage graad, wordt deze constante verbeterd tot 1.031.
• Specifieke waarden:
  • $R_h(3) = 5$
  • $R_h(4) = 7$
  • Voor $k \ge 5$: $2(k-2) \le R_h(k) \le 32(k-2)^{\lfloor \log(k-2) \rfloor + 1}$.

B. Het geval met $\ell$ kleuren

Voor een groot aantal kleuren $\ell$ en grote $k$ wordt de volgende asymptotische formule afgeleid:
$$R_h(k; \ell) = 2\beta \ell k \sqrt{\log k} (1 + o(1))$$
waarbij $\beta \approx 0.265656$.

• Dit betekent dat $R_h(k; \ell)$ lineair groeit met het aantal kleuren $\ell$.
• Voor kleine $k$ (specifiek $k=3$) geldt exact: $R_h(3; \ell) = 2\ell + 1$.

4. Bijdragen en Significatie

1. Eerste expliciete behandeling: Dit paper is de eerste die de Ramsey-getallen voor Hadwiger-getallen ($R_h(k)$) systematisch onderzoekt en formuleert, een gebied dat eerder niet expliciet in de literatuur was opgepakt ondanks de relevantie voor de Hadwiger-conjecture.
2. Verbetering van constanten: De auteur verbetert de constante in de bovengrens voor $R_h(k; 2)$ aanzienlijk (van $\approx 1.06$ naar $\approx 1.031$) door een meer genuanceerde analyse van de structuur van de grootste kleurgroep.
3. Asymptotische precisie: Het paper levert een nauwkeurige asymptotische vorm voor het geval met veel kleuren, waarbij de constante $2\beta$ wordt geïdentificeerd.
4. Verbinding van theorieën: Het werk verbindt succesvol de theorie van grafenminors (Hadwiger), extremale grafentheorie (dichtheidsresultaten van Thomason) en Ramsey-theorie.

5. Conclusie en Toekomstperspectief

De auteur concludeert dat $R_h(k; 2) \sim c k \sqrt{\log k}$ met een constante $c$ die zeer waarschijnlijk gelijk is aan 1. Hoewel de huidige bovengrens $1.031$is, gelooft de auteur dat er een eenvoudigere, directe bewijsvoering mogelijk is voor een bovengrens met een constante$c$ (misschien zelfs groter dan 1, maar zonder gebruik te maken van de complexe dichtheidsstelling van Thomason).

Het paper suggereert ook alternatieve methoden voor het bewijzen van ondergrenzen door het packen van $H$-factoren (waarbij $H$ een graaf is zonder $K_k$-minor) in $K_n$, gebruikmakend van stellingen van Messuti, Rödl en Schacht.

Samenvattend: Dit paper vult een gat in de grafentheorie door de Ramsey-eigenschappen van minors te kwantificeren en levert de eerste scherpe asymptotische schattingen voor deze belangrijke parameter.