Het platte vlak heeft minstens vijf kleuren nodig

Hoeveel kleuren heb je nodig om een (eventueel oneindig groot) plat vlak in te kleuren? Zonder beperkende voorwaarden is dit een onzinnige vraag. Iedereen kan immers een muur strak paars verven. Eén kleur is genoeg.

Maar stel nu, dat iemand je een klein maatlatje geeft – waarvan je de lengte ‘1’ noemt – en je vraagt om een muur te schilderen, zodanig dat als je dit maatlatje ergens tegen de muur houdt, de uiteinden altijd in verschillende kleuren liggen. Hoeveel kleuren heb je dan nodig? Dit probleem is in 1950 voor het eerst geopperd door de Amerikaanse wiskundige Edward Nelson. Het minimaal benodigde aantal kleuren heet het chromatische getal van het platte vlak.

Met twee kleuren lukt dit niet, maar dit is niet makkelijk in te zien, gegeven de oneindige verscheidenheid van mogelijke twee-kleuringen van een muur. Gelukkig bewezen Paul Erdös en Nikolaas de Bruijn al een jaar later, dat het probleem equivalent is aan de vraag: hoeveel kleuren zijn nodig, om een netwerk van knooppunten (een graaf) te kleuren, als alle verbonden knooppunten onderlinge afstand 1 hebben en niet dezelfde kleur mogen hebben?

Twee kleuren is niet genoeg

Met andere woorden: het inkleuren van een vlak met oneindig veel punten, is gelijkwaardig aan het inkleuren van een graaf met eindig veel knooppunten. Bewijzen dat twee kleuren niet genoeg zijn om de muur te verven is nu kinderlijk simpel: neem een graaf met drie knooppunten in de vorm van een gelijkzijdige driehoek met zijde 1. Als één knooppunt paars is, en één knooppunt geel, kan het derde knooppunt noch paars, noch geel zijn, anders ontstaat een paar van knooppunten met dezelfde kleur, en dat mag niet. Voor dat derde knooppunt moet je een derde kleur kiezen.

Zo hebben we voor het chromatische getal van het platte vlak al een ondergrens van drie vastgesteld. Er zijn ook simpele grafen bekend die vier kleuren nodig hebben (zie als voorbeeld bovenstaande afbeelding). Dit was sinds 1950 de stand van zaken: de ondergrens is vier.

Anderzijds, als je een bovengrens voor het chromatische getal wilt vaststellen, zul je een kleuring moeten presenteren van alle punten in het vlak, dus een kleuring die echt de hele muur vol schildert. Zo’n vlakvullende kleuring met maar zeven kleuren is bekend (zie onderstaande afbeelding), dus de bovengrens is zeven. Ook dit is al heel lang bekend.

Ondergrens opgeschoven

Zo heeft De Grey, met een mengeling van geluk en wijsheid, zonder ‘diepe’ theorie, de ondergrens opgeschoven. Dion Gijswijt, wiskundige aan de TU Delft, is enthousiast over dit resultaat, maar betwijfelt of dit veel perspectief biedt: “Je ziet dat de graaf van De Grey om de ondergrens op vijf te zetten al behoorlijk groot is. Als het chromatisch getal zes is, zou het best kunnen dat de graaf die dat bewijst nog veel groter is. Zo groot, dat zelfs computers die niet meer kunnen hanteren.”

Recente voorbeelden in deze tak van wiskunde zijn niet hoopgevend. Twee jaar geleden bewees een supercomputer dat er een bovengrens bestaat voor het Booleaanse Pythagoreïsche drietallenprobleem . Dit bewijs was 200 terabyte, wat ongeveer overeenkomt met de tekst in alle Nederlandse bibliotheekboeken. Een van de drie betrokken onderzoekers was Marijn Heule, ooit promovendus aan de TU Delft, en nu onderzoeker aan de University of Texas.

Overigens zegt niets in de methode van De Grey dat er geen kleinere grafen bestaan die ook minstens vijf kleuren nodig hebben. Er is een online project gestart om de 1581 knooppunten zo ver mogelijk terug te snoeien. Marijn Heule vond al snel nadat De Grey zijn graaf had gepubliceerd, een graaf met 803 knooppunten (een deel daarvan is te zien in de illustratie bovenaan dit artikel). Heules meest recente vondst is een graaf met nog maar 633 knooppunten .

Meer dan twee dimensies

Een logische voortzetting is de vraag wat het chromatisch getal is voor ruimtes met meer dan twee dimensies. Hier is onderzoek naar gedaan door onder andere Fernando Oliveira. Voor dimensie drie, de ruimte waarin wij bestaan, ligt de ondergrens momenteel op 7, de bovengrens op 15. De getallen stijgen exponentieel naarmate het aantal dimensies toeneemt. Voor tien dimensies ligt de ondergrens momenteel op 73. Gijswijt: “In hogere dimensies liggen de onder- en bovengrens verder uit elkaar, zodat je als wiskundige meer interessante dingen kunt doen.”

Zullen we ooit weten of het chromatisch getal van het platte vlak 5,6 of 7 is? Experts verschillen van mening over hoe moeilijk dit type probleem is. Weliswaar staat dit al bijna zeventig jaar open, maar omdat het niet gezien wordt als een heel belangrijke kwestie binnen de wiskunde, is er ook niet heel veel aan gewerkt. Het is denkbaar dat iemand een diepzinnige theorie over n-dimensionale ruimtes ontdekt die in één klap alle chromatische getallen bepaalt, maar niemand kan een zinnig woord zeggen over hoe de groot die kans is.