Detailed history

Work in progress (15/Feb/2016)!

I’d like to create a timeline of all historical events concerning the theorem. I am using informations taked from various sources: the MacTutor History of Mathematics archive, the Wikipedia page for the Four color theorem and some books, as for example the “The Four-Color Theorem: History, Topological Foundations, and Idea of Proof” by Rudolf Fritsch and Gerda Fritsch and the “Four Colors Suffice: How the Map Problem Was Solved” by Robin Wilson e Ian Stewart.

Here is the timeline:

  • 1850 – Francis Guthrie obtained a Bachelor of Arts degree at the University College and it is known that at that time (1850) he was already a former student of Augustus De Morgan (England – London)
  • 1852 – Francis Guthrie took a Bachelor of Laws, that years later “forced” him to move to South Africa (England – London)

The 4ct begins here:

  • 1852 – Francis Guthrie told to his brother Frederick Guthrie about some results he had been trying to prove regarding the colouring of maps and asked Frederick to submit to his professor Augustus De Morgan this problem (England – London)
  • 23 October 1852 – Frederick Guthrie asked to his professor De Morgan if the problem that he showed to him was known. De Morgan, facinated by this problem, wrote the same day to William Rowan Hamilton in Dublin: “A student of mine asked me today to give him a reason for a fact which I did not know was a fact – and do not yet. …” (England – London)
  • 26 October 1852 – Hamilton replied after few days (showing the efficiency of both himself and the postal service): “I am not likely to attempt your quaternion of colour very soon” (Ireland – Dublin)
  • 09 December 1853 – De Morgan wrote to his friend and former teacher William Whewell in which he discussed the four color conjecture. TBContinued (The Four-Color Theorem: History, Topological Foundations, and Idea of Proof)
  • 24 June 1854 – De Morgan wrote to … TBContinued (The Four-Color Theorem: History, Topological Foundations, and Idea of Proof)
  • 1857 – Francis Guthrie some years after he took the Bachelor of Laws, was called to the bar and moved to South Africa, where he had a distinguished career becoming a professor of mathematics at the newly estabilished college in Cape Town. He also contributed in botany and two plants were named after him: the Guthriea Capensis and the heather Erica Guthriei (South Africa – Cape Town)
  • 1860 – De Morgan kept asking if anyone could find a solution to Guthrie’s problem and several mathematicians worked on it (England – London)
  • 04 November 1869 – The British interdisciplinary scientific journal Nature was first published this day (England)
  • 13 June 1878 – Arthur Cayley also learnt of the problem from De Morgan and he posed a question to the London Mathematical Society asking if the Four Colour Conjecture had been solved (England –  London)
  • 1878 – The American Journal of Mathematics (the oldest continuously published mathematical journal in the United States) was founded at the Johns Hopkins University by James Joseph Sylvester, an English-born mathematician (United States – Baltimore)
  • 1879 – Shortly afterwards Cayley sent a paper on the colouring of maps to the Royal Geographical Society that published it. This paper explains where the difficulties lie in attempting to prove the Conjecture (England  – London)
  • 1979 – Charles Peirce was appointed as lecturer in Logic in the Department of Mathematics at Johns Hopkins University and became, in that multidisciplinary conference, interested in the Four Colour Problem and also problems of knots and linkages studied by Kempe. He then attempted to prove the conjecture and retained a lifelong interest in the problem (United States)
  • 17 July 1879 – Alfred Bray Kempe announced in Nature (journal) that he had a proof of the Four Colour Conjecture (England – London)

Jet to review:

  • 1879 – At Cayley’s suggestion Kempe submitted the Theorem to the American Journal of Mathematics where it was published. William Story read the paper before publication and made some simplifications. Kempe received great acclaim for his proof
  • November 1879 – William Story reported the proof to the Scientific Association of Johns Hopkins University and Charles Peirce, who was at the November meeting, spoke at the December meeting of the Association of his own work on the Four Colour Conjecture
  • 1880 – Frederick Guthrie wrote a letter remembering it was his elder brother Francis that told him about the four color problem and asked to present the problem to De Morgan: “With my brother’s permission I submitted the theorem to Professor De Morgan, who expressed himself very pleased with it; accepted it as new; and, as I am informed by those who subsequently attended his classes, was in the habit of acknowledging whence he had got his information. If I remember rightly, the proof which my brother gave did not seem altogether satisfactory to himself; but I must refer to him those interested in the subject  . . .”. Personal note: So it was this year that the problem’s origin was attributed to Francis and not Frederick? And also that the nature of the proof that Francis wrote (surely wrong) was and it is not known
  • 1880 – Kempe published two improved versions of his proof, the second in 1880 aroused the interest of P. G. Tait, the Professor of Natural Philosophy at Edinburgh. Tait addressed the Royal Society of Edinburgh on the subject and published two papers on the (what we should now call) Four Colour Theorem. They contain some clever ideas and a number of basic errors
  • 1881 – Kempe was elected a Fellow of the Royal Society and served as its treasurer for many years
  • 1890 – Percy John Heawood, a lecturer at Durham England, published a paper called Map colouring theorem. In it he states that his aim is rather destructive than constructive, for it will be shown that there is a defect in the now apparently recognised proof. Did validate “5-color theorem”. Work by Birkhoff, Veblen, Whitney. The Four Colour Theorem returned to being the Four Colour Conjecture. Heawood was to work throughout his life on map colouring, work which spanned nearly 60 years. He successfully investigated the number of colours needed for maps on other surfaces and gave what is known as the Heawood estimate for the necessary number in terms of the Euler characteristic of the surface
  • 1896Charles Jean Étienne Gustave Nicolas Baron de la Vallée Poussin also pointed out the error in Kempe’s paper, apparently unaware of Heawood’s work
  • 1898 – Heawood made further contributions to the Four Colour Conjecture. In this year he proved that if the number of edges around each region is divisible by 3 then the regions are 4-colourable. He then wrote many papers generalising this result
  • 1904 – The search for unavoidable sets began in 1904 with work of Weinicke. An unavoidable set is a set of configurations such that every map that satisfies some necessary conditions for being a minimal non-4-colorable triangulation (such as having minimum degree 5) must have at least one configuration from this set
  • 1912 – Kempe was knighted and the same year he become the Chancellor for the Diocese of London. He received the honorary degree D.C.L. from the University of Durham
  • 1912 – Renewed interest in the USA was due to Veblen who published a paper on the Four Colour Conjecture generalising Heawood’s work. Further work by G. D. Birkhoff introduced the concept of reducibility on which most later work rested. A reducible configuration is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, then the map can be reduced to a smaller map. This smaller map has the condition that if it can be colored with four colors, then the original map can also. This implies that if the original map cannot be colored with four colors the smaller map can’t either and so the original map is not minimal
  • 1922 – Franklin in 1922 published further examples of unavoidable sets and used Birkhoff’s idea of reducibility to prove, among other results, that any map with ≤ 25 regions can be 4-coloured. The number of regions which resulted in a 4-colourable map was slowly increased. This wasn’t terribly edifying in itself, but Franklin’s method paved the way for the eventual solution by introducing the idea of a reducible configuration
  • 1926 – Reynolds increased it to 27 in 1926 (using unavoidable sets)
  • 1940 – Winn to 35 (using unavoidable sets)
  • 1950 – Heinrich Heesch, who had invented a clever method for proving that many configurations are reducible, said that he believed the four-colour theorem could be proved by finding an unavoidable set of reducible configurations. The only difficulty was to find one – and it wouldn’t be easy, because some rule-of-thumb calculations suggested that such a set would have to include about 10,000 configurations. With the computers then available, it would have taken about a century to deal with an unavoidable set of 10,000 configurations. Though modern computers can do the job in a few hours!
  • 1965 – The mathematical historian Kenneth May observed, in an artical on the problem’s origin, that “the four color conjecture cannot claim either origin or application in carthography”, since carthographers never tried to minimize the number the colors used to color maps
  • 1969 – Heesch in 1969 introduced the method of discharging. This consists of assigning to a vertex of degree i the charge 6 – i. Now from Euler’s formula we can deduce that the sum of the charges over all the vertices must be 12. A given set S of configurations can be proved unavoidable if for a triangulation T which does not contain a configuration in S we can redistribute the charges (without changing the total charge) so that no vertex ends up with a positive charge. Heesch thought that the Four Colour Conjecture could be solved by considering a set of around 8900 configurations. There were difficulties with his approach since some of his configurations had a boundary of up to 18 edges and could not be tested for reducibility. The tests for reducibility used Kempe chain arguments but some configurations had obstacles to prevent reduction
  • 1970 – Ore and Stemple to 39 in 1970 (using unavoidable sets)
  • 01 April 1975 – April fool’s joke. Martin Gardner published on Scientific American “Six sensetional discoveries that somehow or another have escaped public attention” with a counterexample of the four color theorem … “Last November, William McGregor, a graph theorist of Wappingers Falls, N.Y., constructed a map of 110 regions that cannot be colored with fewer than five colors”
  • July 1975 – April fool’s joke map solved. The Journal reported that they received more than a thousand letters and hundreds of drawings with proper coloring of the map
  • 1976 – Mayer to 95 (using unavoidable sets)
  • 1976 – Appel and Haken used a computer to check 1936 cases, giving the first and final proof! The proof was achieved by Appel and Haken, basing their methods on reducibility using Kempe chains. They carried through the ideas of Heesch and eventually they constructed an unavoidable set with around 1500 configurations. They managed to keep the boundary ring size down to ≤ 14 making computations easier that for the Heesch case. There was a long period where they essentially used trial and error together with unbelievable intuition to modify their unavoidable set and their discharging procedure. Appel and Haken used 1200 hours of computer time to work through the details of the final proof. Koch assisted Appel and Haken with the computer calculations.
  • 1977 – Details of the Appel and Haken proof appeared in two article
  • 1996 – A new simplified version of the proof is found. Robertson, Sanders, Seymour, Thomas used computer to check 633 cases
  • 2008George Gonthier and Benjamin Werner, proved four colour theorem using Coq. Unlike the programs used by Appel and Haken, Coq automatically generates a proof on the basis of the algorithm that has been selected. So we have is a proof of which 0.2% was done by a human being (that matters and must be gotten right) and other 99.8% by a machine (since Coq is certified to be bug free, we can be sure that rest is correct). The shortest known proof of the four colour theorem today still has over 600 cases and is a proof by exhaustion
  • Now – Short proof still wanted

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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