You are here

The Unit-distance graph and the Odd-distance graph

Moshe Rosenfeld, University of Washington, Tacoma
Wednesday, October 10, 2018 - 3:30pm
PDL C-401

On Wednesday, Sep. 5 2018, I visited Branko Grűnbaum. I told him about this new development that was communicated to me by his "grand-son" Gil Kalai. I suggested that I may talk about it in the seminar and offerred to bring him along. It would have brought together possibly five generations of mathematics originated by Branko.
Unfortunately, life is what happens to us while we are busy making other plans.

In 1950, Ed Nelson noted that at least four colors are needed to color the points of \$\mathbb{R}^2\$ so that two points at distance 1 are assigned distinct colors. He asked whether four colors are enough. He called it the the alternative four-color problem. John Isbell noted that the plane can be colored by seven colors. For 68 years, these two bounds resisted many improvement attempts. On April 10, 2018, Aubrey de Grey "broke the ice:" he
published a configuration of 1581 points in the plane that require 5 colors. Thus began a new wave of activity trying to improve this result.

A related graph is the Odd-distance graph. The vertices of this graph are the points in the plane, two points connected by an edge if their distance is an odd integer. In this talk I will briefly describe the Odd-distance graph, the current status and focus on open problems.

Event Type: 
Share