Plane colorings

[Desiato]

So, I've checked and was surprised that apparently this classic hasn't been posted here yet:

Is it possible to color the plane with three colors such that no two points of equal color have distance 1?

And since I'm certain that for the regulars, this will be easy to solve, bonus question:

What is the minimum number of colors to allow for such a coloring in R^n? Note that I don't have a complete solution for the bonus question at this time.

[Goplat]

Spoiler:

No, it is not possible. Proof:

Construct an isosceles triangle with corners named A, B₁, and B₂ such that B₁ and B₂ have a distance of 1 unit apart from each other and both of them have a distance of sqrt(3) units from A. Since B₁ and B₂ are 1 unit apart, they must be different colors, which means at least one of them differs from A. Let B be one that does differ.

There are two points that are distance 1 from both A and B; call them C and D. By the Pythagorean theorem, the distance between C and D is also 1:

C and D must be two distinct colors, neither of which is the same as either A or B, but since we already established A and B as different colors, 3 colors are not sufficient.

[jestingrabbit]

I had a slightly different proof.

Spoiler:

If you take a hexagonal lattice of points then you can quickly see that the colour of two adjacent points in the lattice forces a colouring of the rest of the lattice, and, by inspecting this forced colouring, you can see that any points that have distance an integer multiple of 3 have the same colouring. But, there are triangles with side lengths 3, 3, and 4. The vertices of this triangle must all have the same colour, but the vertices on the length 4 side must have different colours.

That extended problem looks pretty nontrivial.

[Proginoskes]

Spoiler:

Right picture, Goplat, wrong explanation.

If you have only 3 colors, then A and B must be colored the same. (Color C and D with 1 and 2; hence, A and B have to both be colored 3.) Now rotate the point B around A; you get a circle of radius \sqrt{3}, all of whose points are colored the same. It is easy to find two points on that circle at distance 1 apart which are colored the same.

The plane can be colored with 7 colors.

No one has made any progress on this problem since it was first proposed 50 or 60 years ago!

[jestingrabbit]

Right picture, Goplat, wrong explanation.

No, just a different explanation. Your own proof has a biggish lemma, that in a 3 colouring all points distance 3^1/2 must have the same colour. Goplat's proof hinges on no lemmas.

[jaap]

The solution Goplat described works in higher dimensions too to show that at least n+2 colours are necessary for Rⁿ.

Spoiler:

In R³, a regular tetrahedron of side length 1 must have all four points of different colours. If there were no more than four colours allowed, then by sticking two such regular tetrahedra together you construct two points that must be the same colour, and lie some distance L apart. Then construct an isosceles triangle with side lengths 1, L, and L, and you can force the two points at distance 1 to have the same colour. This shows that in R³ at least 5 colours are needed for such a colouring.
Similarly, in Rⁿ at least n+2 colours are necessary. By sticking a pair of simplexes together so that they share all but one vertex each you force those two vertices to have the same colour. Using a chain of 2 or more of such pairs you can force two points at distance 1 to be the same colour.

The more difficult question is how many colours are actually sufficient. I don't have a good answer to that.

Spoiler:

For R² seven colours are sufficient. Take a simple hexagonal grid, where each hexagon has diameter D, slightly less than 1. Colour it such that each hexagon and its six neighbours all have different colours. Two hexagons of the same colour must therefore lie at least two hexagons apart, or a distance of D*sqrt(3). So as long as D<1 and D>1/sqrt(3) this 7-colouring of the plane does cannot have a pair of points of the same colour that are a distance 1 apart.
In R³ you could probably use a rhombic dodecahedron to show that 13 colours suffice.

[tomtom2357]

Can anyone prove that four colors are enough/not enough?

Edit: I have proven that a hexagonal, square, or triangular coloring must use seven colors. The triangle/square and octahedral coloring are even worse, requiring at least 10 and 13 colors respectively. I suspect that to need any fewer than 7 colors you need an irregular tiling. Also, for coloring space, you need at least 6 colors (and at most 15), I don't have the proof, but it is on wikipedia.

[skeptical scientist]

Spoilers:
http://en.wikipedia.org/wiki/Hadwiger-Nelson_problem

[tomtom2357]

Yes I've seen that page, but it doesn't give any more results than my findings. I am thinking about using circles of diameter 1, but having the edges be in a different color.

[Desiato]

Spoilers:
http://en.wikipedia.org/wiki/Hadwiger-Nelson_problem

Thanks for that link; I was not aware of the number of results known and the complexities involved. Apologies for the somewhat extensive "bonus question"!

That said - it certainly seems interesting that AoC might play a role in the answer - http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf from the links on the wikipedia page suggests this might be the case. Worth a read for anyone with math background curious about this problem!

[Proginoskes]

Can anyone prove that four colors are enough/not enough?

That would be a major breakthrough, so my response is: I doubt it.

There is a paper at the LANL preprint archives which says that the answer to similar problems can depend on which extension of set theory is used, so the problem may be undecidable. See http://arxiv.org/abs/0707.1177 for details.

[Desiato]

Yes I've seen that page, but it doesn't give any more results than my findings. I am thinking about using circles of diameter 1, but having the edges be in a different color.

This one won't give a (much) better result; it's been shown that using either polygons or jordan curves (i.e. any sort of "map" - both versions can in- or exclude the borders of their regions at will) that >= 6 colors are needed for the plane, and it's also been shown that using measurable sets >=5 colors are needed. This means if there is a 4-coloring of the plane, at least one of its color sets will be unmeasurable.

[tomtom2357]

What do you mean by not measurable?

[Proginoskes]

What do you mean by not measurable?

"In mathematics, a non-measurable set is a set whose structure is so complicated that it cannot be assigned any meaningful measure. Such sets are constructed to shed light on the notions of length, area and volume in formal set theory." --- Wikipedia

( http://en.wikipedia.org/wiki/Non-measurable_set )

[skeptical scientist]

Yes I've seen that page, but it doesn't give any more results than my findings.

It also talks about the dependence on the axiom of choice, and shows that this problem has been looked at by mathematicians, and remains open, which gives one some idea as to its difficulty.

[tomtom2357]

I have worked on problems not yet solved by mathematicians (no I haven't solved any) and I know how hard they are, so you are right. However, can someone give me an explicit definition of a non-measureable set? I am thinking about one of the colors being a group of very small shapes that somehow occupy a 25% portion of the plane, but are never at unit intervals from each other. Am I just spouting nonsense here?

[mfb]

I think what you mean with "very small" would still be measureable.
The linked wikipedia articles gives you a definition of non-measureable sets.

You can do funny things with these sets, including duplication of spheres by moving a finite number of parts around. This example clearly shows that it is not possible to assign meaningful numbers of a "volume" to these parts. Meaningful in a way that the sum of N sets has a volume which is the sum of the N volumes.

[tomtom2357]

So what you're saying is, if the Axiom of Choice is false then no 4-coloring exists, and therefore we can't construct it if the Axiom of Choice is correct (due to the fact that any such construction would be able to be done without the Axiom of Choice)? I don't like those problems.

[Desiato]

"Measurable" is generally taken to mean Lebesgue-measureable; a short sketchy definition for the plane is the infimum of the area of all square coverings (with the area of a square defined as expected) of the set A to be measured; note that being measurable hinges on the additional requirement that this infimum remains consistant when you take an arbitrary subset S of the plane and then add the measure of the intersection of A and S and the measure of A - S - meaning that this sum must equal the measure of A.

"Giving" an unmeasurable set - well, that's another tricky question. It is known that the axiom of choice proves the existance of unmeasurable sets (not vice-versa, though), and it is known that standard set theoretic axioms without the axiom of choice are consistant with the axiom "all subsets of R (^n) are lebesgue-measurable" (short: LM).

None of these known results, strictly speaking, prevent the possibility of someone finding an ingenious way to describe such a set that does not rely on the axiom of choice. However, any such method would require means that generally are not encountered in "day-to-day" mathematics, as many of them do not require AoC and thus are consistant with LM. For instance, any unmeasurable set can be neither open nor closed in R, nor the countable union or intersection of open or closed sets, nor the complement of such a set, or any combination of these, as all those are Lebesgue-measurable.

Of course, one can sort of "give" an example of an unmeasurable set; the simplest and most broadly known example is Vitali sets. The idea is (a few more details are found on wikipedia, http://en.wikipedia.org/wiki/Vitali_set) to look at R/Q (as additive groups) and choose (with AoC) a representative of each equivalence class in [0,1]. One can then show that this set cannot be Lebesegue-measurable.

These sets have nothing to do with the original question here, though.

[skeptical scientist]

So what you're saying is, if the Axiom of Choice is false then no 4-coloring exists...

Not exactly. The axiom LM (which contradicts the axiom of choice, but which is consistent with ZF, i.e. the other axioms of ZFC) implies that no four-coloring exist, but I don't think the negation of choice alone is known to imply that no 4-coloring exists. (Again, it could be that ZF/ZFC already implies that no four-coloring exists, but this is unknown.)

and therefore we can't construct it if the Axiom of Choice is correct (due to the fact that any such construction would be able to be done without the Axiom of Choice)? I don't like those problems.

That depends what you mean by "construct". That the axiom of choice appears necessary suggests that any 4-coloring which may exist would in some sense require many arbitrary choices to be made, but there are still things using the axiom of choice that feel similar to constructions.

Note the large amount of weasel-words in this post. When talking about open problems, there tend to be unanswered questions hanging around. (Maybe you'll be able to answer them.)

[tomtom2357]

Thanks, so you could construct one of the colors in the four colouring to appear only when any of the other colors appearing would be contradictory? Also, using Goplat's proof of the non-existence of a three coloring, could you prove that the 4th color will appear at a unit distance form every point? Would this lead to anything interesting?

[skeptical scientist]

Thanks, so you could construct one of the colors in the four colouring to appear only when any of the other colors appearing would be contradictory?

Sort of. Let c be the largest chromatic number of any finite unit distance plane graph. From the arguments already given, we know that 4≤c≤7, but the exact value of c is unknown. With the axiom of choice, you can prove that there is a coloring of the plane with c-colors such that no pair of points one unit apart have the same color.

Spoiler:

One proof goes as follows:

Call a partial c-coloring of the plane f: X -> c (where X is a subset of R²) weakly acceptable if no pair of points one unit apart are assigned the same color. Call a partial c-coloring of the plane f: X -> c acceptable if for every finite subset A of the plane, there is a weakly acceptable coloring g: X U A -> c which extends f. The empty function is acceptable by the choice of c, and we can partially order the set of acceptable c-colorings by f≤g if g extends f. This is a nonempty partial order.

Lemma 1: Given some chain of acceptable colorings, their union is also an acceptable coloring.
Proof of lemma 1: Suppose not, and let f: X -> c be the union of a chain which is not acceptable, and let A be a minimal finite subset of the plane such that f can't be extended to a weakly acceptable coloring g: X U A -> c. Then for each of the (finitely many) possible colorings h_i (1≤i≤N) of A\X, there is some element x_i of A\X and some point y_i at unit distance from x_i with f(y_i)=h_i(x_i), which prevents the extension f U h_i from being weakly acceptable. Thus the restriction of f to the finite set {y₁...y_N} is already not acceptable. But since f is the union of a chain of acceptable colorings, some element of the chain must already extend the restriction of f to the finite set {y₁...y_N}, a contradiction.

Now, based on lemma 1, we can apply Zorn's lemma to the partial ordering of acceptable colorings to get a maximal acceptable coloring.

Lemma 2: A maximal acceptable coloring must be total.
Proof of lemma 2: Suppose not, and let f: X -> c be a non-total maximal acceptable coloring, and x in R² \ X. Then f has a weakly acceptable extension to X U {x}, but no acceptable extension to X U {x}, so for each color 1≤i≤c that might be assigned to x in the extension, there is some finite set A_i such that extending f by assigning color i to x has no weakly acceptable extension to X U {x} U A_i. Then f has no weakly acceptable extension to X U {x} U A₁ U ... U A_c, contradicting the acceptability of f.

By lemmas 1 and 2, together with Zorn's lemma, a maximal acceptable coloring exists, and defines a coloring of the plane graph with c colors.

Using the same idea of the proof of acceptable colorings, one can get a c-coloring of the plane graph using transfinite recursion as follows: choose a new point in the plane, and assign that point a color such that the color assignments made so far defines an acceptable partial coloring. Repeat for each ordinal until the entire plane is colored.

If c is really 4, then you can 4-color the plane graph in this way (using AoC), even though LM implies the chromatic number of the plane is at least 5. However, it may be that c is really 5, 6, or 7, and in fact if this is the case, there is a nice finite example which demonstrates that c is at least that large.

[tomtom2357]

I have an idea. How about we try to make a 4-coloring of finite area, and slowly increase the area, and see if a contradiction exists. For example, I can color a square of area <2 easily with four colors, just divide it up into 4 quadrants and color each of those a different color. But can we do it for area 2 and above?

[Deedlit]

Well, I can color area 2 - color quadrant 1 (including the boundary) color 1 except for the center of the square C. Color the remaining points of quadrant 2 and 3 colors 2 and 3 respectively, except for C. Color quadrant 4 color 4, including C but not the opposite corner. Color the remaining point color 1.

Not sure how to handle area greater than 2. I imagine you quickly run into impossibility of doing it with regions.

[tomtom2357]

If anyone comes up with a coloring for a square of area>2, then I will uhhhh *tries to think of something* *fails*, oh well, I'll be very grateful at least.

[jaap]

Well, I can color area 2 - color quadrant 1 (including the boundary) color 1 except for the center of the square C.

Quadrant 1 has two pairs of opposite corners at distance 1. Your trick of recolouring C takes care of one pair, but not the other.

[tomtom2357]

For those corners, what we have to do is make that point the color of the quadrant counterclockwise to it. Then those points are all colored differently to each other. And we have 4-colored the square!

[Deedlit]

Yeah, it's easy to do, I just misstated it.

[tomtom2357]

Can anyone do it for square of area>2? Okay then, how about this: Can you prove that our 4-coloring of the square of area 2 is the only one possible (assuming that permutations of colors are allowed, and rotations and reflections and finally, the coloring for the center edges are allowed to change)? If that is true, then when you make the area>2, none of the 4 colors can work, and we have disproved the 4-coloring!

[Proginoskes]

Can anyone do it for square of area>2?

Check out http://www.cs.umd.edu/~kruskal/papers/papers.html (Clyde Kruskal's page); you want the paper "The chromatic number of the plane: The Bounded Case".

[tomtom2357]

So those people have basically disproved the four coloring?

[jestingrabbit]

So those people have basically disproved the four coloring?

What?? Read the damn paper. It refers to 4 colourings only in for a page (section 5), and the only thing that it gives is a couple of examples of nice colourings of small rectangles. It doesn't prove, or say, that larger such colourings are impossible.

[tomtom2357]

Okay, sorry. I have another idea of how to prove/disprove the four-coloring of the plane. We have an infinitely long strip of width x. If we can show that there is no four coloring for that strip, then we have disproved the 4-coloring! I have a solution for x<=SQRT(8)/3, simply have rectangles of width x, and length 1/3, and the left edge is defined to be on the rectangle and the right edge is defined to be off the rectangle. Is there a way to 4-color a wider strip?

[tomtom2357]

Okay, the best that I have so far is that I can 6-color a strip of width sqrt(3) (just put two 3-colored strips on top of each other)

[tomtom2357]

I have a new idea for this problem. With any finite amount of points it is relatively easy to decide how many colors they need. Now, you can decide how many colors you need to color n points fitting the condition of being in a plane. So let f(n) be the maximum amount of points you need for any set of n points in the plane. It is easy to see that f(1)=1, f(2)=2, f(3)=3, f(4)=3, and f(7)=4, and this function is well defined as there are only a finite number of cases you need to consider. Now if lim n->infinity f(n)>4, then we know that more colors are required, but if lim n->infinity f(n)=4, then we don't know, but we do know that any finite amount of points will only need a four coloring

[Proginoskes]

I have a new idea for this problem. With any finite amount of points it is relatively easy to decide how many colors they need.

Because ... ?

(I'm serious here. Coloring is known to be NP-complete.)

Now, you can decide how many colors you need to color n points fitting the condition of being in a plane. So let f(n) be the maximum amount of points you need for any set of n points in the plane. It is easy to see that f(1)=1, f(2)=2, f(3)=3, f(4)=3, and f(7)=4, and this function is well defined as there are only a finite number of cases you need to consider. Now if lim n->infinity f(n)>4, then we know that more colors are required, but if lim n->infinity f(n)=4, then we don't know, but we do know that any finite amount of points will only need a four coloring

Something like this has been known for decades:

If there is a number K such that every finite "unit distance" graph is K-colorable, then the entire plane is K-colorable.

One of Erdos's many results ...

[skeptical scientist]

Something like this has been known for decades:

If there is a number K such that every finite "unit distance" graph is K-colorable, then the entire plane is K-colorable.

One of Erdos's many results ...

In fact, I gave a proof earlier in this very thread.

On a semi-related note, does anyone know an algorithm which, given some description of a graph, will decide whether it's embeddable in the unit-distance plane graph?

[phlip]

Because ... ?

(I'm serious here. Coloring is known to be NP-complete.)

Well, he did say relatively easy... compared to an problem involving infinities, a finite NP problem that can provably be brute-forced is easy by comparison.

[jestingrabbit]

Something like this has been known for decades:

If there is a number K such that every finite "unit distance" graph is K-colorable, then the entire plane is K-colorable.

One of Erdos's many results ...

In fact, I gave a proof earlier in this very thread.

On a semi-related note, does anyone know an algorithm which, given some description of a graph, will decide whether it's embeddable in the unit-distance plane graph?

Sadly, I don't think they're closed under taking minors, so we can't rely on

http://en.wikipedia.org/wiki/Robertson-Seymour_theorem

There are clearly a few easy forbidden subgraphs, like K_4, or a square pyramid, but that's not going to get us anywhere quickly imo.

It is the right question though. The answer is probably something to do with triangles.

/stating the obvious.

[tomtom2357]

I have a new idea for this problem. With any finite amount of points it is relatively easy to decide how many colors they need.

Because ... ?

(I'm serious here. Coloring is known to be NP-complete.)

Well, at least it is easier than the problem for an infinite amount of points
Also, the problem has to do with more than triangles, as the hexagonal lattice of points can be 3-colored, but you are right, triangles have a lot to do with it