wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The infinite four-color theorem
        
(Message started by: Deedlit on Jun 1^st, 2005, 11:24pm)

Title: The infinite four-color theorem
Post by Deedlit on Jun 1^st, 2005, 11:24pm

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

Title: Re: The infinite four-color theorem
Post by Aryabhatta on Jun 2^nd, 2005, 10:26am

I don't know the proof you have in mind, but I think this should be in the Putnam Section.

Title: Re: The infinite four-color theorem
Post by Obob on Jun 2^nd, 2005, 12:56pm

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.

Title: Re: The infinite four-color theorem
Post by Deedlit on Jun 2^nd, 2005, 6:25pm

Right, but I was looking for someone coming up with an elementary argument by his or herself.

There are certainly multiple short proofs...

Title: Re: The infinite four-color theorem
Post by Eigenray on Jun 4^th, 2005, 12:19pm

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

Title: Re: The infinite four-color theorem
Post by Deedlit on Jun 4^th, 2005, 11:18pm

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

Title: Re: The infinite four-color theorem
Post by Obob on Jun 5^th, 2005, 11:27am

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.

Title: Re: The infinite four-color theorem
Post by StonedAgain on Jun 5^th, 2005, 12:14pm

I wonder if some variant of analytic continuation could be used to show that the same result holds but extended indefinitely. Just and idea.

Title: Re: The infinite four-color theorem
Post by Deedlit on Jun 5^th, 2005, 3:22pm

Despite what I said about proofs from different branches of mathematics, I would be quite shocked if we could work in holomorphic functions! ;)

Title: Re: The infinite four-color theorem
Post by Logix128 on Jun 20^th, 2005, 1:03am

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.

Title: Re: The infinite four-color theorem
Post by Jon on Jun 20^th, 2005, 1:10am

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

Title: Re: The infinite four-color theorem
Post by Barukh on Jun 20^th, 2005, 4:59am

on 06/20/05 at 01:10:16, Jon wrote:

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" (ftp://ftp.math.gatech.edu/pub/users/thomas/fcdir/npfc.ps)? Introduction is sufficient to get an impression.

Title: Re: The infinite four-color theorem
Post by Icarus on Jun 20^th, 2005, 3:23pm

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.

Title: Re: The infinite four-color theorem
Post by Nigel_Parsons on Jul 17^th, 2005, 11:42am

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

Title: Re: The infinite four-color theorem
Post by JocK on Jul 19^th, 2005, 3:56pm

on 07/17/05 at 11:42:05, 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 06/04/05 at 23:18:19, 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? ;)

Title: Re: The infinite four-color theorem
Post by Nigel_Parsons on Jul 22^nd, 2005, 1:07pm

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.

Title: Re: The infinite four-color theorem
Post by JocK on Jul 22^nd, 2005, 1:46pm

on 07/22/05 at 13:07:16, 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 :) )

Title: Re: The infinite four-color theorem
Post by rmsgrey on Jul 23^rd, 2005, 9:29am

on 07/22/05 at 13:46:42, 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.

Title: Re: The infinite four-color theorem
Post by Deedlit on Aug 2^nd, 2005, 8:38pm

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.

Title: Re: The infinite four-color theorem
Post by gorckat on Aug 19^th, 2005, 2:12pm

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

Title: Re: The infinite four-color theorem
Post by Cahit on Dec 17^th, 2005, 12:50am

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

Title: Re: The infinite four-color theorem
Post by Deedlit on Dec 17^th, 2005, 4:37am

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.

Title: Re: The infinite four-color theorem
Post by Cahit on Dec 17^th, 2005, 9:56am

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.

Title: Re: The infinite four-color theorem
Post by Deedlit on Dec 18^th, 2005, 4:34am

on 12/17/05 at 09:56:45, Cahit wrote:

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?

Title: Re: The infinite four-color theorem
Post by Cahit on Dec 19^th, 2005, 12:29am

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.

Title: Re: The infinite four-color theorem
Post by Icarus on Dec 19^th, 2005, 7:16pm

Since you are a member, you are able to correct your posts. Just click on the "Modify" button in the upper right hand corner of the post you want to change.

Title: Re: The infinite four-color theorem
Post by Deedlit on Dec 20^th, 2005, 6:03am

You still have the same problem - You're picking random graphs, and coloring them in a certain way, without telling us how you definitively choose that coloring.

What we need are step-by-step instructions that we could use to take any graph and color it, without any ambiguity.

As for why you need to pick the safe color beforehand - your Node Coloring Rule says "avoid coloring with the safe color if you can". What use is that rule if you color a node before you know what the safe color is?

Title: Re: The infinite four-color theorem
Post by Cahit on Dec 20^th, 2005, 8:18am

The graph G is not random but rather the worst case possible with respect to 3-coloring of the spiral-segment.

I will try to write in more detail in my next post.

P.S. Another point once the safe colors have been decided it will remain same till the end of the spiral-coloring of G. As my previous example shows this can only be clarified after the coloring of vertex v_6.

Title: Re: The infinite four-color theorem
Post by Cahit on Dec 21^st, 2005, 4:40am

Here is a more elaborated explanation of the selection of safe colors in spiral-chain coloring.

Let v_1,v_2,...,v_k be the set of vertices of the spiral chain S.

Consider T_1 ---> {v_1,v_2,v_3} and T_2 ---> {v_1,v_3,v_4}, where T_1 and T_2 are triangles (cycle of length three) such that T_1 U T_2 ---> theta subgraph in G. Furthermore let the vertices v_4,v_5,....,v_k induce a maximal outerplanar subgraph G_o and finally the vertices v_1,v_2,v_3,v_k induce a K_4.

Spiral chain coloring:

v_1 --->R, v_2 --->B, v_3 --->Y (spiral segment S_1).

Hence C_1 ={R,B,Y}.

Put v_4 --->B (Note that v_4 cannot be colored by G because of the K_4 vertices).

On the otherhand we have to put v_k --->G since together with v_4 --->B these are the only possible vertex coloring in G_o. Now the other vertices of the maximal outerplanar subgraph of G can be colored with the 3-color classes C_2,1 = {B,G,Y} or C_2,2= {B,G,R}.

In either cases G (Green) would be the safe color of the spiral-segment S_2.

The bottom lines are the followings:

1. The complete subgraph K_4 in G forces us to assign a new safe color.

2. In fact K_4 in maximal planar graph can be avoided i.e., degree three vertices, since G originally assumed to be internally 5-connected (see Appel and Haken proof.)

Title: Re: The infinite four-color theorem
Post by Cahit on Dec 30^th, 2005, 1:11am

Perhaps it is not the right place but definitly the right time to ask:

"Is the year 2005 succesful and fruitful from point of an mathematician?"

Here are some hints:

1. The Jordan Curve Theorem: A closed curve divides a plane into the inside and outside areas.

(Stated and incompletely proved by Jordan , 1887)

Computer aided proof is given by Trybulec and Takeuchi in 2005.

2. Four Color Theorem: Any map in a plane can be colored using four-colors in such a way that regiong sharing a common boundary do not share the same color.

(Stated by Guthrie, 1853)

Computer aided proofs first by Appel and Haken, 1977 and then by Robertson, Sanders, Seymour, Thomas, 1996.

Computer verification of the second computer-aided proof is given by Gonthier, 2004.

Kepler Sphere Packing Theorem (?). Cubic and hexagonal close packing is the densest possible packing.

(Stated by Kepler, 1611).

Computer aided proof by Hales, 1998.

My new year card is attached.

Title: Re: The infinite four-color theorem
Post by Icarus on Dec 30^th, 2005, 8:56pm

Based on what I can find, I am not sure I agree with the assessment that the Jordan Curve Theorem was not fully proved until Trybulec and Takeuchi finished their work. From what I read in the synopsis, they claim that they were unable to back all the references down to hard proofs, but it sounds like at least part of this is due to lost references. Whether or not the missing references were inadequate to finish the proof with complete rigor cannot be known unless they are discovered. It is also possible (even likely) that there are proofs that they did not discover. Some of these may be rigorous. I know of a fairly elementary proof that a simple closed curve divides the plane into at least 2 components, which is based on the Cauchy Integral formula. The other half of the proof - that there are at most 2 components - does not seem likely to me to require computer checking.

I do not mean to devalue the significance of Trybulec and Takeuchi's work, but I am not sure that I am willing to accept the claim that they are the first to fully prove Jordan's theorem.

Title: Re: The infinite four-color theorem
Post by Cahit on Dec 31^st, 2005, 12:21am

Justin Mullins has an art exhibition on "Mathematical Photography" and named a figure from the (classical) proof of the four color theorem as "ugliness"

(http://www.justinmullins.com/home.htm).

Compare with it with my little artistic figures on spiral-chain coloring of maps at

http://www.flickr.com/photos/49058045@N00/

Title: Re: The infinite four-color theorem
Post by Cahit on Jan 10^th, 2006, 1:13am

on 12/20/05 at 06:03:16, Deedlit wrote:

You still have the same problem - You're picking random graphs, and coloring them in a certain way, without telling us how you definitively choose that coloring.

What we need are step-by-step instructions that we could use to take any graph and color it, without any ambiguity.

As for why you need to pick the safe color beforehand - your Node Coloring Rule says "avoid coloring with the safe color if you can". What use is that rule if you color a node before you know what the safe color is?

It is possible to color spiral chain with for four colors by reserving only one color as "safe color". Here is rough description of the algorithm. Let the colors 1, 2, 3 are the primary colors and select w.l.o.g. color 4 as safe color. We know that spiral chain (when there are more than one nothing has been changed in general) decomposed the maximal planar graph into a serial maximal outerplanar graph. Then we start coloring of the vertices of spiral chain with only three colors 1, 2, 3 and when we have situation color conflict e.g., (1,1), (2,2) or (3,3) we change always the current vertex color i, i=1,2,3 to 4. This strategy is a bit different than of coloring spiral-segments with three-colors and it may require of the use Kempe-switching. In short the idea here (1) Use spiral chain, (2) Use 3-coloring of the maximal outer planar subgraph in between two neighbor spiral chains. (3) when there is color conflict use safe color 4 with possibly Kempe-switching. The result is again four coloring of the maximal planar. This idea is new and complemantry with the previous spiral chain coloring.

I have just added an illustration for the idea above. I call it "spiral chain 3-plus-1 coloring" where the safe color, say "yellow" has been chosen right from the begining but used at the final step of the algorithm. The link for this illustration is

http://www.emu.edu.tr/%7Ecahit/Spiral%20Chain%203%20Plus%201%20Coloring.ppt

As you may notice that nothing much changed with my previous spiral chain coloring algorithm. That is they both color maximal planar graphs with only four colors.

Title: Re: The infinite four-color theorem
Post by Cahit on Feb 26^th, 2006, 12:53pm

This is not continuation of the discussion on my proof but an finishing touch to the original question.

Paul Erdos has an old result stated that "The chromatic number of an infinite planar graph (infinite map) G is the max chromatic number over all finite subgraphs of G. Thus 4CT also applies to infinite graphs".

P.S. I learned this from Chris Heckman (another 4CT lover) through his discussions in another group.