Drawing Blanks

Premature Optimization is a Prerequisite for Success

Coloring of an infinite map: inductive solution

with one comment

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

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

Definitions:

Let’s call a proper coloring of a set S extendable if for any finite set E it can be extended to S U E.

If a coloring is not extendable then there exists a finite set D (a “dead end” set) such that our coloring can not be extended to S U D.

Inductive Step Lemma:

Let C be an extendable coloring of a set S. Let r be a single region. There exists an extendable extension of C to S U {r}.

Proof of the Lemma:

C has at most 4 extensions to S U {r}. Assume none of them is extendable. So each of them has a dead end set on which it can’t be extended. The union of those dead ends would be a dead end for C, so C would not be extendable. QED.

“Any finite map can be properly colored” basically means that the coloring of the empty set is extendable.

Let’s number our regions: r_1, r_2, …. Let R_n be the set of the first n regions. The coloring of the empty set extends to R_1. And by the lemma, it extends to all R_n. The union of all these extensions gives us a coloring of the whole map.

CONTINUE READING:

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

Advertisements

Written by bbzippo

01/20/2011 at 3:14 am

Posted in math

One Response

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: