Author |
Topic: The infinite four-color theorem (Read 6781 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
The infinite four-color theorem
« on: Jun 1st, 2005, 11:24pm » |
 Quote  Modify
|
This isn't your typical math puzzle, but as it isn't that involved, but not that well known, I think it's appropriate for this forum.
A famous mathematical theorem states that any finite map can be colored in four colors so that any two adjacent countries are colored with different colors. The question is: what about infinite maps? Is four colors still enough?
(Note that "adjacent" means it shares a positive length boundary - touching at a corner doesn't count as adjacent.)
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: The infinite four-color theorem
« Reply #1 on: Jun 2nd, 2005, 10:26am » |
Quote Modify
|
I don't know the proof you have in mind, but I think this should be in the Putnam Section.
|
| « Last Edit: Jun 2nd, 2005, 10:30am by Aryabhatta » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: The infinite four-color theorem
« Reply #2 on: Jun 2nd, 2005, 12:56pm » |
Quote Modify
|
If I recall correctly, the compactness principle states that the chromatic number of any infinite graph is the supremum of the chromatic numbers of its finite subgraphs. Therefore the four-color theorem would hold for infinite planar graphs, which is same as the country-coloring problem.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The infinite four-color theorem
« Reply #3 on: Jun 2nd, 2005, 6:25pm » |
Quote Modify
|
Right, but I was looking for someone coming up with an elementary argument by his or herself.
There are certainly multiple short proofs...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: The infinite four-color theorem
« Reply #4 on: Jun 4th, 2005, 12:19pm » |
Quote Modify
|
For each face F and color c = 1,2,3,4, introduce a variable to represent "F is colored c". For each F, write a sentence saying that F is colored exactly one of the four colors. For each pair of adjacent countries, add a sentence saying they have different colors.
By the four-color theorem, any finite subset of these sentences is satisfiable. So the infinite four-color theorem follows from the compactness theorem of first-order logic (which follows from Godel's completeness theorem).
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The infinite four-color theorem
« Reply #5 on: Jun 4th, 2005, 11:18pm » |
Quote Modify
|
Cute. I assume this only works for countable graphs? Formulas are usually restricted to some countable alphabet, and besides the compactness theorem for uncountable graphs requires the axiom of choice, which I don't see how can be applied in this context.
Still, the idea was for someone to come up with an elementary argument that doesn't involve hitting it with a big hammer, like the Compactness Theorem or Godel's Completeness Theorem.
There's another neat proof from a seemingly unrelated branch of mathematics, using topology...
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: The infinite four-color theorem
« Reply #6 on: Jun 5th, 2005, 11:27am » |
Quote Modify
|
I believe the problem only makes sense for countable graphs, anyways. If a map is embedded in R^2, then every country must contain some open set. But there is no uncountable collection of disjoint open sets in the plane.
|
|
IP Logged |
|
|
|
StonedAgain
Guest
|
|
Re: The infinite four-color theorem
« Reply #7 on: Jun 5th, 2005, 12:14pm » |
Quote Modify
 Remove
|
I wonder if some variant of analytic continuation could be used to show that the same result holds but extended indefinitely. Just and idea.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The infinite four-color theorem
« Reply #8 on: Jun 5th, 2005, 3:22pm » |
Quote Modify
|
Despite what I said about proofs from different branches of mathematics, I would be quite shocked if we could work in holomorphic functions! 
|
|
IP Logged |
|
|
|
Logix128
Guest
|
|
Re: The infinite four-color theorem
« Reply #9 on: Jun 20th, 2005, 1:03am » |
Quote Modify
Remove
|
I don't think I am understanding this question correctly..what if a given country has four bordering countries? only three of them could be a separate color from the first country..let's take russia for example, it borders about 10 countries, and thus would be the same color as some of its boundary countries.
|
|
IP Logged |
|
|
|
Jon
Guest
|
|
Re: The infinite four-color theorem
« Reply #10 on: Jun 20th, 2005, 1:10am » |
Quote Modify
Remove
|
whoa let me clarify that..what i meant was are countries like russia who have two ends (that are separate from each other) count as one country or two separate countries in this scheme? because if you divide all of the once-were-soviet-union states into very fine lines and split one of them down the middle, this will create a paradox near the western piece of russia
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: The infinite four-color theorem
« Reply #11 on: Jun 20th, 2005, 4:59am » |
Quote Modify
|
on Jun 20th, 2005, 1:10am, Jon wrote:| whoa let me clarify that..what i meant was are countries like russia who have two ends (that are separate from each other) count as one country or two separate countries in this scheme? because if you divide all of the once-were-soviet-union states into very fine lines and split one of them down the middle, this will create a paradox near the western piece of russia |
|
IMHO Russia (and also US) will count as 2 countries. In fact, the Four-Colour Theorem (4CT) is stated not in terms of countries, but in terms of simply connected regions, and then re-formulated in terms of graphs.
BTW, have you seen the following "New Proof of 4CT"? Introduction is sufficient to get an impression.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: The infinite four-color theorem
« Reply #12 on: Jun 20th, 2005, 3:23pm » |
Quote Modify
|
Yes - if you allow disconnected regions to be considered as one country, then there is no upper limit to the amount of colors needed - it can always be as high as the number of countries.
It always needful to not take "colloquial" versions of the statements of theorems too seriously.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: The infinite four-color theorem
« Reply #13 on: Jul 17th, 2005, 11:42am » |
Quote Modify
|
Yes! (answering the question as phrased)
A famous mathematical theorem states that any finite map can be colored in four colors so that any two adjacent countries are colored with different colors. The question is: what about infinite maps? Is four colors still enough?
Presumably though, the proof is required.
Here's the simple version (I'm nothing, if not simple)
The usual theorem requires that any planar, finite, map can be coloured with a maximum of four colours without having adjacent areas of the same colour. My proof of the infinite case relies on the fact that the finite case has already been proven (though I can't claim to fully understand that proof.)
The usual theorem can be re-stated that any finite, planar, map can be coloured in such a way (with the constraint that no two adjacent areas share a coulour) so that all the areas at the external edge can be coloured using only three colours without breaking the above (bracketed) constraint.
This is because, at any time an additional region can be added which encompasses the perimeter of the area already coloured, as this must be of a different colour then only 3 colours are needed to colour all the previous extreme segments.
Thus even continuing building upon previous 'maps' to infinity will have the same requirement.
Nigel
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: The infinite four-color theorem
« Reply #14 on: Jul 19th, 2005, 3:56pm » |
Quote Modify
|
on Jul 17th, 2005, 11:42am, Nigel_Parsons wrote:
[..] at any time an additional region can be added which encompasses the perimeter of the area already coloured, as this must be of a different colour then only 3 colours are needed to colour all the previous extreme segments.
Thus even continuing building upon previous 'maps' to infinity will have the same requirement.
|
|
This reasoning seems to ignore the fact that 'building upon previous maps' can also be done by 'growing' one or more regions (till infinity).
on Jun 4th, 2005, 11:18pm, Deedlit wrote:
There's another neat proof from a seemingly unrelated branch of mathematics, using topology... |
|
May we use the fact that four colours suffice to colour a map on a sphere?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: The infinite four-color theorem
« Reply #15 on: Jul 22nd, 2005, 1:07pm » |
Quote Modify
|
Jock, 'Growing one more regions' must still observe the same proof & constraints, hence my comments stand.
Apropos a sphere:
Imagine any point upon the sphere which does not lie upon a boundary.
'Puncture' the map at this point, and the map can be stretched and flattened in such a way that the perimeter of the puncture becomes the perimeter of the map thus formed.
As we now have a map bounded by a perimeter of a single colour, the theorem holds.
Thus the theorem is valid for the surface of a sphere, just as for a planar map.
|
| « Last Edit: Jul 22nd, 2005, 1:22pm by Nigel_Parsons » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: The infinite four-color theorem
« Reply #16 on: Jul 22nd, 2005, 1:46pm » |
Quote Modify
|
on Jul 22nd, 2005, 1:07pm, Nigel_Parsons wrote:
Thus the theorem is valid for the surface of a sphere, just as for a planar map.
|
|
So, if the 4-colour theorem holds for a finite planar region, it also holds for a sphere.
But if it holds for a sphere, it must also hold for an infinite plane. (Any infinite planar map can be projected onto a sphere on top of the plane using straight-line projections through the top point of the sphere.)
Ergo, if it holds for a finite planar region, it must also hold for an infinite planar region.
(Well... some regions get very small when projected onto the sphere, but apart from that, I don't see a problem with this proof  )
|
| « Last Edit: Jul 22nd, 2005, 2:48pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: The infinite four-color theorem
« Reply #17 on: Jul 23rd, 2005, 9:29am » |
Quote Modify
|
on Jul 22nd, 2005, 1:46pm, JocK wrote:
So, if the 4-colour theorem holds for a finite planar region, it also holds for a sphere.
|
|
...with a finite number of regions.
A sphere with an infinite number of regions maps to a case not covered by the finite planar 4CT. Extending either proof to cover an infinite number of regions would prove the other.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The infinite four-color theorem
« Reply #18 on: Aug 2nd, 2005, 8:38pm » |
Quote Modify
|
I've been away for awhile, so this I'm responding to some old posts - my apologies.
The problem with Nigel's proof is that we color the extra region by asserting that there exists a coloring of the previous regions such that there is an allowable color for the extra one. But then, we can't say the same for the _next_ region - unless we were to recolor all the previous regions. So at best we get a sequence of unrelated colorings that cover more and more regions - that doesn't tell us how to color all the regions with a single coloring.
Rmsgrey's objection to Jock's proof is correct - maps with finitely many regions on the plane are equivalent to maps with finitely many regions on the sphere, but neither is equivalent to maps with infinitely many regions on either the plane or the sphere.
|
|
IP Logged |
|
|
|
gorckat
Newbie
Gender:
Posts: 3
|
|
Re: The infinite four-color theorem
« Reply #19 on: Aug 19th, 2005, 2:12pm » |
Quote Modify
|
Regarding Nigel's proof- isn't the starting point, and thus recoloring of the map relative, like time?
If I start in area A, then my map will have a certain pattern. If you start in a region some distance away, then the colors will be different, and possibly the pattern, but the proof should still hold, shouldn't it?
Cheers
(And please forgive my noobness, but puzzles are just fun.)
|
|
IP Logged |
|
|
|
Cahit
Newbie
Posts: 10
|
|
Re: The infinite four-color theorem
« Reply #20 on: Dec 17th, 2005, 12:50am » |
Quote Modify
|
The infinite four-color problem (theorem?) is quite interesting. We know that the finite case is a theorem (proved by the help of a computer).
I have proposed non-computer proof for 4CT in 2004 by using spiral chains in the maximal planar graph, see summary of three different proofs at
(http://www.emu.edu.tr/~cahit/THE%20FOUR%20COLOR%20THEOREM%20---%20THREE% 20PROOFS.htm).
My proof is based on three-coloring of consecutive spiral chain segments and termination condition is given in the last segment which is the outer boundary of the map (or outer cycle of the maximal planar graph). Since the map here is infinite I wonder how the termination condition would be given for any four coloring algorithm. That is will not be sure whether four colors is enough for the infinte maps. On the other hand I don`t know in what way a possible inductive proof can be applied to this problem as in the case Kempe`s fallacious proof.
Cahit
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The infinite four-color theorem
« Reply #21 on: Dec 17th, 2005, 4:37am » |
Quote Modify
|
While it is extremely unlikely that you have actually proven the 4CT, I did take a few minutes to look at your web page. However, you never clearly stated what you coloring strategy is; what's the exact definition of the "safe" color, for instance? Whatever it is, it looks like it doesn't apply to the outer layer, so that layer can be 3-colored arbitrarily - but if you do that, it's easy to force two neighboring inner vertices to the fourth color.
While examples and exposition have their place, what you really need is a precise description of your coloring strategy that is as concise and unambiguous as possible, followed by a proof that this always works that is also as concise and unambiguous as possible. Your proofs try to argue by example, and it's just not explaining the general case.
A technical point: Graphs and planar graphs do not ordinarily come with an embedding into the plane, so words like "clockwise" and "outer" don't have meaning in general. I believe "plane graphs" would be the correct term here.
|
|
IP Logged |
|
|
|
Cahit
Newbie
Posts: 10
|
|
Re: The infinite four-color theorem
« Reply #22 on: Dec 17th, 2005, 9:56am » |
Quote Modify
|
Thanks for the comment.
Let us first consider simplest maximal planar graph as an triangle T which its two edges are in the spiral-chain segment S_1. Color the vertices of T with R, Y, B (Red, Yellow, Blue) (see Fig. 2a in my web-article). Vertices surround T form the spiral-segment S_2. Notice that we have not yet decided the “safe” color yet. If we would shrink the vertices of T then we would get a wheel (if it is odd then we require three colors including the shrinked vertices, otherwise we need four colors). Then color the vertices of S_2 with Y,G,B. Then Red is a safe color with respect to spiral segment S_1 and Green is a safe color with respect to S_2. That is two 3-color classes are formed i.e., C_1={R,Y,B} and C_2={Y,G,B}. W.l.o.g. consider a maximal plane graph with a set of spiral-segments {S_1,S_2,S_3,S_4,….,S_n}.
From the argument above we color
spiral_segments S_1,S_3,S_5,… with the colors in the 3-color class C_1={R,Y,B}
and
spiral_segments S_2,S_4,S_6,… with the colors in the 3-color class C_2={Y,G,B}.
Now any maximal planar graph can be consisted of several consecutive spiral chains (here spiral-segment is a subgraph in the spiral-chain) separated with the theta-graphs.
Here theta graph in general is a maximal outerplanar graph which is three-colorable. Therefore we can apply our spiral-chain-three coloring for every spiral-chain in the graph.
Now back to strategy of the selection of the “safe” colors which is “use non-safe color whenever it is possible” in the three-coloring of each spiral-segment. I leave to the reader to extract the justification behind this selection strategy. I claim that the strategy of the use of the safe color is not unique.
The last words is about the termination condition in the spiral-coloring of the very last spiral-segment which is the outerboundary cycle with one edge being omitted. This can always be satisfied since all spiral segments in the maximal planar graph is three colorable.
That is why I mentioned in my previous post the “infinite” version of the four-color problem would not easy.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: The infinite four-color theorem
« Reply #23 on: Dec 18th, 2005, 4:34am » |
Quote Modify
|
on Dec 17th, 2005, 9:56am, Cahit wrote:Thanks for the comment.
Let us first consider simplest maximal planar graph as an triangle T which its two edges are in the spiral-chain segment S_1. Color the vertices of T with R, Y, B (Red, Yellow, Blue) (see Fig. 2a in my web-article). Vertices surround T form the spiral-segment S_2.
|
|
I thought the vertices of T were S_1?
Quote:
Notice that we have not yet decided the “safe” color yet. If we would shrink the vertices of T then we would get a wheel (if it is odd then we require three colors including the shrinked vertices, otherwise we need four colors).
|
|
Quote:
Then color the vertices of S_2 with Y,G,B. Then Red is a safe color with respect to spiral segment S_1 and Green is a safe color with respect to S_2. That is two 3-color classes are formed i.e., C_1={R,Y,B} and C_2={Y,G,B}. W.l.o.g. consider a maximal plane graph with a set of spiral-segments {S_1,S_2,S_3,S_4,….,S_n}.
|
|
You still haven't explained how you picked either the color sets or the safe colors. Anyway, don't you have to pick the safe color for a spiral before you color it, for your rule to have any meaning?
|
|
IP Logged |
|
|
|
Cahit
Newbie
Posts: 10
|
|
Re: The infinite four-color theorem
« Reply #24 on: Dec 19th, 2005, 12:29am » |
Quote Modify
|
Are the SAFE colors be selected beforehand?
Let v_1,v_2,v_3 be the vertices of the (core) triangle T in the maximal plane graph G. Color the vertices of T as before as v_1 --->R, v_2 --->B and v_3 --->Y.
Now consider additional vertices v_4,v_5,v_6 arround T with the edge set {(v_3,v_4),(v_4,v_2),(v_4,v_5),(v_5,v_2),(v_5,v_3),(v_5,v_6),(v_6,v_3),( v_6,v_4)}. Clearly v_4,v_5,v_6 are the vertices of the spiral-segment S_2.
Since (v_3,v_4) U T is a K_4 (complete graph on 4 vertices) v_4 must be colored by G (Green) and G is entitled as the SAFE color of S_2. Since v_5 is adjacent to v_2 (colored by B) and v_3 (colored by Y) we have to color it by R (Red) and since v_6 is adjacent to v_3 (colored by Y) and v_4 (colored by G) we have to color v_6 by B (Blue). Now the safe color of the spiral segment S_1 has been decided and it is Y (Yellow). This argument suggests that 'SAFE' colors should not be selected beforehand.
Further suggestions would be welcomed.
|
| « Last Edit: Dec 19th, 2005, 11:20pm by Cahit » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print