Clever Geek Handbook
📜 ⬆️ ⬇️

The problem of four colors

The problem of four colors
Map of the subjects of the Russian Federation , painted in four colors

The four-color theorem is a theorem that states that any map located on a sphere can be colored with no more than four different colors (colors) so that any two regions with a common part of the border are colored in different colors. At the same time, regions can be both simply connected and multiply connected (“holes” can be present in them), and a common part of the border is a part of a line, that is, the joints of several areas at one point are not considered a common border for them. The task of coloring a map on a plane is equivalent to a problem on a sphere.

In 1852, , drawing up a map of the counties of England, noticed that four colors were enough for such a purpose, His brother, Frederick, reported this observation to the well-known mathematician O. De. Morgan, and that - the mathematical community. The exact formulation of the hypothesis was published by A. Cayley (1878) [1] . It was not possible to prove the theorem for a long time. During this time, many attempts were made both to proof and refutation, and this task was called the problem of four colors [2] .

For simple cards, three colors are enough, and the fourth color begins to be required, for example, when there is one area surrounded by an odd number of others that are in contact with each other, forming a cycle. The five-color theorem, which asserts that five colors are sufficient, had a short simple proof and was proved at the end of the 19th century, but the proof of the theorem for the case of four colors was faced with considerable difficulties.

The four-color theorem was proved in 1976 by Kenneth Appel And Wolfgang Hacken From the University of Illinois . It was the first major mathematical theorem, proved by computer. The first step of the proof was the demonstration that there is a certain set of 1936 maps, none of which can contain a smaller map that would disprove the theorem. The authors used a special computer program to prove this property for each of the 1936 maps. The proof of this fact took hundreds of pages. After that, Appel and Haken came to the conclusion that the smallest counterexample to the theorem does not exist, because otherwise it would have to contain any of these 1936 cards, which is not. This contradiction suggests that there is no counterexample at all.

Initially, the proof was not accepted by all mathematicians, since it cannot be verified manually. Later it gained wider recognition, although some had doubts for a long time. To dispel the remaining doubts, in 1997, Robertson, Sanders, Seymour, and Thomas published simpler proof using similar ideas, but still done with a computer. In addition, in 2005, evidence was carried out by Georges Gontir using specialized software ( Coq v7.3.1) [3] .

Content

Equivalent wording

In graph theory, the statement of the four-color theorem has the following formulations:

  • The chromatic number of a planar graph does not exceed 4 [4] .
  • The edges of an arbitrary triangulation of a sphere can be colored in three colors so that all sides of each triangle are colored in different colors. [five]
  • Many more equivalent formulations are known [4] .

Historical Attempts of Evidence

The most famous evidence attempts:

  • Alfred Campé proposed evidence in 1879 [6] , it was refuted in 1890, but based on his ideas, it was possible to prove that any card can be painted in 5 colors [2] .
  • Peter Tet offered other evidence in 1880, [2] [7] and was refuted in 1891.
  • Maliev M. The Problem of Four Colors , 1914

Variations and generalizations

Similar problems for other surfaces ( torus , Klein bottle , etc.) were much simpler. For all closed surfaces, except for the sphere (and equivalent to the plane and cylinder) and the Klein bottle , the required number of colors can be calculated using the Eulerian characteristicχ {\ displaystyle \ chi}   according to the formula proposed in 1890 by [8] and the group of mathematicians finally proved during 1952-1968 with the greatest contribution of Gerhard Ringel and [9] [10] [11]

p=⌊7+49-24χ2⌋.{\ displaystyle p = \ left \ lfloor {\ frac {7 + {\ sqrt {49-24 \ chi}}} {2}} \ right \ rfloor.}  

For a Klein bottle, the number is 6 (and not 7, as according to the formula) - this was shown by P. Franklin in 1934, [12] and for the sphere - 4.

For one-sided surfaces of the genusg {\ displaystyle g}   [ten]

p=⌊7+one+48g2⌋,{\ displaystyle p = \ left \ lfloor {\ frac {7 + {\ sqrt {1 + 48g}}} {2}} \ right \ rfloor,}  

In the higher dimensions, a reasonable generalization of the problem does not exist, since it is easy to come up with a three-dimensional map with an arbitrary number of areas that all touch each other.

Four Color Game

Stephen Barr proposed a two-player puzzle game called Four Colors. According to Martin Gardner , “I don’t know a better way to understand the difficulties that are encountered in solving the problem of four colors than just playing this curious game” [13] .

Four colored pencils are needed for this game. The first player starts the game by drawing an arbitrary empty area. The second player paints it in any of the four colors and in turn draws his empty area. The first player paints over the area of ​​the second player and adds a new area, and so on - each player paints the opponent's area and adds his own. In this area, having a common border, should be painted in different colors. The one who is forced to take the fifth paint at his own turn loses.

It is worth noting that in this game the loss of one of the players is not at all proof of the infidelity of the theorem (four colors were not enough!). But only an illustration of the fact that the conditions of the game and the theorems are quite different. To verify the correctness of the theorem for the map obtained in the game, you need to check the connectivity of the drawn areas and, removing colors from it, find out if you can do with only four colors to paint the resulting map (the theorem states that you can).

There are also the following variations of the game:

  1. The map is pre-divided randomly into areas of different size, and each turn of the game changes the player who paints the area, and also the color changes (in strict sequence). Thus, each player paints over the map with only two colors, and in case he cannot paint over so that areas with a common border are painted in different colors, skips the turn. The game stops when no player can make a single move anymore. The winner is the one who has the total area of ​​the filled areas more.
  2. The square is divided into several squares (mostly 4x4), and its sides are painted in one of four colors (each in a different color). The first move fills the square adjacent to the side, each subsequent move can paint the square that is adjacent to one of the filled squares. It is impossible to paint over a square with those colors with which one of the adjacent squares (including diagonally) or the side adjacent to the square is painted over. The player who makes the last move wins.

In culture

  • “The Island of Five Colors” is a fantastic tale by Martin Gardner [14] .

See also

  • Evidence Calculations
  • The task of Nelson - Erdös - Hadwiger

Notes

  1. ↑ Samokhin A.V. The problem of four colors: unfinished history of evidence // Sorovskiy educational journal. - 2000. - V. 6 , № 7 .
  2. ↑ 1 2 3 JJ O'Connor, EF Robertson. The four color theorem (Neopr.) . MacTutor History of Mathematics archive . School of Mathematics and Statistics, University of St Andrews, Scotland (September 1996).
  3. ↑ Georges Gonthier. A computer-checked proof of the Four Color Theorem (Neopr.) .
  4. ↑ 1 2 Shor N. Z. , Donets G. A. On the four-color problem // Math Today / ed. prof. A. Ya. Dorogovtseva - Kiev, Vishcha school, 1982. - Circulation: 3000 copies. - c. 33-53
  5. ↑ Lakeev A.V. Elements of the theory of ordinary graphs. - Irkutsk: Publishing House of ISU, 2014. - p. 7. - 92 p.
  6. ↑ AB Kempe. Amer. J. Math. . - 1879. - V. 2 . - p . 193-200 .
  7. ↑ PG Tait. Note on a theorem in geometry of position // Trans. Roy. Soc. Edinburgh . - 1880. - T. 29 . - p . 657-660 .
  8. ↑ Percy John Heawood. Map-Color Theorem // Quarterly Journal of Mathematics, Oxford. - 1890. - T. 24 . - pp . 332–338 .
  9. ↑ G. Ringel and JWT Youngs. Solution of the Heawood Map-Coloring Problem // Proc. Nat. Acad. Sci. USA. - 1968. - V. 60 , no. 2 - p . 438-445 . - DOI : 10.1073 / pnas.60.2.438 . - PMID 16591648 .
  10. ↑ 1 2 Ringel G. A map coloring theorem / Translated from English by V. B. Alekseev. - M .: Mir, 1977. - 256 p.
  11. ↑ Boltyansky, 1982 , p. 77.
  12. ↑ P. Franklin. A Six Color Problem // J. Math. Phys. - 1934. - T. 13 . - p . 363-369 .
  13. ↑ Martin Gardner. The problem of four colors // Mathematical puzzles and entertainment = Mathematical puzzles and diversions. - 2nd ed. - M .: "The World" , 1999. - p. 389-390. - 447 s. - ISBN 5-03-003340-8 .
  14. ↑ Martin Gardner. The Island Of Five Colors . - NY: Fantasia Mathematica, 1958.

Literature

Ian Stewart. "The Greatest Math Problems"

  • A.A. Zykov. Fundamentals of graph theory. - M .: University book, 2000. - p. 367-386.
  • R. Courant, G. Robbins What is mathematics?
  • Samokhin A.V. The problem of four colors: the unfinished history of evidence // Coolant . - 2000. - № 7 . - p . 91-96 . (Checked November 7, 2018)
  • Rodionov V.V. Methods of four-color coloring of vertices of flat graphs. - M .: ComBook, 2000. - 48 p. - 2005 copies - ISBN 5-484-00127-7 .
  • Thomas, Robin The Four Color Theorem
  • Ringel G. A theorem on map coloring / Translated from English by V. B. Alekseeva. - M .: Mir, 1977. - 256 p. - a book with problem proof for all surfaces except the plane and the sphere
  • Boltyansky V. G. , Efremovich V. A. Visual topology. - M .: Science, 1982. - 160 p. - ( Library "Quant" ).
  • Donets G. A., Shor N. Z. On an algebraic approach to the problem of coloring flat graphs. - Kiev: Naukova Dumka, 1982. - 144 p.
  • Harari F. Graph Theory. - M., Mir, 1973. - 304 p.
Source - https://ru.wikipedia.org/w/index.php?title=Check_color_ problem&oldid = 101403798


More articles:

  • Loop Ash
  • Nuclear Magnetic Resonance
  • Gaftra
  • Kaufman, Mikhail Konstantinovich
  • Chalet "Wolf"
  • Le, Francis
  • Brandt, Rudolf
  • Kanote
  • Capture Maracaibo
  • Gunibskaya HPP

All articles

Clever Geek | 2019