Researcher Fernando de Oliveira Filho of the Centrum Wiskunde & Informatica (CWI) in Amsterdam improved the lower bounds on the chromatic number. He received his PhD degree on December 1 for his thesis 'New Bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization'.
The following problem was posed by mathematician E. Nelson (1950): Suppose we wish to give colors to the points of the (Euclidean) plane in such a way that no two points at distance one are colored with the same color. What is the minimum number of colors one needs to do this? The minimum number of colors needed is called the chromatic number of the plane. It is known that this number lies between 4 and 7, that is, that one needs at least 4 colors and at most 7 colors.
Although finding the exact value of this chromatic number sounds like a simple puzzle, it is in fact a famous and notoriously difficult problem in geometry. One reason for the difficulty is that the collections of points receiving the same color might have extremely strange shapes, so strange that they could not even be drawn. The problem becomes even more difficult if one considers not the two-dimensional plane, but the three-dimensional (or even higher dimensional) space.
Fernando de Oliveira Filho invented new optimization methods in order to obtain better lower bounds for these numbers. He considers shapes which mathematicians call Lebesgue measurable, a restriction which opened the way to using optimization software. Oliveira improved the lower limits beginning at three dimensions. The greater the number of dimensions, the greater the improvement. This kind of colouring problem is used for
example when assigning frequencies to mobile phones. Moreover the new optimization methods developed by Oliveira have a great potential of being useful in different contexts, e.g. in finding energy minimizing states of systems in physics and engineering.
The research was conducted at the Centrum Wiskunde & Informatica (CWI), and the PhD defence took place at the University of Amsterdam (UvA). Supervisor is Prof. A. Schrijver (CWI and UvA) and co-supervisor is dr. F. Vallentin (TUD and CWI).
Source: UvA web site, translation CWI
Illustration: Fernando de Oliveira Filho, CWI
