Title: Chromatic Number of the Plane: Why is the Problem Still Open?

Speaker: Alexander Soifer, DIMACS, Princeton & University of Colorado at Colorado Springs

Date: Tuesday May 6, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Define Unit Distance Plane U^2 as a graph on the set of all points of the plane R^2 as its vertex set, with two vertices adjacent iff they are distance 1 apart. The chromatic number x of U^2 is called chromatic number of the plane. Surprisingly, the past 52 years have not brought about any improvement in general case: x = 4, or 5, or 6, or 7. The problem CNP of finding chromatic number of the plane has been credited in print to P. Erdos, M. Gardner, H. Hadwiger, L. Moser and E. Nelson. Who created CNP?

Why is CNP still wide open? In a joint work with Saharon Shelah the presenter points out circumstances under which the chromatic number of the plane would depend upon a system of axioms chosen for set theory.

In the same joint work a graph on the real line is constructed, whose chromatic number is affected dramatically by a system of axioms chosen for sets.