Suns in triangle-free graphs of large chromatic number

Dit artikel bewijst dat elke driehoekvrije graaf met een voldoende grote chromatische getal een geïnduceerde subgraaf bevat die óf een $t$-zon is voor $t \geq 5$, óf een $4$-zon met één graad-een-vertex verwijderd, waarmee een vraag van Trotignon over de aanwezigheid van zulke structuren in grote driehoekvrije grafen wordt beantwoord.

De kern

Stel je voor dat wiskundigen als detectives werken die op zoek zijn naar verborgen patronen in een enorme, chaotische stad. In dit geval is de "stad" een graf (een verzameling punten die met lijnen verbonden zijn) en de "detectives" proberen te begrijpen hoe groot en complex deze stad kan worden voordat er bepaalde, specifieke gebouwen verschijnen.

Dit artikel van Sepehr Hajebi en Sophie Spirkl gaat over een heel specifiek raadsel in de wiskunde: Hoe "kleurig" kan een stad zijn zonder dat er driehoekige gebouwen of zonnige bloemen ontstaan?

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. De Basisregels van de Stad

Om het verhaal te volgen, moeten we eerst drie concepten begrijpen:

• Driehoeksvrij (Triangle-free): Stel je voor dat in deze stad niemand met twee andere mensen bevriend is die ook onderling bevriend zijn. Als A vriend is van B, en B van C, dan mogen A en C niet vrienden zijn. Er zijn dus geen "driehoekjes" van vriendschap.
• Kleuring (Chromatic Number): Dit is het aantal kleuren dat je nodig hebt om de stad in te delen, zodat geen twee buren dezelfde kleur hebben. Een stad met een "groot kleurnummer" is heel complex en druk; je hebt heel veel verschillende kleuren nodig om de chaos te ordenen.
• De Zon (The Sun): Dit is het belangrijkste personage in dit verhaal. Een "t-zon" is een cirkel van mensen (een ring), waarbij elke persoon in de ring nog één extra vriend heeft die nergens anders mee te maken heeft (een "staartje").
  • Vergelijking: Denk aan een zonnetje met stralen. De cirkel is de gloed, en de extra vrienden zijn de stralen.

2. Het Grote Raadsel (Het Probleem)

Een wiskundige genaamd Trotignon stelde de volgende vraag:
"Als je een stad bouwt die geen driehoekjes heeft, maar die toch ontzettend complex is (veel kleuren nodig), moet er dan vroeg of laat een 'zon' in verschijnen?"

Tot nu toe wisten ze dit niet zeker. Misschien kun je een oneindig complexe stad bouwen zonder dat er ooit een zonnetje ontstaat.

3. Wat deze auteurs hebben ontdekt

De auteurs zeggen: "We kunnen het niet voor alle zonnetjes bewijzen, maar we komen er heel dichtbij."

Ze ontdekten een grens. Als je een stad bouwt die:

1. Geen driehoekjes heeft,
2. Geen "4-zon" heeft (een zon met 4 stralen, maar dan met één straal eraf gehaald, een zogenaamde "4-zonspot"),
3. En geen grote zonnen (met 5 of meer stralen) heeft,

...dan kan die stad niet oneindig complex worden. Er is een limiet aan het aantal kleuren. Als je probeert de stad nog complexer te maken dan die limiet (in hun berekening is dat 47 kleuren), dan moet er per ongeluk een zonnetje ontstaan.

De Analogie:
Stel je voor dat je een toren bouwt van blokken. Je mag geen driehoekige blokken gebruiken. Je mag ook geen blokken gebruiken die eruitzien als een klein zonnetje met 4 stralen (waarvan er één mist).
De auteurs zeggen: "Als je probeert deze toren hoger te bouwen dan 47 verdiepingen, dan gaat het mis. De structuur is zo stijf dat je gedwongen wordt om ergens een 'zonnetje' te bouwen, of je wilt of niet."

4. Hoe hebben ze dit bewezen? (De Reis door de Stad)

Om dit te bewijzen, gebruikten ze een slimme strategie die lijkt op het verkennen van een stad in lagen:

• Stap 1: De Lagen (Leveling): Ze keken niet naar de hele stad tegelijk, maar verdeelden de stad in concentrische ringen (lagen). De buitenste laag had nog steeds veel complexiteit.
• Stap 2: De Gaten (Holes): Ze zochten naar grote cirkels in de stad (gaten) die lang genoeg waren. Ze bewezen dat als de stad complex genoeg is, er altijd zo'n groot gat moet zijn.
• Stap 3: De Vlammen (Flares): Dit is het meest creatieve deel. Ze dachten: "Stel dat we bij elke persoon in die grote cirkel een extra vriendje zoeken die niet met de rest van de cirkel praat."
  • Als de stad complex genoeg is, kunnen ze voor iedereen in de cirkel zo'n vriendje vinden.
  • Als je dat doet, heb je plotseling een perfecte "zon" gecreëerd! De cirkel is de gloed, en al die vriendjes zijn de stralen.
• Stap 4: De Contradictie: Omdat we in de aanname hadden gesteld dat er geen zonnen zijn, leidt dit tot een tegenstrijdigheid. De enige conclusie is dat de stad niet zo complex kon zijn als we dachten. De limiet (47) is dus echt.

5. Waarom is dit belangrijk?

In de wiskunde is het belangrijk om te weten welke structuren moeten bestaan als iets complex genoeg wordt.

• Het helpt om te begrijpen hoe complexe netwerken (zoals het internet, sociale netwerken of biologische systemen) zich gedragen.
• Het lost een deel van een langdurig raadsel op. Hoewel ze niet het hele probleem hebben opgelost (de vraag of het geldt voor alle zonnetjes), hebben ze wel bewezen dat je niet kunt ontsnappen aan zonnetjes als je de stad complex genoeg maakt, mits je een paar specifieke kleine varianten uitsluit.

Kort samengevat:
De auteurs hebben bewezen dat je in een wereld zonder driehoekjes, niet oneindig hoog kunt klimmen zonder dat er op een gegeven moment een "zonnetje" (een specifieke cirkel met uitsteeksels) ontstaat. Als je te hoog probeert te bouwen, breekt de wet van de natuur (de wiskunde) en moet je die zon accepteren.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Suns in Triangle-Free Graphs of Large Chromatic Number" van Sepehr Hajebi en Sophie Spirkl, vertaald en samengevat in het Nederlands.

Titel: Zonnen in driehoeksvrije grafen met een grote chromatische getal

Auteurs: Sepehr Hajebi en Sophie Spirkl
Datum: 10 maart 2026

---

1. Probleemstelling en Achtergrond

Het artikel behandelt een fundamenteel probleem in de structurele grafentheorie, gerelateerd aan de $\chi$-gebondenheid (chi-boundedness) van grafenklassen. De centrale vraag is of de chromatische getal $\chi(G)$ van een graf $G$ begrensd kan worden door een functie van het clique-getal $\omega(G)$, wanneer bepaalde geïnduceerde subgrafen zijn uitgesloten.

• Trotignons Probleem (Probleem 1.1): Is het chromatische getal begrensd voor elke driehoeksvrije graf die zon-vrij is?
  • Een $t$-zon ($t$-sun) is een graf die ontstaat uit een cykel van $t$ hoekpunten ($C_t$) waarbij aan elk hoekpunt van de cykel een nieuw hoekpunt van graad 1 wordt toegevoegd.
  • Een graf is zon-vrij als geen enkel geïnduceerd subgraf een $t$-zon is voor enige $t \ge 4$.
• Status: Dit probleem is nog open. Er is bekend dat "shift graphs" driehoeksvrije grafen met willekeurig groot chromatisch getal kunnen hebben zonder geïnduceerde $t$-zonen voor $t \ge 5$. Dit betekent dat het uitsluiten van 4-zonen essentieel is voor een positief antwoord.
• Doel van het artikel: Het auteurs bewijzen dat als men 4-zonen uitsluit (en specifiek een variant daarvan, de "4-zonspot"), en ook alle $t$-zonen voor $t \ge \ell$ (waarbij $\ell \ge 6$), het chromatische getal inderdaad begrensd is.

2. Belangrijkste Definities en Notatie

• 4-Zonspot: Een graf die ontstaat uit een 4-zon door één hoekpunt van graad 1 te verwijderen. Formeel een 7-tupel $(x_1, x_2, x_3, x_4; y_1, y_2, y_3)$ met specifieke randen.
• Gaten (Holes): Geïnduceerde cycli met lengte $\ge 4$.
• Flap: Een 4-gat dat ten minste één rand deelt met een groter gat $H$.
• Flare: Een mapping $\Phi$ van een gat $H$ naar de omgeving in $G \setminus H$, waarbij elk hoekpunt van $H$ maximaal één extra buur krijgt.
• Eigenschappen van grafen:
  • Niet-degeneraat: Elk hoekpunt heeft graad $\ge \chi(G) - 1$.
  • Liberaal: Geen enkel hoekpunt "domineert" een ander (voor elke niet-benaderde $x, y$ geldt dat $N(x) \setminus N(y) \neq \emptyset$ en vice versa).
  • Flaploos: Voor elk gat $H$ van lengte $\ge 6$ bestaat er geen $H$-flap.

3. Methodologie en Bewijsstrategie

Het bewijs is opgebouwd uit een reeks structurele lemmata die leiden tot een contradictie als het chromatische getal te groot wordt. De aanpak volgt een "decompositie"-strategie:

Stap 1: Reductie tot een "Goede" Subgraf (Sectie 2)

De auteurs bewijzen Stelling 2.1: Als een driehoeksvrije, 4-zonspot-vrije graf een groot chromatisch getal heeft, bevat deze een geïnduceerd subgraf $L$ dat:

1. Een specifiek chromatisch getal heeft ($c+1$).
2. Niet-degeneraat is.
3. Liberaal is.
4. Flaploos is (geen flaps voor gaten van lengte $\ge 6$).

Dit wordt bereikt door gebruik te maken van levelings (lagen van hoekpunten) en het selecteren van componenten met maximale chromatische getallen.

Stap 2: Analyse van Flares en Veiligheid (Sectie 3)

In een flaploze, libere graf met een groot minimumgraad, bewijzen de auteurs (Stelling 3.1) dat voor elk gat $H$ van lengte $\ge 6$ een volledige $d$-veilige $H$-flare bestaat.

• Een flare is $d$-veilig als de extra buur van een hoekpunt $h$ in $H$ geen connecties heeft met de extra buur van een ander hoekpunt $h'$ binnen afstand $d$ in $H$.
• Dit wordt bewezen via een maximaliteitsargument: als een flare niet volledig is, kan men een nieuw hoekpunt toevoegen zonder de veiligheidsvoorwaarde te schenden, wat leidt tot een contradictie met de 4-zonspot-vrijheid.

Stap 3: Constructie van een Zon (Sectie 4)

De uiteindelijke stap combineert de eerdere resultaten:

1. Uit Corollary 4.4 (gebaseerd op werk van Chudnovsky, Scott, en Seymour) volgt dat een driehoeksvrije graf met groot chromatisch getal een gat van lengte $\ge \ell$ moet bevatten.
2. Door de structuur van $L$ (niet-degeneraat, liberaal, flaploos) en de aanwezigheid van een gat $H$ van lengte $t \ge \ell$, garandeert Stelling 3.1 het bestaan van een volledige $\ell$-veilige flare.
3. De auteurs tonen aan dat de combinatie van het gat $H$ en de flare-punten een $t$-zon vormt.
4. Omdat de graf per definitie $t$-zon-vrij is voor $t \ge \ell$, ontstaat er een contradictie.

4. Kernresultaten

Het artikel levert de volgende hoofdstellingen:

• Stelling 1.2: Als $G$ driehoeksvrij is, 4-zonspot-vrij is, en geen $t$-zon bevat voor enige $t \ge 5$, dan is $\chi(G) \le 47$.
• Stelling 1.3 (Hoofdstelling): Voor elke integer $\ell \ge 6$ bestaat er een constante $c_{1.3}(\ell)$ zodanig dat voor elke graf $G$ die driehoeksvrij, 4-zonspot-vrij en $t$-zon-vrij is voor alle $t \ge \ell$, geldt:
  $$\chi(G) \le c_{1.3}(\ell)$$
  Specifiek geldt voor $\ell = 6$ dat $c_{1.3}(6) = 47$.
• Stelling 1.6 (Uitbreiding naar begrensd clique-getal): Voor grafen die ook bul-vrij zijn (een "bull" is een net met één graad-1 hoekpunt verwijderd), is de chromatische getal begrensd door een functie van het clique-getal: $\chi(G) \le \omega(G)^{37}$ (voor $\ell=5$).

5. Significatie en Bijdrage

1. Nabijheid aan een oplossing: Het artikel biedt een bijna volledig antwoord op Trotignons open probleem. Het toont aan dat het uitsluiten van 4-zonen (via 4-zonspots) en grote zonen voldoende is om de chromatische getal te begrenzen.
2. Structurele Inzicht: De methode introduceert en gebruikt krachtige structurele concepten zoals "levelings", "flaps" en "flares" om complexe interacties in driehoeksvrije grafen te analyseren.
3. Kwantitatieve Grenzen: Het levert expliciete numerieke grenzen op (bijv. 47), wat zeldzaam is in dit type structurele problemen waar vaak alleen asymptotische resultaten worden gevonden.
4. Verband met andere klassen: Door de resultaten te combineren met bestaande stellingen over bul-vrije grafen (Hajebi, 2025), wordt een bredere klasse van grafen ($\chi$-gebonden) geïdentificeerd die net-vrij en zon-vrij is.

Conclusie: De auteurs bewijzen dat de enige obstakels voor $\chi$-gebondenheid in driehoeksvrije grafen die geen grote zonen bevatten, de 4-zonen zijn. Zodra deze (en hun varianten) worden uitgesloten, is het chromatische getal noodzakelijk begrensd.