##### 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

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