Class Note for MATH 410 with Professor Martin at KU
Class Note for MATH 410 with Professor Martin at KU
Popular in Course
Popular in Department
This 2 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 16 views.
Reviews for Class Note for MATH 410 with Professor Martin at KU
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
The FourColor Theorem 1 The mapcoloring problem Given a map of the continental USA or the counties of England or the school districts of Kansas or i i you want to color each of the regions so that adjacent regions never receive the same color For example the map on the left is colored correctly The map on the right is not correct because Nevada and Idaho which share a little bit of border are both colored greeni How many colors are necessary Of course the answer to this question depends on the particular mapi So what the problem is really asking is this Is there some number of colors that is always enough no matter what the map looks like We have to be a little more precise First by adjacent we mean sharing a common piece of border not just meeting at a point77i For example in the maps above it is okay that Utah and New Mexico are both colored bluei Otherwise it would be possible to construct maps that required arbitrarily high numbers of colors so the problem would make no sense Second we have to assume that each region is contiguous 7 for example the Lower and Upper Peninsulas of Michigan are not part of the same region and can have different colors Again if we allow noncontiguous regions then the problem would not have a wellde ned answeri Even with these caveats its not too hard to construct maps for which at least four colors are required The map above is an example Here s why Each two of the states California Nevada and Arizona share a common border so they need three different colors 7 say blue green and red respectively as in the lefthand gurei If we don7t want to use a fourth color then Utah has to be blue because it has a red neighbor and a green neighbor and then ldaho has to be red because it has a blue neighbor and a green neighbori But then we7re stuck when we try to color Oregon it has a neighbor of each color so we have no choice but to introduce a fourth color 2 A reformulation using graph theory Remember that a graph consists of a set of vertices and a set of edges where each edge joins two of the vertices In the mapcoloring problem we can de ne a graph whose vertices are the regions of thre map and whose edges are the pairs of regions sharing a common borderi For the map above the graph has vertices WA OR CA lD NV UT AZ CO NM and edges WAiOR WAilD ORilD ORicA ORiNV CAiNV CAiNM lDiNV lDiUT NV7UT NV7AZ UTiAZ UTicO AZiNM COiNM Every graph coming from a map in this way has to be planar That is it can be represented by a diagram in the plane dots for vertices line segments or curves for edges in which no two edges cross The border between say California and Nevada does not cross the border between Kansas and Missouri This is most emphatically not the case for all graphs Meanwhile what is a coloring Its a function whose domain is the set of vertices and whose range is the set of colors For example the rst coloring above is equivalent to the function k de ned by kWA green kOR yellow kCA blue kNV green A coloring function k is then de ned to be proper if kI ky whenever I and y form an edge So the graphtheoretic restatement of the mapcoloring problem is as follows Is there a number n such that every planar graph has a proper coloring with n or fewer colors 3 The solution It turns out that four colors are enough to color any planar graph This fact known as the Four Color Theorem or 4CT has a long and complicated you might say colorful history 0 1852 English student Francis Guthrie proposes the problem Prominent English mathematicians of the time such as Augustus De Morgan and Arthur Cayley get interested o 1879 Alfred Kempe publishes a proof of the FourColor Theorem 0 1890 Percy Heawood nds a subtle aw in Kempe s proof On the other hand Heawood is able to prove that E colors are always enough 0 1891976 Lots of people publish proofs some serious many crankyl all of them awed in some way or other On the plus side large areas of graph theory perfect graphs chromatic polynomials are developed in an attempt to prove the 4CT these ideas turn out to be useful in totally different contexts o 1976 Kenneth Appel and Wolfgang Haken publish the rst widely accepted proof of the 4CT Their proof relies partly on some of Kempe7s ideas but is controversial because they reduce the theorem to checking only 1936 cases for which they use 7 horrorsl 7 a computer Debate rages over whether Appel and Hakenls argument constitutes a valid proof As time goes on the mathematical community comes to accept the method even though mistakes are found in the details Computeraided proof becomes more and more a part of research mathematics 0 1996 Robertson Sanders Seymour and Thomas publish an improved proof with the same general structure as the AppelHaken proof but simpler and involving fewer cases They also provide an ef cient algorithm for coloring any planar graph Source code for checking the cases is available on the Web so you can prove the theorem yourself at home For the juicy details see httpwwwmathgatecheduNthomasFCfourcolorhtml 1Probably because of its simplicity and notoriety the 4CT is one of those theorems that everyone tries to prove not unlike Fermat7s Last Theorem The recycling bins of mathematics departments and journals are full of rejected manuscripts that claim to give proofs of the 4CT
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'