Shulou(Shulou.com)11/24 Report--

This article comes from the official account of Wechat: ID:fanpu2019, author: Hanying

You must have heard of the four-color theorem, an interesting problem that originated from coloring countries on maps. It is known as one of the three major mathematical problems in the world in modern times. It took mathematicians more than 100 years to give real proof, and the computer proof used also appeared on the mathematical stage. Nowadays, in the field of graph theory, there are many interesting problems derived from the four-color theorem. For example, a question that originated from a radio station: fill in a number on an infinite grid paper, and the "distance" between the same number must be greater than the number itself, so at least how many numbers are needed to cover the entire plane?

Write an article | in English

When you are young, will you be in a daze at the world map on the wall of your study? Staring at the colorful patterns, I imagined that I would be able to travel around the world one day. In Britain in the 19th century, an ancient and classic mathematical problem-coloring problem, was born out of such a gaze.

Figure 1: map of the World? map Source: the story of the origin of the four-color problem in the Department of Natural Resources's standard map service system began in 1852 when British cartographer Francis Francis Guthrie asked the question of "coloring the map" while looking at the map. He found that only four colors were needed to color the map, making the colors of neighboring countries different. But what puzzles him is whether this number "4" is the best. So he asked his brother Frederick Frederick Guthrie and his friends for help. In the course of communication, they gradually realized that this problem is deeply related to mathematics. So Frederick asked his teacher, Augustus de Morgan (Augustus De Morgan), a mathematician at University College London, for help. Professor de Morgan was powerless after trying, so he wrote to refer the question to his good friend, Irish mathematician Professor William William Hamilton. Unfortunately, the wise Hamilton did not have much interest in this issue.

"Today, a student asked me to explain a fact that we don't know if it can be used as a fact," Morgan wrote in a letter. He said that a figure on a plane is randomly divided into limited parts and stained so that the adjacent parts have different colors and can only be used in four colors. What do you think? if this question is true, can it attract people's attention? "

At first, this "sounds easy to understand" problem did not attract the widespread attention of mathematicians. It was not until 1878 that the British mathematician Arthur Gloria (Arthur Cayley) officially announced and named this problem as the "four-color problem" at the mathematics conference in London, which aroused everyone's desire to solve it. At that time, mathematicians generally believed that the four-color problem would not be too difficult and should be solved soon. However, things went against one's wishes. From "four-color conjecture" to "four-color theorem", it has gone through a long period of more than 120 years, and even once synonymous with "Fermat Great Theorem" and "Goldbach conjecture" as the world's three most famous mathematical problems.

Figure 2: mathematician Gloria source: a century-old proof of Smithsonian Institution Librarie's four-color theorem there is a lot of invalid information in the popular narrative of the four-color problem, such as the shape, area, longitude and latitude of each country, and so on. The only important information is that it is adjacent (that is, two regions share the same boundary). Ignoring this invalid information, let's look at how to strictly define this problem in abstract graph theory (Graph Theory) language.

Given a graph (graph) G = (V, E), where the non-empty set V is the vertex set and E is the edge set. In fact, the concept of dual graph is used here, that is, a vertex v ∈ V is used to represent a country on the map, and an edge E12 = (v 1, v 2) ∈ E is used to indicate that two vertices (countries) v 1, v 2 are adjacent. Now we only consider a simple undirected graph-the edge of the graph is undirected, that is, e12distinct e21; there is no repeated edge, that is, there is at most one edge connecting vertices v 1, v 2; there is no self-ring, that is, there is no edge connected to only one vertex.

So the four-color problem is abstracted into a conjecture: coloring the vertices of a simple undirected graph G = (V, E) so that the colors of the adjacent points are different, then at least four colors are needed. The minimum number of colors required here is called chromatic number (chromatic number).

At first, people can only calculate by hand, for a map of 96 countries, the four-color conjecture holds. The turning point of the story took place in 1879, when an English lawyer, Alfred Kempe, provided an important idea for the proof of the four-color conjecture. Kemp proposed that at least one vertex in any simple undirected graph G = (V, E) has 2, 3, 4 or 5 adjacent vertices (a country has at least 2, 3, 4 or 5 neighboring countries). This proposition is actually an application of Euler's formula. Let G = (V, E) have v vertices, e edges and f faces. First of all, any face has at least three edges, two adjacent faces share an edge, and each edge has two vertices, so 2e=3f. If each vertex has at least six edges, then 2e ≥ 6 v. But the Euler formula tells us that v-e+f=2. This leads to a contradiction.

Kemp named the above vertices with up to five adjacent points and their corresponding edges as "inevitable configurations". Then he uses induction to remove this vertex and adjacent edges to get a subgraph G'. If the subgraph G 'satisfies the four-color conjecture, then the original graph G' is reducible, and the removed vertices and their edges are called "reducible configurations". Kemp believes that as long as it is proved that all the inevitable configurations are reducible (that is, the corresponding vertices and their edges can be removed), then the four-color conjecture is bound to be true. In mathematical language, assuming that a graph with n vertices satisfies a four-color conjecture, then for a graph with 1 vertices, there must be a vertex and its edges that are inevitable. If the adjacent points are trichromatic, then the removed points are painted with a fourth color, and the conclusion is naturally true; otherwise, it is necessary to recolor the original image and try to release the vertex so that its adjacent points can be tricolor. For this reason, Kemp designed the method of "Kemp chain".

However, 11 years after Kemp's results were published, a fatal and irreparable error was discovered. But Kemp's thinking still provides an important breakthrough for later generations, and people continue his method to prove that maps of 22 countries, 39 countries and 52 countries can be four colors. Until 1976, American mathematicians Kenneth Appel (Kenneth Appel) and Wolfg Harken (Wolfgang Haken) spent 1200 hours on two computers at the University of Illinois and finally completed the proof of the four-color theorem. They continued and improved Kemp's method, listing all 1936 inevitable configurations and verifying their reducibility in turn. This work has caused a sensation in the world, not only because they prove a mathematical problem, but more importantly, it tells people that computers can also be used in mathematical logic. On the day that the two mathematicians made the results of their research public, the local post office celebrated by stamping all the mail with a special postmark of "four colors enough".

Fig. 3 for many years after the publication of the four-color theorem proof, the Department of Mathematics at the University of Illinois at Urbana-Champaign has postmarked "four colors enough" on its emails. ? source: las.illinois.edu

Figure 4: mathematicians Harken (Wolfgang Haken,1928-2022) and Appel (Kenneth Appel,1938-2013). In fact, Appel and Harken were not the first to realize the need to solve the four-color conjecture with computer assistance. As early as 1950, the German mathematician Heinrich Heesch predicted that only with the help of powerful computing devices that can handle huge amounts of data can the limited but huge number of different configurations in the four-color conjecture be tested. In the era when computer technology has not yet boomed, Hirsch's ideas are very advanced. He was the first mathematician to advocate and try to use computers to overcome the four-color problem, and he generously communicated many of his ideas with Harken, which can be said to have played a great role in promoting the proof of the four-color conjecture.

Although the research results of Appel and Harken caused a sensation, they were not widely recognized at that time. People's doubts mainly stem from the disapproval of computer proof of mathematical problems. Skeptics believe that Appel and Harken's method is essentially an exhaustive test, they only use machines to test thousands of cases, and the details of their proof are hidden in the computer, which cannot be rechecked by manpower. The mathematical community calls for a purely clear mathematical proof. Thirty years later, George Gondier (Georges Gonthier), a young mathematician from the University of Cambridge in England, gave a complete computerized proof of the four-color theorem. Unlike Appel and Harken, every step of his logical proof is done independently by a computer. After years of computer revolution, people gradually recognize the help of computers for mathematical work, and are finally willing to admit that the four-color theorem is established!

Broadcast chromatic number problem: the generalization of the four-color problem mathematicians also thought about other related coloring problems in the process of studying the four-color conjecture. For example, the most famous Hadwiger-Nelson problem: coloring points on an infinite plane so that the colors of the adjacent points are different. What we are introducing today is another variant of the four-color problem: the Packing coloring (Packing coloring) problem, also known as the broadcast coloring (Broadcast coloring) problem. This question was first raised by Wayne Goddard, a professor at Clemson University University, and it actually stems from a very practical problem-the frequency allocation of radio stations.

Figure 5: radio, source: the coverage area of the signal sent by each radio station in the network is limited, and the stronger the signal, the wider the coverage. The frequency modulation (FM) band of radio is very narrow, and the frequency modulation range of civil radio in China is FM87.5-108MHz. It is obviously impractical if the radio stations of every province and city in our country send out signals of different frequencies. On the other hand, only when the two stations of the same frequency are far enough apart, their signals will not interfere with each other. For example, the FM frequencies of Tianjin crosstalk Radio, Shenyang Metropolitan Radio and Taizhou Traffic Music Radio are all 92.1MHz, while Beijing, which is adjacent to Tianjin, does not assign the signal band of 92.1MHz in its radio frequency table in order to avoid superimposed interference of the same signal.

So how to allocate the frequencies of radio stations in different regions so that we can cover the national broadcasting system with the shortest signal band range on the premise of avoiding interference? How do mathematicians define this in mathematical language?

Similar to the four-color theorem, given a simple undirected graph G = (V, E), we use a set of integers K = {1, … , k} to represent the color set, d (u, v) is used to define the distance between two vertices u, v. Consider mapping FRV → {1, … , k}, which satisfies that for any two vertices u, v ∈ V, and any integer c ∈ K, if f (u) = f (v) = c (that is, the color of vertices u and v are the same), then the distance between u and v is d (u, v) > c (that is, the distance between the two vertices of the same color is far enough; considering the actual background above, this means that the distance between the radio stations with the same signal frequency is far enough). Such a mapping f constitutes a packing k-coloring scheme, and the smallest integer that satisfies the packing coloring scheme is called the packing chromatic number (packing coloring number) χ ρ (G) of the graph.

The packing coloring problem is actually a stronger restriction on the map coloring problem. When K = {1}, the packing 1-coloring problem is the most primitive map coloring problem, that is, two adjacent vertices are required to have different colors. Let's first look at a simple example, consider the one-dimensional integer axis in the following figure, and take the graph Graph Z = {0, ±1, ±2,. } is a set of integers, each integer represents a vertex, two adjacent integers are marked as two adjacent vertices, and the distance between the two integers is defined as the absolute value of their difference. The construction mapping is as follows:

So d (- 2,2) = 4 > 3f (- 2) = f (2). Then at this point, χ ρ (Z) = 3.

Figure 6: one-dimensional Packing 3-coloring graph source: reference [8] the example above only considers the one-dimensional case. What if we consider the coloring problem of two-dimensional integer set Z2? As you can imagine, for an infinite plane, we can divide the plane into grids (just like an infinite chessboard) and define the distance between the two grids as the horizontal distance plus the vertical distance between them, so how to dye them with packing?

In 2008, Goddard and his four collaborators first made public their thinking on this problem. They calculated entirely by manpower and obtained 9 ≤ χ ρ (Z2) ≤ 23. Since then, several mathematicians have used computer-aided proof to gradually optimize the results to 13 ≤ ρ (Z2) ≤ 15.

In 2022, Bernardo Subercaseaux, a graduate student from Carnegie Mellon University, and Professor Marijn J. H. Heule further optimized this result to 14 ≤ χ ρ (Z2) ≤ 15. In January 2023, they announced that they had completely solved the packing coloring problem of the planar integer set Z2. In their paper, they proved that χ ρ (Z2) = 15, that is, only 15 numbers from 1 to 15 can fill the entire planar grid and ensure that the distance between two grids with the same number is greater than this number. Next, let's briefly introduce their ideas and methods.

Obviously, it is neither realistic nor necessary to use the exhaustive method for an infinite grid. Therefore, mathematicians want to verify a small part of it, such as taking a grid of 10 × 10, and then copying and splicing it. If it can still meet the requirements for distance, it can be proved. Suwekasius and Heller first simplified the graph from this point of view, but instead of considering a simple rectangle, they started from a finite subgraph Dr (v) = {u ∈ Z2 ≤ r}, which is similar to a diamond, using Dr, k to denote the k-packing coloring of the subgraph Dr [(0,0)]. Dr, k, c denote that the subgraph Dr [(0,0)] is k-packing-colored and the center point (0,0) is colored c. If k-packing coloring can be performed on a subgraph Dr (v), then there must be χ ρ (Z2) ≥ k; on the contrary, χ ρ (Z2) ≥ knot 1. It is not difficult to imagine that in a finite graph such as Dr (v), the smaller the number, the more times it appears; so in the dyeing process, priority can be given to the location of larger numbers. For example, when r ≤ k, the number r in the subgraph Dr, k, r will appear only once at the center point (0,0), otherwise it will destroy our requirement for distance. This is also the advantage of Dr (v) over rectangular subgraphs. Dr (v) is actually a regular quadrilateral with good symmetry, so Suvikasius and Heller divide Dr (v) into eight equal parts (see figure 7), and arrange the larger numbers in turn in the 1ram octagonal field when dyeing, thus avoiding repeated verification of the dyeing scheme. Figure 8 D3, 7, 3 is a very intuitive example.

Figure 7: eight equal parts of Dr (v)? map source: reference [8]

Figure 8:D3, 7, 3 staining? source: reference [8] the second simplification made by Suwekasius and Heller is that it is no longer simply taking the lattice as a staining unit. They select five adjacent lattice points in Dr (v) to form a plus-sign region, which is dyed as a unit. In other words, you can only consider filling a number into the plus area, but do not consider which grid point to put in the plus area for the time being. After arranging the dyeing scheme of the plus area, each lattice point is stained.

Figure 9: plus area? map Source: references [8] as peer evaluation: Suwekasius and Heller are not just solving problems, they are optimizing combinatorial research ideas. In the unremitting efforts, lasted four months, they finally conquered the plane packing staining problem.

The ending four-color theorem has perplexed the field of mathematics for more than a century, and up to now there is no real pure mathematical proof. However, the significance of the four-color problem has far exceeded the problem itself. what is more important is the thinking of other disciplines derived from generations of mathematicians in the process of thinking one after another, such as graph theory, topology, computer science and so on. People are willing to study the four-color problem, not to really fill the map with four colors, but to explore the topological properties and mathematical connotations of the number "4".

As the first mathematical theorem to be proved by computer, the four-color reason was initially questioned to widely accepted, which is doomed to its extraordinary position in the history of mathematics. Today, with the rapid development of artificial intelligence, AI-aided mathematical proof has become the focus of most scholars. Although some people still think that the formal proof of AI will destroy the original beauty of mathematics, it is undeniable that advanced technical means have greatly simplified the work of mathematicians. Perhaps what we should question is not the computer itself, but the attitude and method of scholars in using computers.

In the original Geometry, Euclid defined the mathematics of 300 BC in a near-perfect language and presented a set of intuitive and rigorous systems to later generations. When the time comes to the 21st century, people use precise symbols and mechanical rules to translate mathematics into computer code, which is not an inheritance and iteration of mathematical culture?

reference

[1] Xu Junming. Graph theory and its application. Edition 3 [M]. Hefei: University of Science and Technology of China Press. 2010.

[2] Fritsch R. The Four-Color Theorem [J]. American Mathematical Monthly, 1997 (8): 785.

[3] Gonthier G. Formal Proof-The Four- Color Theorem [J]. American Mathematical Society Notices, 2009 (1).

[4] Wang Xianfen, Hu Zuoxuan. Three generations of proof of the four-color theorem. Dialectics of Nature Newsletter. No. 4, 2010, 42-48, 127, a total of 7 pages

[5] Goddard, W., Hedetniemi, S., Hedetniemi, S., Harris, J., Rall, D.: Broadcast chromatic numbers of graphs. Ars Comb. 86 (01 2008)

[6] Bre sar, B., Ferme, J., Klav zar, S., Rall, D.F.: A survey on packing colorings. Discussiones Mathematicae Graph Theory 40 (4), 923 (2020)

[7] Subercaseaux, B., Heule, M.J.H.: The Packing Chromatic Number of the Infinite Square Grid Is at Least 14. In: Meel, K.S., Strichman, O. (eds.) 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 236, pp. 21:1-21:16. Schloss Dagstuhl-Leibniz-Zentrum fur Infor-: matik, Dagstuhl, Germany (2022)

[8] Subercaseaux, B., Heule, M.J.H The Packing Chromatic Number of the Infinite Square Grid is 15. ArXiv:2301.09757

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.