The Four Color Theorem (4CT) Emily Mis Discrete Math Final Presentation Origin of the 4CT вЂў First introduced by Francis Guthrie in the early 1850вЂ™s вЂ“ Communicated to Augustus De Morgan in 1852 вЂў First printed reference of the theorem in 1878 in the Proceedings of the London Mathematical Society вЂў The original problem was stated to be: вЂњвЂ¦the greatest number of colors to be used in coloring a map so as to avoid identity of color in lineally contiguous districts is four.вЂќ -Frederick Guthrie to the Royal Society of Edinburgh (1880) Graph Theory for the Four Color Conjecture Graph Theory for the Four Color Conjecture Graph Theory for the Four Color Conjecture Any Planar Map Is Four-Colorable Planar graph - a graph drawn in a plane without any of its edges crossing or intersecting Each vertex (A,B,C,D,E) represents a region in a graph Each edge represents regions that share a boundary вЂњIn any plane graph each vertex can be assigned exactly one of four colors so that adjacent vertices have different colors.вЂќ -Four-Color Conjecture вЂњProvingвЂќ the Conjecture вЂў A. B. Kempe in 1879 вЂ“ Found to be flawed by Heawood in 1890 вЂ“ Introduced a new technique now called KempeвЂ™s chains KempeвЂ™s Chains A four-sided region R is surrounded by Regions 1 - 4 that have already been colored by the four available colors KempeвЂ™s Chains A four-sided region R is surrounded by Regions 1 - 4 that have already been colored by the four available colors First consider all regions colored b and d. Either there is a chain of regions colored b and d connecting Region 2 and Region 4, or no such chain exists. If no chain exists, you can change the color of either Region 4 or Region 2 in order to free up the other color for the center region R. вЂњProvingвЂќ the Conjecture вЂў A. B. Kempe in 1879 вЂ“ Found to be flawed by Heawood in 1890 вЂ“ Introduced a new technique now called KempeвЂ™s chains вЂў P. G. Tait in 1880 вЂ“Found to be flawed by Peterson in 1891 вЂ“Found an equivalent formulation of the 4CT in terms of three-edge coloring No two edges coming from the same vertex share the same color вЂњProvingвЂќ the Conjecture вЂў A. B. Kempe in 1879 вЂ“ Found to be flawed by Heawood in 1890 вЂ“ Introduced a new technique now called KempeвЂ™s chains вЂў P. G. Tait in 1880 вЂ“Found to be flawed by Peterson in 1891 вЂ“Found an equivalent formulation of the 4CT in terms of three-edge coloring вЂў 1900вЂ™s brought proofs on limited sets of regions вЂ“ Increased to a 90-region proof in 1976 by Mayer other concerned parties вЂў Sir William Hamilton вЂў Arthur Cayley вЂў Lewis Carroll "A is to draw a fictitious map divided into counties. B is to color it (or rather mark the counties with names of colours) using as few colours as possible. Two adjacent counties must have different colours. A's object is to force B to use as many colours as possible. How many can he force B to use?" other concerned parties вЂў Sir William Hamilton вЂў Arthur Cayley вЂў Lewis Carroll "A is to draw a fictitious map divided into counties. B is to color it (or rather mark the counties with names of colours) using as few colours as possible. Two adjacent counties must have different colours. A's object is to force B to use as many colours as possible. How many can he force B to use?" The New Proof of the 4CT вЂў Completed by Appel and Haken in 1976 вЂ“ Based on KempeвЂ™s chains вЂ“ Required 1200 hours of computation вЂў Used mostly to perform reductions and discharges on planar configurations using KempeвЂ™s original idea of chains вЂў Introduced a collection of 1476 reducible configurations вЂ“ These configurations are an unavoidable set that must be tested to show that they are reducible вЂ“ No member of this set can appear in a minimal counterexample Discharging - Why do it? Discharging -- moving a charge along a circuit of connected vertices in order to cancel positive and negative values as much as possible Sites where a positive value remains are often part of a reducible configuration G is the smallest maximal plane graph which cannot be four-colored each vertex in G gets a charge (6-deg v) from Euler, we know that the sum of all G is 12 A charge is then moved around the circuit to change the charges of individual vertices Discharging is used to show that a certain set S is an unavoidable set WeвЂ™re not in Kansas anymore вЂў A new version of the computer-based proof was produced by Robertson, Sanders, Seymour and Thomas in 1996 вЂ“ Used a quadratic algorithm for four-color planar graphs вЂ“ Decreased the size of the unavoidable set to 633 вЂў The fears: вЂ“ Is this a movement towards computer-based proof for traditional mathematical proofs? вЂ“ Does this proof вЂњqualifyвЂќ as a proof based on the original definition of a вЂњproofвЂќ? Works Cited вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў вЂў Thomas, Robin (1998) An Update on the Four-Color Theorem, Notices of the AMS, 45: 7:848-859 Brun, Yuriy The Four Color Theorem, MIT Undergraduate Journal of Mathematics pp 21-28 Calude, Andreea (2001)The Journey of the Four Colour Theorem Through Time, The New Zealand Mathematics Magazine, 38:3:27-35 Cayley (1879) On the colouring of maps, Proceedings of the Royal Geographical Society and Monthly Record of Geography New Monthly Series, 1:4:259-261 Robertson et al (1996) A New Proof of the Four-Colour Theorem, Electronic Research Announcements of the AMS, 2:1:17-25 Mitchem, John (1981) On the History and Solution of the Four-Color Map Problem, The Two-Year College Mathematics Journal, 12:2:108116 Bernhart (1991) Review of Every Planar Map is Four Colorable by Appel and Haken, American Mathematical Society, Providence RI, 1989 May, Kenneth (1965) The Origin of the Four-Color Conjecture, Isis, 56:3:346-348 Saaty, Thomas (1967) Remarks on the Four Color Problem: the Kempe Catastrophe, Mathematics Magazine, 40:1:31-36

1/--страниц