Grenzen van chromatisch getal verbeterd

Onderzoeker Fernando de Oliveira Filho van het Centrum Wiskunde & Informatica (CWI) in Amsterdam verbeterde de ondergrenzen van het chromatisch getal. Hij promoveerde op 1 december op zijn proefschrift 'New Bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization'.



Onderzoeker Fernando de Oliveira Filho van het Centrum Wiskunde & Informatica (CWI) in Amsterdam verbeterde de ondergrenzen van het chromatisch getal. Hij promoveerde op 1 december op zijn proefschrift 'New Bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization'.

De wiskundige E. Nelson stelde in 1950 het volgende: stel dat alle punten van een plat vlak worden gekleurd op zo'n manier dat twee punten met afstand één niet dezelfde kleur hebben. Wat is het minimum aantal kleuren dat nodig is om dit te doen? Dit aantal wordt het chromatische getal van het vlak genoemd. Het is bekend dat dit minimum tussen de vier en zeven ligt.

Fernando de Oliveira Filho onderzocht dit probleem. Met optimalisatiemethodes zocht hij betere grenzen voor dit kleurprobleem. Vanaf drie dimensies verbeterde De Oliveira Filho de ondergrenzen. Hoe groter het aantal dimensies, des te groter de verbetering. Dit soort kleurproblemen wordt bijvoorbeeld gebruikt bij het toewijzen van frequenties aan mobiele telefoons.

Het onderzoek is uitgevoerd op het Centrum voor Wiskunde en Informatica (CWI); de promotie vond plaats aan de Universiteit van Amsterdam (UvA). Promotor is prof. dr. A. Schrijver (CWI en UvA), co-promotor dr. F. Vallentin (TUD en CWI).

Bron: website UvA

Illustratie: Fernando de Oliveira Filho, CWI