Plane colorings

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Plane colorings

Postby Desiato » Tue Jan 03, 2012 1:01 am UTC

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.

Goplat
Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

Re: Plane colorings

Postby Goplat » Tue Jan 03, 2012 6:19 am UTC

Spoiler:
No, it is not possible. Proof:

Construct an isosceles triangle with corners named A, B1, and B2 such that B1 and B2 have a distance of 1 unit apart from each other and both of them have a distance of sqrt(3) units from A. Since B1 and B2 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:
Image
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.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Plane colorings

Postby jestingrabbit » Tue Jan 03, 2012 6:49 am UTC

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Plane colorings

Postby Proginoskes » Tue Jan 03, 2012 6:52 am UTC

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 [imath]\sqrt{3}[/imath], 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!

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Plane colorings

Postby jestingrabbit » Tue Jan 03, 2012 7:02 am UTC

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.

User avatar
jaap
Posts: 2077
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Plane colorings

Postby jaap » Tue Jan 03, 2012 7:10 am UTC

The solution Goplat described works in higher dimensions too to show that at least n+2 colours are necessary for Rn.
Spoiler:
In R3, 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 R3 at least 5 colours are needed for such a colouring.
Similarly, in Rn 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 R2 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 R3 you could probably use a rhombic dodecahedron to show that 13 colours suffice.
Last edited by jaap on Tue Jan 03, 2012 10:51 am UTC, edited 1 time in total.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Tue Jan 03, 2012 8:56 am UTC

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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Plane colorings

Postby skeptical scientist » Tue Jan 03, 2012 5:44 pm UTC

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

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Wed Jan 04, 2012 2:13 am UTC

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.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Plane colorings

Postby Desiato » Wed Jan 04, 2012 6:30 am UTC

skeptical scientist wrote: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!

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Plane colorings

Postby Proginoskes » Wed Jan 04, 2012 6:31 am UTC

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.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Plane colorings

Postby Desiato » Thu Jan 05, 2012 12:29 am UTC

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 4-coloring of the plane, at least one of its color sets will be unmeasurable.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Thu Jan 05, 2012 6:29 am UTC

What do you mean by not measurable?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Plane colorings

Postby Proginoskes » Thu Jan 05, 2012 6:56 am UTC

tomtom2357 wrote: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 )

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Plane colorings

Postby skeptical scientist » Thu Jan 05, 2012 7:03 am UTC

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

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Thu Jan 05, 2012 7:54 am UTC

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? :?:
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 947
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Plane colorings

Postby mfb » Thu Jan 05, 2012 1:35 pm UTC

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
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Thu Jan 05, 2012 2:01 pm UTC

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. :cry:
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Plane colorings

Postby Desiato » Fri Jan 06, 2012 12:02 am UTC

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

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Plane colorings

Postby skeptical scientist » Fri Jan 06, 2012 1:55 am UTC

tomtom2357 wrote: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. :cry:

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

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Fri Jan 06, 2012 5:06 am UTC

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?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Plane colorings

Postby skeptical scientist » Fri Jan 06, 2012 7:21 am UTC

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 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 R2) 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 hi (1≤i≤N) of A\X, there is some element xi of A\X and some point yi at unit distance from xi with f(yi)=hi(xi), which prevents the extension f U hi from being weakly acceptable. Thus the restriction of f to the finite set {y1...yN} 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 {y1...yN}, 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 R2 \ 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 Ai such that extending f by assigning color i to x has no weakly acceptable extension to X U {x} U Ai. Then f has no weakly acceptable extension to X U {x} U A1 U ... U Ac, 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.
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

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Fri Jan 06, 2012 8:16 am UTC

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?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Deedlit
Posts: 91
Joined: Sun Mar 08, 2009 2:55 am UTC

Re: Plane colorings

Postby Deedlit » Fri Jan 06, 2012 9:55 am UTC

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
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Fri Jan 06, 2012 10:40 am UTC

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. :D
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
jaap
Posts: 2077
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Plane colorings

Postby jaap » Fri Jan 06, 2012 11:57 am UTC

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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Fri Jan 06, 2012 12:02 pm UTC

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! :D
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Deedlit
Posts: 91
Joined: Sun Mar 08, 2009 2:55 am UTC

Re: Plane colorings

Postby Deedlit » Fri Jan 06, 2012 12:10 pm UTC

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

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Fri Jan 06, 2012 2:00 pm UTC

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!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Plane colorings

Postby Proginoskes » Sat Jan 07, 2012 7:23 pm UTC

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

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Sun Jan 08, 2012 5:01 am UTC

So those people have basically disproved the four coloring? :D
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Plane colorings

Postby jestingrabbit » Sun Jan 08, 2012 7:18 am UTC

tomtom2357 wrote:So those people have basically disproved the four coloring? :D


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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Sun Jan 08, 2012 7:40 am UTC

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?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Tue Jan 24, 2012 10:33 am UTC

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)
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Tue Mar 20, 2012 4:57 am UTC

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.

User avatar
Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Plane colorings

Postby Proginoskes » Tue Mar 20, 2012 6:24 am UTC

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

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Plane colorings

Postby skeptical scientist » Tue Mar 20, 2012 6:40 am UTC

Proginoskes wrote: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?
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

User avatar
phlip
Restorer of Worlds
Posts: 7550
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Plane colorings

Postby phlip » Tue Mar 20, 2012 6:48 am UTC

Proginoskes wrote: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.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Plane colorings

Postby jestingrabbit » Tue Mar 20, 2012 6:51 am UTC

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 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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Plane colorings

Postby tomtom2357 » Tue Mar 20, 2012 6:56 am UTC

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 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
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests