Four color theorem

From Wikipedia, the free encyclopedia

Example of a four-colored map

A four-coloring of an actual map of the states of the United States (ignoring water and other countries).

 

1. First, scan the text quickly and try to match the headings and paragraphs.

 

1.      Attitude of mapmakers

2.      Which number of colors is enough?

3.      Second proof using computers

4.      Theorem proven, doubts remain

5.      What is it about?

A. In mathematics, the four color theorem, or the four color map theorem, states that given any separation of a plane into contiguous regions, called a map, the regions can be colored using at most four colors so that no two adjacent regions have the same color. Two regions are called adjacent only if they share a border segment, not just a point.

B. Three colors are adequate for simpler maps, but an additional fourth color is required for some maps, such as a map in which one region is surrounded by an odd number of other regions that touch each other in a cycle. The five color theorem, which has a short elementary proof, states that five colors suffice to color a map and was proven in the late 19th century,  however, proving four colors suffice turned out to be significantly harder. A number of false proofs and false counterexamples have appeared since the first statement of the four color theorem in 1852.

C. Despite the motivation from coloring political maps of countries, the theorem is not of particular interest to mapmakers. According to an article by the math historian Kenneth May (Wilson 2002, 2), “Maps utilizing only four colours are rare, and those that do usually require only three. Books on cartography and the history of mapmaking do not mention the four-color property.”

D. The four color theorem was proven in 1976 by Kenneth Appel and Wolfgang Haken. It was the first major theorem to be proven using a computer. Appel and Haken's approach started by showing there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem. Appel and Haken used a special-purpose computer program to check each of these maps had this property. Additionally, any map (regardless of whether it is a counterexample or not) must have a portion that looks like one of these 1,936 maps. To show this required hundreds of pages of hand analysis. Appel and Haken concluded that no smallest counterexamples existed because any must contain, yet not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and the theorem is true. Initially, their proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand.

E. To dispel remaining doubt about the Appel–Haken proof, a simpler proof using the same ideas and still relying on computers was published in 1997 by Robertson, Sanders, Seymour, and Thomas. Additionally in 2005, the theorem was proven by Georges Gonthier with general purpose theorem proving software.

2. Go back to the text and read it carefully. State what these numbers refer to.

a)      5

b)      1976

c)      1,936

d)      1852

e)      2005

f)        1997

 

3. Now answer Qs, using the information from the text.

1.      What are adjacent regions?

2.      What kinds of maps need four colors?

3.      When was the five color theorem proven?

4.      Is the four color theorem used by mapmakers?

5.      How was the four color theorem proven?

6.      Why was the proof unacceptable?

7.      Which methods of proving the theorem were used in 2005?

 

LANGUAGE STUDY:  a)There are some expressions, mainly verbs, in the text indicating the opinion and attitude of various scholars. Try to find them. 

………………………………..      ………………………………………….

……………………………….       …………………………………………

b) Which words from the text are synonyms to these expressions?

     inappropriate …………………..   impossible …………………….

 

     at first ………………………..      adjacent ……………………….

 

     to be enough …………………      put to rest …………………….      

Colors on maps

http://www.youtube.com/watch?v=68Njs99jTBk

Pre-listening

1) What can colors on maps show? Make a list.

    ………………………………………………..

    ……………………………………………….

    ……………………………………………….

    ………………………………………………..

    ………………………………………………..

Listen and compare, supplement your list.

2) What are adjacent regions? ……………………………………………………………

3) How many colors do you need for a political map of the world? …………………….

4) There are some sentences with missing words. Try to fill in the missing words, then listen again and check your answers.

 a) Colors show different ………., or in Canada, different …..or …….

b) States are colored to show ……………..

c) No states with the same color …… each other.

d) Rivers and lakes are ………….

e) On…….or physical map, colors show ………….

f) Green is for the areas with the ……..

g) The darkest shade of ……. indicates the highest elevation.

h) Various shades between the …….. and dark brown show the increased altitude above ………..

i) Colors also indicate climate and …...

j) ………….. is a natural vegetation in Central Europe.

k) ………….is very cold and dry.

l) Higher population density is shown by …………….

m) Parts of the world with most people: Japan, China, ….., Central Europe and the North ………… of the USA.

Exercise. Fill in a definite, indefinite or zero article.  KEY

 

 

1)      Theorem 7 has been extended to …a….class of boundary value problems.

2)      We call C …a… module of ellipticity.

3)      …the…. First Poisson integral in (4) converges to g.

4)      Thus A is the smallest possible extension in which …..differentiation is possible.

5)      By ……duality we easily obtain the following theorem.

6)      …a….more general theory must be sought to account for these irregularities.

7)      …….direct sums exist in the category of abelian groups.

8)      ……..section 4 gives a concise presentation of this problem.

9)      This idea comes from the game theory (homological algebra).

10)  It has ………..finite norm.

11)  The direct sum and ……direct product.

12)  It has …………cardinality c.

13)  a……remarkable feature of the solution should be stressed.

14)  In particular, …….closed sets are Borel sets.

15)  …….Borel measurable functions are often called Borel mappings.

16)  …the……existence of test functions is not evident.

17)  …the…..second statement follows immediately from the first.

18)  …the….real measures form a subclass of …the…..complex ones.

19)  …the…..Gauss theorem

20)  …the….two groups have been shown to have the same number of generators.

21)  The equation (3) has …a… unique solution g for every f.

22)  This map extends to all of M in …an….obvious fashion.

23)  The four centers lie in …a…plane.

24)  The right-hand side of (4) is then …a….bounded function.

25)  Let f and g be ……functions such that

26)  This is easily seen to be …an…equivalence relation.

27)  For this, we introduce ……an….auxiliary variable z.

28)  Then x is …the…centre of an open ball U.

29)  This reduces the solution to ………division by Px.

30)  …….property (iii) is called the triangle inequality.

31)  It has …….compact support.

32)  The equation of …….motion.

33)  The order and …….symbol of a distribution

34)  This has been proved in ……..part (a) of the proof.

35)  The hypothesis of …….positivity

36)  Here we do not require ……translation invariance.

37)  …a….chapter will be devoted to the study of …….expanding maps.

38)  The set of ……….points with distance 1 from K.

39)  We wish to find …a….solution of (6) which is of the form

40)  …the…..intersection of a decreasing family of such sets is convex.

41)  Using …the….standard inner product we may identify

42)  Each of …the..three products on the right of (4) satisfies

43)  …the…Dirichlet problem

44)  Let us now state …a…corollary of ……Lebesgue’ s theorem for

45)  After …a..change of variable in the integral we get