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?

Improve this question
$\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$
    – Jonas Meyer
    Commented 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$
    – Konrad Swanepoel
    Commented 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$
    – Timothy Chow
    Commented Jun 30, 2010 at 17:45

4 Answers 4

Reset to default
9
$\begingroup$

This is the Hadwiger–Nelson problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ wow, impressively fast answer. $\endgroup$
    – Richard Dore
    Commented 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.

Improve this answer
$\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...).

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .