Thresholds for colouring the random Borsuk graph

Dit artikel bepaalt de drempelwaarden voor het kleurengtal van het willekeurige Borsuk-graaf en toont aan dat de overgang van $k$-kleurbaarheid naar meer dan $k$ kleuren plaatsvindt bij een constante gemiddelde graad, met name met een scherpe drempel voor $k=2$ die wordt uitgedrukt via de kritieke intensiteit van continue AB-percolatie.

De kern

Stel je voor dat je een gigantische, perfecte bal hebt (zoals de Aarde, maar dan wiskundig perfect). Op deze bal plonzen we duizenden punten willekeurig neer, alsof je een zak met confetti over de wereldkaart gooit. Dit is het begin van het verhaal van dit onderzoek.

Nu gaan we een spelletje spelen: we verbinden twee punten met een lijn (een "rand" of "edge") als ze bijna aan de andere kant van de bal liggen. Als twee punten heel dicht bij elkaar zijn, verbinden we ze niet. Maar als ze bijna elkaars spiegelbeeld zijn (antipodaal), maken we een verbinding.

De vraag die de onderzoekers willen beantwoorden is: Hoeveel kleuren heb je nodig om deze hele bal in te kleuren, zodat twee verbonden punten nooit dezelfde kleur hebben?

In de wiskunde heet dit het "chromatisch getal".

Het Grote Geheim: De "Temperatuur" van de Bal

De onderzoekers ontdekken dat het antwoord afhangt van hoe groot je "bijna" hebt gekozen. Laten we dit vergelijken met het regelen van een feestje:

1. De koude winter (Weinig verbindingen):
   Als je de regels heel streng maakt (alleen punten die extreem dicht bij hun spiegelbeeld liggen mogen een lijn hebben), dan zijn er maar heel weinig lijnen. Je kunt de hele bal makkelijk inkleuren met weinig kleuren. Het is een rustig feestje.

2. De warme zomer (Veel verbindingen):
   Als je de regels losser maakt (punten die "een beetje" ver weg zijn mogen ook een lijn hebben), dan worden er ineens heel veel lijnen getrokken. Plotseling heb je veel meer kleuren nodig om het chaos op te lossen.

De onderzoekers hebben nu precies uitgezocht wanneer die omslag plaatsvindt. Het is alsof ze een thermometer hebben die precies aangeeft op welk moment het feestje van "rustig" naar "chaotisch" springt.

De Drie Belangrijkste Ontdekkingen

Hier zijn de drie grote conclusies, vertaald naar alledaagse taal:

1. De "Thermodynamische" Omslag (Theorema 1)

Vroeger dachten mensen dat je pas veel kleuren nodig had als er ontzettend veel lijnen waren (zoals een drukke stad met miljoenen wegen).
De onderzoekers zeggen: "Nee, dat is niet waar!"
Zij tonen aan dat je al veel meer kleuren nodig hebt (namelijk $d+1$ kleuren) zodra er een constant aantal verbindingen per punt is.

• Analogie: Stel je voor dat je een groep vrienden hebt. Je dacht dat je pas in de war zou raken als iedereen met iedereen praatte. Maar de onderzoekers zeggen: "Zelfs als elke persoon maar met een paar vaste vrienden praat, is het al zo complex dat je meer kleuren (persoonlijkheden) nodig hebt om de groep te ordenen dan je dacht."

2. De Twee-Kleuren Grens (Theorema 2)

Dit is misschien wel het coolste deel. Ze kijken specifiek naar het moment waarop je niet meer met twee kleuren (bijvoorbeeld rood en blauw) kunt werken.
Ze ontdekken dat dit gebeurt op een heel specifiek moment, en dat dit moment precies te voorspellen is met een formule die lijkt op een bekend fenomeen uit de natuurkunde: percolatie.

• Analogie: Denk aan koffie die door een filter druppelt. Als de koffie te dun is, loopt hij niet door. Als hij dik genoeg is, druppelt hij plotseling door.
  Bij deze bal is het hetzelfde: als de "dikte" van de verbindingen een bepaalde drempel overschrijdt, ontstaat er plotseling een oneindige lus (een cirkel van punten die je niet met twee kleuren kunt kleuren). Dit is als een "kloof" in de koffie die plotseling openbreekt. De onderzoekers hebben de exacte maat voor die kloof gevonden.

3. De "Bijna Perfecte" Voorspelling (Theorema 4)

Voor de andere situaties (waar je 3, 4, of meer kleuren nodig hebt) kunnen ze niet zeggen "het gebeurt precies bij punt X". Maar ze zeggen wel: "Het gebeurt bijna altijd bij punt X."

• Analogie: Stel je voor dat je een horloge hebt dat soms 1 seconde voorloopt en soms 1 seconde achterloopt. Je kunt niet zeggen "het is altijd precies 12:00", maar je kunt wel zeggen: "Voor bijna alle dagen klopt de tijd wel binnen een fractie van een seconde." De onderzoekers hebben bewezen dat voor bijna alle aantallen punten, de omslag naar meer kleuren op een heel scherp moment gebeurt.

Waarom is dit belangrijk?

Dit klinkt misschien als abstract wiskundig gezeur, maar het helpt ons om complexe netwerken te begrijpen.

• In de echte wereld: Denk aan communicatienetwerken, sociale media, of zelfs hoe moleculen in een stof met elkaar interageren.
• De les: Soms denk je dat een systeem pas instabiel wordt als het heel druk is. Maar dit onderzoek toont aan dat zelfs bij een gemiddelde druk (niet extreem veel, maar ook niet weinig) de structuur van het netwerk fundamenteel verandert.

Samenvattend in één zin:

De onderzoekers hebben bewezen dat op een willekeurige bal, het moment waarop het "kleurprobleem" onoplosbaar wordt, niet gebeurt als de bal volgepropt is, maar al bij een veel lagere, constante dichtheid van verbindingen, en dat dit moment met wiskundige precisie te voorspellen is.

Het is alsof ze de exacte temperatuur hebben gevonden waarop water niet meer vloeibaar is, maar al bij een temperatuur die we dachten dat het nog gewoon water was.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Thresholds for colouring the random Borsuk graph" in het Nederlands.

Titel: Drempels voor het kleuren van de willekeurige Borsuk-grafiek

Auteurs: Álvaro Acitores Montero, Matthias Irlbeck, Tobias Müller, Matěj Stehlík
Datum: 6 maart 2026

---

1. Probleemstelling en Context

Het artikel onderzoekt het chromatische getal ($\chi$) van de willekeurige Borsuk-grafiek, aangeduid als $G(n, \alpha)$.

• Definitie: De grafiek heeft $n$ knopen die onafhankelijk en uniform willekeurig zijn gekozen op de $d$-dimensionale sfeer $S^d$. Twee knopen $u, v$ zijn verbonden door een rand dan en slechts dan als hun geodetische afstand $dist(u, v) > \pi - \alpha$. De parameter $\alpha = \alpha(n)$ bepaalt hoe "antipodaal" de verbonden punten moeten zijn (kleine $\alpha$ betekent dat punten bijna tegenover elkaar liggen).
• Achtergrond: De klassieke Borsuk-grafiek (niet-willekeurig) heeft een chromatisch getal van $d+2$ voor voldoende kleine $\alpha$. Kahle en Martinez-Figueroa ([21]) hebben eerder aangetoond dat de overgang van $(d+1)$-kleurbaar naar $\ge d+2$ kleuren plaatsvindt in het regime waar het gemiddelde graad van de orde van $\ln n$ is (logaritmisch).
• Doel van dit onderzoek: De auteurs willen de drempels bepalen waarbij de grafiek overgaat van $k$-kleurbaar naar het nodig hebben van $> k$ kleuren, specifiek voor $2 \le k \le d$. Ze vermoeden dat deze overgangen plaatsvinden in het **thermodynamische regime**, waar het gemiddelde graad constant is (d.w.z.$\alpha \sim n^{-1/d}$).

---

2. Methodologie

De auteurs gebruiken een combinatie van meetkundige analyse, percolatietheorie en probabilistische methoden.

• Stereografische Projectie: Om de analyse op de sfeer $S^d$ te vereenvoudigen, projecteren de auteurs de punten naar de Euclidische ruimte $\mathbb{R}^d$ via stereografische projectie. Dit maakt het mogelijk om lokale structuren te analyseren alsof ze in een vlak liggen.
• Continuum AB-percolatie: Voor het geval $k=2$ (twee kleuren) vergelijken ze de lokale structuur van de Borsuk-grafiek met het continuum AB-percolatiemodel. In dit model zijn er twee onafhankelijke Poisson-processen ($Z_A$ en $Z_B$) in $\mathbb{R}^d$; punten uit $Z_A$ worden verbonden met punten uit $Z_B$ als hun afstand $\le 1$ is.
  • Een grafiek is 2-kleurbaar (bipartiet) dan en slechts dan als er geen oneven cyclus is.
  • De auteurs tonen aan dat het bestaan van oneven cycli in de Borsuk-grafiek correleert met het ontstaan van een oneindige cluster in het AB-percolatiemodel.
• Inbedding en "Bad Patches": Voor het bewijs van Theorema 1 (overgang naar $d+1$ kleuren) construeren ze een inbedding $\phi: S^{d-1} \to S^d$ die dicht bij de evenaar ligt. Ze vermijden gebieden op de sfeer die "leeg" zijn (geen willekeurige punten bevatten) door iteratieve verstoringen toe te passen. Hierdoor vinden ze een subgraaf die gedraagt als een Borsuk-grafiek in dimensie $d-1$.
• Scherp-drempel theorieën: Voor Theorema 4 maken ze gebruik van resultaten over scherpe drempels voor Booleaanse functies (gebaseerd op werk van Friedgut en Kalai) en een "sprinkling"-techniek (het toevoegen van extra punten) om globale eigenschappen af te leiden uit lokale percolatie-eigenschappen.

---

3. Belangrijkste Resultaten

Theorema 1: Overgang naar $d+1$ kleuren

Er bestaat een constante $c = c(d) > 0$ zodanig dat als $\alpha = c \cdot n^{-1/d}$, de kans dat $\chi(G(n, \alpha)) > d$ naar 1 convergeert.

• Betekenis: De overgang van $(d+1)$-kleurbaar naar $\ge d+2$ kleuren gebeurt al wanneer het gemiddelde graad constant is, veel eerder dan het logaritmische regime dat eerder bekend was.

Theorema 2: Scherpe drempel voor 2 kleuren ($k=2$)

Er bestaat een constante $c_2 = c_2(d) > 0$ zodanig dat er een scherpe drempel is voor 2-kleurbaarheid:

• Als $\alpha \ge (c_2 + \epsilon)n^{-1/d}$, dan is $\chi > 2$ met kans 1 (er bestaat een oneven cyclus).
• Als $\alpha \le (c_2 - \epsilon)n^{-1/d}$, dan is $\chi \le 2$ met kans 1 (de grafiek is bipartiet).
• De constante $c_2$ wordt uitgedrukt in termen van de kritieke intensiteit $\lambda_c$ voor continuum AB-percolatie in $\mathbb{R}^d$.

Theorema 3: Overgang van 1 naar 2 kleuren

Dit beschrijft het regime waar het gemiddelde aantal randen constant is ($n^2 \alpha^d \to \nu$). De overgang is hier een "ruwe drempel" (coarse threshold), waarbij de kans op het hebben van randen (en dus $\chi > 1$) overgaat van 0 naar 1 volgens een Poisson-verdeling.

Theorema 4: Scherpe drempels voor $k = 3, \dots, d+1$

Voor elke $k$ tussen 3 en $d+1$ bestaat er een rij $\alpha_k(n)$ zodanig dat er een scherpe drempel is voor de eigenschap "$\chi > k$" voor bijna alle $n$ (een verzameling met dichtheid 1).

• Dit betekent dat voor de meeste waarden van $n$, de overgang scherp is rond $\alpha_k \sim c_k \cdot n^{-1/d}$.

---

4. Significatie en Bijdragen

1. Versnelling van de drempel: Het artikel weerlegt de impliciete aanname dat de overgang naar hogere chromatische getallen alleen in het logaritmische regime plaatsvindt. Ze tonen aan dat de "thermodynamische regime" (constante gemiddelde graad) al voldoende is voor de overgang naar $\chi \ge d+1$.
2. Verbinding met Percolatie: Een van de meest significante bijdragen is de connectie tussen het chromatische getal van de Borsuk-grafiek en de percolatietheorie. Specifiek voor $k=2$ wordt het probleem gereduceerd tot het bestuderen van de kritieke intensiteit van AB-percolatie. Dit biedt een nieuwe wiskundige taal om problemen rondom oneven cycli in geometrische grafieken aan te pakken.
3. Scherpe Drempels: Het bewijst het bestaan van scherpe drempels voor kleurbaarheid in een geometrisch model, wat een belangrijke stap is in het begrijpen van monotoon grafiek-eigenschappen in willekeurige geometrische grafieken (een gebied waar dit niet vanzelfsprekend is, in tegenstelling tot de Erdős-Rényi grafieken).
4. Open Problemen en Vermoedens: De auteurs formuleren het vermoeden (Conjecture 57) dat voor elke $k \in \{3, \dots, d\}$ er een constante $c_k$ bestaat zodanig dat de drempel exact van de vorm $c_k \cdot n^{-1/d}$ is, met $c_2 < c_3 < \dots < c_d$. Ze suggereren dat $c_k$ gerelateerd zou kunnen zijn aan de kritieke intensiteit voor "hogere-orde percolatie-evenementen".

Conclusie

Dit werk biedt een fundamenteel inzicht in de structurele eigenschappen van willekeurige Borsuk-grafieken. Het verlegt de grens van kennis over wanneer deze grafieken niet meer kleurbaar zijn met een klein aantal kleuren, en koppelt dit aan diepe resultaten uit de percolatietheorie. De resultaten suggereren dat de complexiteit van het kleuren van deze grafieken al op een zeer vroeg stadium (constante graad) optreedt, in plaats van pas bij hogere connectiviteit.