Discrete Geometry: The Unit Distance Graph Problem and the Axiom of Choice

Event Date: 

Wednesday, April 16, 2014 - 2:00pm to 3:00pm

Event Location: 

  • 4607B South Hall

Event Contact: 

Michael Dougherty

Email: dougherty@math.ucsb.edu

Speaker: Paddy Bartlett

Abstract: Here's the unit distance graph problem:

``What is the smallest number of colors needed to color the plane, so that no two points of the same color are distance 1 apart?''

On one hand, it is not difficult to get some rudimentary bounds on this problem: in the first few minutes of our talk, we will show that we need at least four colors and at most seven. The surprising thing about this problem is that these simple bounds are the best currently known for this problem, despite over a half-century of attacks from some of the best minds in combinatorics!

In this talk, we will discuss some of the history behind these attempts. In particular, we will discuss results of Shelah and Soifer that suggest that the axiom of choice (somehow) plays a key role in answering this problem.