Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose one wants to color the points in the plane so any two points at distance one apart are different colors. How many colors are needed?

I heard this problem when I was a kid. Back then the most I knew was that 3 is impossible and 7 is possible (tile hexagons of diameter 1-ε). I haven't heard about this problem since then and I don't know how to search for it. Is more known? Is this problem well known in certain circles?

share|improve this question
    
The second link Googling "Coloring Points in the Plane" led me to Mariano's answer. This shows you picked a good title! –  Jonas Meyer Feb 3 '10 at 6:32
8  
Alexander Soifer's "The Mathematical Coloring Book" contains a lot of history on this problem. There is some recent research of Soifer, Shelah and others that suggest the answer may depend on the axioms of set theory. –  Konrad Swanepoel Feb 3 '10 at 8:10
2  
In my opinion it is somewhat misleading to say that "the answer may depend on the axioms of set theory." If we assume the axiom of choice then we can use a compactness argument to prove that the chromatic number of the plane is equal to the maximum chromatic number of a finite unit-distance planar graph. In the absence of the axiom of choice, these two numbers aren't necessarily equal so there are two separate questions here. But if you accept the axiom of choice, as most mathematicians do, I don't think there is any evidence that the answer is independent of ZFC. –  Timothy Chow Jun 30 '10 at 17:45
add comment

4 Answers

up vote 8 down vote accepted

This is the Hadwiger–Nelson problem.

share|improve this answer
    
wow, impressively fast answer. –  Richard Dore Feb 3 '10 at 6:34
add comment

I remember seeing this while grazing online back in the 20th century. The relevant phrase to google would be something like "chromatic number of the plane"; see also this wikipedia page.

share|improve this answer
add comment

This is the well-known unit distance graph problem. If we call $U=U(\mathbb R^2)$ as the unit distance graph on the plane; that is, the vertices are the points on the plane and the edges are the pairs at distance one from each other.

It is well-known that $$4 \leq \chi(U(\mathbb R^2))\leq 7.$$

The lower bound is found by drawing a finite unit distance subgraph of $U$ which has chromatic number 4 while the upper bound is found by coloring the plane with 7 colors after dividing it into hexagons of a fixed,small diameter.

\medskip

Recently, I came across the study of the chromatic index of a supergraph of $U$ called odd-distance graphs. Moreover, I think that this problem is equivalent to finding a measure of some sort but that is all I remember.

We once tried to use Hammel Basis of the plane to come up with a proof which at least improves the above bounds but it does not seem to work(well, we were able to prove that $\mathbb Z$ is an integral domain... funny...).

share|improve this answer
add comment

If one assumes measurability of the corresponding sets in the plane partition, the bounds are tighter. See e.g. Lower bounds for measurable chromatic numbers , Geom. Funct. Anal. 19 (2009), 645-661.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.