5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ The second link Googling "Coloring Points in the Plane" led me to Mariano's answer. This shows you picked a good title! $\endgroup$ Feb 3, 2010 at 6:32
  • 8
    $\begingroup$ 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. $\endgroup$ Feb 3, 2010 at 8:10
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 30, 2010 at 17:45

4 Answers 4

9
$\begingroup$

This is the Hadwiger–Nelson problem.

$\endgroup$
1
  • $\begingroup$ wow, impressively fast answer. $\endgroup$ Feb 3, 2010 at 6:34
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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...).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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