Drawing Blanks

Premature Optimization is a Prerequisite for Success

Coloring of an infinite map

with 2 comments

Assume that any finite map on the plane can be colored using 4 colors. Prove that any map on the plane can be colored using 4 colors.

Hints:

  • An infinite map is properly colored if every finite subset of it is properly colored.
  • The set of regions on the map is countable.

I think that this problem is very instructive and it touches some important foundational concepts. So rather than just presenting a solution, I’d like to try and reconstruct the thought process and demonstrate the emergence of those concepts.

First, let’s notice that those hints that I gave may both lead and mislead us. For example, one may be tempted to come up with non-solutions like these:

  1. Non-solution: Since (any finite subset can be properly colored) and (if any finite subset is properly colored then the whole map is properly colored), it immediately follows that the whole map can be properly colored.
  2. Non-solution: Since the set of regions is countable (r_1, r_2, …), and for any n we can color the set {r_1, …, r_n}, it immediately follows that we can color the whole map.

In the first non-solution the fallacy is that the fact that we can find a proper coloring for each finite subset doesn’t mean we can find one for all of them. This in fact is what we are trying to prove. Just like the fact that a function is continuous at every point doesn’t guarantee that it is uniformly continuous. If we can find a delta for the given epsilon at each point, we don’t  necessarily have one “blanket” delta. It is only guaranteed to exist on a compact domain… So we are trying to prove some sort of compactness property of planar maps with respect to coloring. Really, it is compactness that allows us to reduce properties of infinite sets to properties of their finite subsets.

The second non-solution is an attempt to apply induction, but it neglects to demonstrate the inductive step. If we could show how to extend a proper coloring of {r_1, …, r_n} to a proper coloring of {r_1, …, r_n+1} then we would have a recipe for coloring each region that would be the “blanket” coloring that would satisfy all finite subsets.

In the next post I will give an inductive proof. Then I will present a much simpler proof that demonstrates the compactness of the map with respect to coloring by using compactness of some other space.

Then (if I still have inspiration) I’d like to show how the Axiom of Choice allows to “compactify” uncountable sets. And then I’m planning to mention the mother of all compactness: the compactness in Model Theory, and its implications. And did I mention that I have no clue about all this stuff 🙂 I am not sharing knowledge or wisdom, but the excitement of exploration 🙂 Cabbages and kings, you know, and men and cats and cops (anagram of compactness)

CONTINUE READING:

https://bbzippo.wordpress.com/2011/01/20/coloring-of-an-infinite-map-inductive-solution/

https://bbzippo.wordpress.com/2011/01/21/coloring-of-an-infinite-map-proof-by-compactness/

Advertisements

Written by bbzippo

01/18/2011 at 7:14 am

Posted in math

2 Responses

Subscribe to comments with RSS.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: