Je leest:

Erdös’ probleem uit de combinatorische meetkunde opgelost

Erdös’ probleem uit de combinatorische meetkunde opgelost

Auteur: | 7 juni 2011

Teken een stel punten en verbind elk tweetal punten met een rechte lijn. Rangschik de punten zo, dat het aantal verbindingslijnen van verschillende lengte minimaal is. Hoe groot is die minimale waarde als het aantal punten groot is? Dit 65 jaar oude vraagstuk is nu opgelost.

De befaamde Hongaarse wiskundige Paul Erdös (1913-1996) is – dankzij een publicatielijst van ruim 1500 artikelen – vooral bekend als probleemoplosser, maar hij bedacht zelf ook nieuwe problemen. Een daarvan is het verschillende afstanden probleem uit 1946. Nu, 65 jaar later, is het probleem opgelost door Nets Hawk Katz van de Indiana University en Larry Gutz van het Institute for Advanced Study in Princeton.

Teken een stel punten en verbind elk tweetal punten met een rechte lijn. Lijnen van verschillende lengte geef je verschillende kleuren, lijnen van gelijke lengte krijgen dezelfde kleur. De vraag die Erdös stelde is: wat is het kleinst mogelijke aantal kleuren bij een gegeven aantal punten?

Bij drie punten is het makkelijk: één kleur volstaat, door de punten op de hoekpunten van een gelijkzijdige driehoek te plaatsen. Bij vier punten heb je twee kleuren nodig en ook bij vijf punten lukt het met twee kleuren, zie onderstaande illustratie.

Alex van den Brandhof

Bij zes of zeven punten heb je een derde kleur nodig; de twee mogelijkheden om zeven punten te rangschikken, zie je hieronder.

Alex van den Brandhof

Bij acht of negen punten heb je vier kleuren nodig; de vier mogelijkheden om negen punten te rangschikken, zie je hieronder. Slechts bij één mogelijkheid zijn alle lijnen met kleur aangegeven. Bij de andere drie mogelijkheden is van elke lengte er één met kleur aangegeven; de overige lijnen zijn gestippeld met zwart. Overtuig jezelf dat er geen vijfde kleur nodig is om deze stippellijnen te kleuren!

Alex van den Brandhof

Bij tien, elf of twaalf punten heb je vijf kleuren nodig. Voor twaalf punten volstaat het niet om de punten met gelijke afstand op de omtrek van een cirkel te leggen; je zou dan zes kleuren nodig hebben! Probeer zelf te bedenken hoe je twaalf punten moet rangschikken, zodat je aan vijf kleuren genoeg hebt. De oplossing staat onderaan dit artikel.

Heel veel punten: hoeveel kleuren?

De vraag is hoe het verder gaat als het aantal punten toeneemt. Bij een zeer groot aantal punten is het verre van eenvoudig om uit te vinden hoe je de punten moet rangschikken, om het aantal verbindingslijnen van verschillende lengte te minimaliseren.

Nets Katz.

Katz zegt dat ze ongeveer drie maanden hebben gewerkt aan hun artikel ‘On the Erdös distinct distance problem in the plane’, dat inmiddels is geaccepteerd door het prestigieuze tijdschrift Annals of Mathematics. “Maar het bewijs dat we daarin geven, is gebaseerd op eerder werk van ons en van andere wiskundigen,” zegt hij. “In feite is het bewijs een product van meerdere jaren.”

De twee wiskundigen gebruikten verschillende technieken uit de wiskunde. In eerste instantie probeerden ze het probleem geheel langs algebraïsche weg te tackelen. “Op een zeker moment realiseerden we ons dat deze methode niet toereikend was. We eindigden met een combinatie van verschillende technieken.” Zo gebruikten ze onder meer de ham-sandwich-stelling, een resultaat uit de algebraïsche topologie.

Door hun nieuwe ideeën konden de wiskundigen bewijzen dat als je uitgaat van n punten, het aantal verbindingslijnen van verschillende lengte ten minste gelijk is aan een constante maal n_/log(_n). Dit is een aanzienlijke verbetering ten opzichte van de ondergrens die hiervoor bekend was. Fieldsmedaille-winnaar Terence Tao is onder de indruk van het werk van Katz en Gutz. “Hiermee is de basis gelegd voor verdere ontwikkelingen in de combinatorische meetkunde,” schreef hij.

Katz zegt dat een wiskundig probleem hem enorm kan fascineren. Zoals bij zo veel wiskundigen, gaat het hem om het probleem zélf. Maar ook toegepast wiskundigen kunnen blij zijn: de combinatorische meetkunde wordt gebruikt in onder meer de robotica en bij computer graphics.

Ronald Graham, zijn vrouw Fan Chung Graham en Paul Erdös in 1986 in Japan.

Een check van Erdös

Met het geld dat Erdös met zijn lezingen en gastcolleges verdiende, loofde hij prijzen uit voor de persoon die een door hem bedacht probleem zou oplossen. Sommige prijzen waren symbolische geldbedragen, maar voor ingewikkelde problemen kon het prijzengeld aardig oplopen. Voor het verschillende afstanden probleem was een check ter waarde van 500 dollar beschikbaar.

Na Erdös’ dood in 1996 heeft Ronald Graham, een vooraanstaand wiskundige op de befaamde Bell Labs en een goede vriend van Erdös, een aantal nog openstaande problemen geadopteerd en zich garant gesteld voor eventuele uitbetaling.

Het geld hoeven Katz en Guth echter niet te hebben. Veel liever hebben ze de originele check, ondertekend door Erdös, ook al kan die niet meer ingewisseld worden voor geld. “Die check is het waard om ingelijst te worden. Ik hoop echt dat die bewaard is gebleven,” aldus Katz.

Meer over (problemen van) Paul Erdös:

Oeps: Onbekende tag `feed’ met attributen {"url"=>"https://www.nemokennislink.nl/kernwoorden/erdos.atom", “max”=>"7", “detail”=>"minder"}

Oplossing van het verschillende afstanden probleem voor n = 12. Als je 12 punten rangschikt zoals op de tekening hiernaast en elk tweetal punten met een rechte lijn verbindt, is het aantal lijnen van verschillende lengte gelijk aan 5.
Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 07 juni 2011

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.