Drawing Blanks

Premature Optimization is a Prerequisite for Success

Coloring of an infinite map: Proof by compactness

leave a comment »

https://bbzippo.wordpress.com/2011/01/18/coloring-of-an-infinite-map/

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

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.

Proof

Let’s number the regions: r_1, r_2, …. Let’s number the colors: 0, 1, 2, 3.

For any n there exists a coloring of {r_1, r_2, …, r_n}. Let’s encode this coloring by a real number x_n with the decimal expansion 0.c1c2…cn where each digit is the number of the color of the corresponding region.

So we have an infinite sequence {x_n} of real numbers from [0, 1/3]. By compactness, it has at least one limit point X. Easy to see that X encodes a proper coloring of the whole map.

Notice that here (unlike in the inductive case) we didn’t bother to build a self-extending tower from ground up. The limit point is guaranteed to be such a tower. If it wasn’t, it wouldn’t be possible to find a proper coloring arbitrarily close to it.

CONTINUE READING:

https://bbzippo.wordpress.com/2011/02/04/back-to-compactness/

Advertisements

Written by bbzippo

01/21/2011 at 6:14 am

Posted in math

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: