Plane colorings
Moderators: jestingrabbit, Moderators General, Prelates
Plane colorings
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 [imath]R^n[/imath]? Note that I don't have a complete solution for the bonus question at this time.
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 [imath]R^n[/imath]? Note that I don't have a complete solution for the bonus question at this time.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Plane colorings
I had a slightly different proof.
That extended problem looks pretty nontrivial.
Spoiler:
That extended problem looks pretty nontrivial.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Proginoskes
 Posts: 313
 Joined: Mon Nov 14, 2011 7:07 am UTC
 Location: Sitting Down
Re: Plane colorings
Spoiler:
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Plane colorings
Proginoskes wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Plane colorings
The solution Goplat described works in higher dimensions too to show that at least n+2 colours are necessary for R^{n}.
The more difficult question is how many colours are actually sufficient. I don't have a good answer to that.
Spoiler:
The more difficult question is how many colours are actually sufficient. I don't have a good answer to that.
Spoiler:
Last edited by jaap on Tue Jan 03, 2012 10:51 am UTC, edited 1 time in total.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
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.
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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Plane colorings
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Plane colorings
skeptical scientist wrote:Spoilers:
http://en.wikipedia.org/wiki/HadwigerNelson_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
 Posts: 313
 Joined: Mon Nov 14, 2011 7:07 am UTC
 Location: Sitting Down
Re: Plane colorings
tomtom2357 wrote: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.
Re: Plane colorings
tomtom2357 wrote: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 4coloring of the plane, at least one of its color sets will be unmeasurable.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
What do you mean by not measurable?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 Proginoskes
 Posts: 313
 Joined: Mon Nov 14, 2011 7:07 am UTC
 Location: Sitting Down
Re: Plane colorings
tomtom2357 wrote:What do you mean by not measurable?
"In mathematics, a nonmeasurable 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/Nonmeasurable_set )
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Plane colorings
tomtom2357 wrote: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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
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 nonmeasureable 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?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Plane colorings
I think what you mean with "very small" would still be measureable.
The linked wikipedia articles gives you a definition of nonmeasureable 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.
The linked wikipedia articles gives you a definition of nonmeasureable 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.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
So what you're saying is, if the Axiom of Choice is false then no 4coloring 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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Plane colorings
"Measurable" is generally taken to mean Lebesguemeasureable; 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 viceversa, 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 lebesguemeasurable" (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 "daytoday" 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 Lebesguemeasurable.
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 Lebeseguemeasurable.
These sets have nothing to do with the original question here, though.
"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 viceversa, 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 lebesguemeasurable" (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 "daytoday" 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 Lebesguemeasurable.
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 Lebeseguemeasurable.
These sets have nothing to do with the original question here, though.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Plane colorings
tomtom2357 wrote:So what you're saying is, if the Axiom of Choice is false then no 4coloring 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 fourcoloring exist, but I don't think the negation of choice alone is known to imply that no 4coloring exists. (Again, it could be that ZF/ZFC already implies that no fourcoloring 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 4coloring 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 weaselwords in this post. When talking about open problems, there tend to be unanswered questions hanging around. (Maybe you'll be able to answer them.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
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 nonexistence 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?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Plane colorings
tomtom2357 wrote: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 ccolors such that no pair of points one unit apart have the same color.
Spoiler:
Using the same idea of the proof of acceptable colorings, one can get a ccoloring 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 4color 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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
I have an idea. How about we try to make a 4coloring 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?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Plane colorings
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.
Not sure how to handle area greater than 2. I imagine you quickly run into impossibility of doing it with regions.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Plane colorings
Deedlit wrote: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.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
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 4colored the square!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Plane colorings
Yeah, it's easy to do, I just misstated it.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
Can anyone do it for square of area>2? Okay then, how about this: Can you prove that our 4coloring 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 4coloring!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 Proginoskes
 Posts: 313
 Joined: Mon Nov 14, 2011 7:07 am UTC
 Location: Sitting Down
Re: Plane colorings
tomtom2357 wrote: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".

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
So those people have basically disproved the four coloring?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Plane colorings
tomtom2357 wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
Okay, sorry. I have another idea of how to prove/disprove the fourcoloring 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 4coloring! 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 4color a wider strip?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
Okay, the best that I have so far is that I can 6color a strip of width sqrt(3) (just put two 3colored strips on top of each other)
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
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
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 Proginoskes
 Posts: 313
 Joined: Mon Nov 14, 2011 7:07 am UTC
 Location: Sitting Down
Re: Plane colorings
tomtom2357 wrote: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 NPcomplete.)
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 Kcolorable, then the entire plane is Kcolorable.
One of Erdos's many results ...
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Plane colorings
Proginoskes wrote:Something like this has been known for decades:
If there is a number K such that every finite "unit distance" graph is Kcolorable, then the entire plane is Kcolorable.
One of Erdos's many results ...
In fact, I gave a proof earlier in this very thread.
On a semirelated note, does anyone know an algorithm which, given some description of a graph, will decide whether it's embeddable in the unitdistance plane graph?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 phlip
 Restorer of Worlds
 Posts: 7554
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Plane colorings
Well, he did say relatively easy... compared to an problem involving infinities, a finite NP problem that can provably be bruteforced is easy by comparison.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Plane colorings
skeptical scientist wrote:Proginoskes wrote:Something like this has been known for decades:
If there is a number K such that every finite "unit distance" graph is Kcolorable, then the entire plane is Kcolorable.
One of Erdos's many results ...
In fact, I gave a proof earlier in this very thread.
On a semirelated note, does anyone know an algorithm which, given some description of a graph, will decide whether it's embeddable in the unitdistance plane graph?
Sadly, I don't think they're closed under taking minors, so we can't rely on
http://en.wikipedia.org/wiki/RobertsonSeymour_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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Plane colorings
Proginoskes wrote:tomtom2357 wrote: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 NPcomplete.)
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 3colored, but you are right, triangles have a lot to do with it
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Who is online
Users browsing this forum: No registered users and 9 guests