ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Erdős: How many colors is it necessary to use so that, if you paint every single point of the two-dimensional plane some color, no two points which are a distance one from each other are the same color? (That is, what is the chromatic number of the unit distance graph in the plane?) It's not hard to show that the number is between 4 and 7 -- but nobody has a clue where it falls in between. Recently, De Grey showed it's at least 5. See this. A related problem, due to Chris Dillard: Consider B_(r), the Ball of radius r about 0 in R^(2). What is the chromatic number of the unit distance graph on B_(r)? We know that, for r < 1/2, it is 1; for r = 1/2, it is 2; for 1/2 < r <= sqrt(3)/3, it's 3. How about for r > sqrt(3)/3? At some r_(0), the chromatic number must become 4. It is easy to see that r_(0 )is no more than 3/sqrt(11) : see the figure below. In fact, it is possible to improve this to sqrt(3)/2, but that still leaves a sizable gap.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.