Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Andrey Raigorodskii

Moscow State University

On the chromatic number of the plane

Abstract:

In our talk, we will discuss a classical problem of combinatorial geometry going back to E. Nelson, P. Erd\"os, and H. Hadwiger. The main question is to find the minimum number of colors needed to paint all the points in a space so that the distance between any two points of the same color would not belong to a fixed set of positive reals. We will present a survey of various results concerning the problem. In particular, we will exhibit some amazing connections between this problem and the Borsuk partition problem (which is to determine the minimum number of parts of smaller diameter into which an arbitrary bounded $n$ - dimensional set can be partitioned.)

Host: M. Alekhnovich

January 17, 2006

3:00 PM

AP&M 7321

****************************