Je leest:

Het platte vlak heeft minstens vijf kleuren nodig

Het platte vlak heeft minstens vijf kleuren nodig

Eindelijk stap vooruit in zeventig jaar oud wiskundeprobleem

Auteur: | 3 mei 2018

Hoeveel kleuren zijn minimaal nodig om een plat vlak in te kleuren, onder voorwaarde dat geen twee punten op onderlinge afstand 1 dezelfde kleur hebben? Al bijna zeventig jaar is bekend, dat dit met zeven kleuren lukt, en met maar drie kleuren zeker niet. Amateur-wiskundige Aubrey de Grey liet zien dat vier kleuren te weinig is; de ondergrens is opgeschoven naar vijf.

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?

Golombsgraaf
Een van de simpelste afstand-1 grafen waarvoor vier kleuren nodig zijn. Als dit al geldt voor maar tien punten in een vlak, zijn ook minstens vier kleuren nodig om het hele vlak volgens deze eis in te kleuren. Bijna zeventig jaar lang was dit de beste ondergrens voor het chromatische getal van een vlak.

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.

Hexagon7kleuren
Er zijn hoogstens zeven kleuren nodig om het hele vlak in te kleuren, zodanig dat geen twee punten op onderlinge afstand 1 dezelfde kleur hebben. Om dat te bewijzen is één voorbeeld genoeg, zoals deze betegeling van het hele vlak met zeshoeken. De getallen geven de kleuren weer, het patroon in het centrum wordt in de omliggende rozetten identiek herhaald. Als het basis-zeshoekje de juiste afmeting heeft – een diameter iets minder dan 1 – voldoet deze kleuring aan de afstandseis.
Public Domain

Amateur in de wiskunde

De ontdekker van de vijfkleurengraaf, Aubrey de Grey, staat bekend als goeroe van de bijna-onsterfelijkheid. Volgens hem zullen sommige mensen die nu leven tot wel duizend jaar oud worden. Hij gelooft namelijk dat medisch onderzoek al binnen enkele decennia erin zal slagen om alle normale verouderingsprocessen bij de mens vrijwel tot stilstand te brengen of zelfs terug te draaien. Dankzij een grote erfenis en sponsors heeft hij een eigen instituut dat op dit gebied onderzoek doet. De meeste verouderingswetenschappers zijn zeer sceptisch over De Greys ambities. Daarnaast doet De Grey in zijn vrije tijd aan wiskunde. Misschien wordt hij daar, dankzij dit resultaat, wel onsterfelijker mee dan met al het verouderingsonderzoek dat hij als zijn voornaamste missie beschouwt.

Graaf met 1581 knooppunten

Nu heeft iemand de ondergrens eindelijk een stapje weten op te schuiven naar vijf, een amateur-wiskundige nog wel (zie het zijkader). Aubrey de Grey heeft, met hulp van wiskundigen en veel computerkracht, een graaf geconstrueerd van 1581 punten waarvoor vijf kleuren nodig zijn. Het chromatisch getal van het platte vlak is dus 5,6 of 7.

Hij bouwde die enorme graaf op uit een groot aantal kopieën van simpele bouwstenen, waaronder een graaf in de vorm van een regelmatige zeshoek. In diverse stadia moest een computerprogramma grote aantallen kleuringen uitproberen om te checken dat er geen 4-kleuring bij zat.

Uiteindelijk ontstond een bouwwerk met 20.425 knooppunten, waarvan De Grey dacht dat er geen 4-kleuring mogelijk was. Maar deze was te groot om helemaal door te rekenen met een computerprogramma. Daarom is hij (en een computerprogramma) systematisch knooppunten gaan snoeien waarvan hij wist dat die geen invloed zouden hebben op het kleuringsgetal, waarna hij er 1581 overhield. Van deze graaf is met een ander computerprogramma nogmaals gecontroleerd of er geen 4-kleuring mogelijk was, maar wel een 5-kleuring.

Debreygraaf
De afstand-1 graaf met 1581 knooppunten, die vijf kleuren nodig heeft om hem zodanig in te kleuren, dat geen twee verbonden knooppunten dezelfde kleur hebben. De graaf is zo groot, dat de kleuren van de afzonderlijke knooppunten niet goed te zien zijn.

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.

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 03 mei 2018

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.