Besides finishing my own qualifying paper and proofreading reams of pages of someone else’s work (ahem!), I’ve also been busy this past month as a “behind the scenes” organizer for the Symposium on Logical Foundations of Computer Science (http://lfcs.info/). The first talk was a presentation of a proof of the Four Color Theorem, which states that “any planar map can be coloured with only four colors.” A planar map is one that doesn’t wrap (e.g. a wall map as opposed to a globe), and the coloring has to be done such that no two adjacent regions which touch at more than one point end up being the same color. So Arizona and Colorado, which touch at only one point, could be the same color, but Arizona and Utah need to be different colors. It’s fairly easy to prove that any map can be colored this way with five colors, and there are some obvious examples of maps which can’t be colored this way with only three colors, but the question is: are four colors always enough?
According to the talk, the theorem was first proposed by a math student who was trying to color the counties of England, and noticed that it was possible with four colors. It’s a fascinating conjecture as it’s incredibly simple to grasp the basic statement of the problem, and yet it resisted a correct proof for quite some time. It was also the first major theorem to be proven with a computer (a controversial result). Anyway, the wikipedia article on the subject is a great read (be sure to follow the links to snark and Klein bottle). It’s also one of those wikipedia pages whose talk page is just as interesting as the main page — lots of mathematically-inclined amateurs think they have counter-examples, or new proofs.
Read More