wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/only-computers-can-solve-this-map-coloring-problem-from-the-1800s-20230329\/#comments<\/a><\/br> One of the great episodes in the history of mathematics began on October 23, 1852. In a letter to Sir William Rowan Hamilton, Augustus De Morgan wrote, \u201cA student of mine asked me today to give him a reason for a fact which I did not know was a fact \u2014 and do not yet.\u201d To this day, that \u201cfact\u201d continues to enthrall and challenge scholars.<\/p>\n The student was Frederick Guthrie, and the \u201cfact\u201d in question originally came from his brother, Francis. After looking at a map of British counties, he wondered whether it was always possible to color a map using four or fewer colors, while ensuring that regions sharing a border (more than a corner point) are different colors.<\/span><\/p>\n It seemed as if this should always be possible. \u201cThe more I think of it the more evident it seems,\u201d De Morgan wrote. Still, the problem didn\u2019t excite Hamilton. He replied, \u201cI am not likely to attempt your \u2018quaternion<\/a> of colours\u2019 very soon.\u201d And De Morgan\u2019s efforts to get others interested failed as well.<\/p>\n The problem sat largely dormant until 1878, when Arthur Cayley asked members of the London Mathematical Society if anyone had found a proof. Soon after that, proofs started appearing. It was the first one, by the barrister Alfred Kempe in 1879, that turned out to be the most important. The proof was convincing, and it was accepted as correct for over a decade. Unfortunately, Kempe\u2019s proof \u2014 like all the others that would appear for the next century \u2014 was flawed. Yet it was ingenious, and it contained key ideas that would appear in the eventual proof.<\/p>\n To understand how Kempe and most mathematicians have looked at this problem, it helps to recognize that a map contains a lot of information irrelevant to the coloring problem, such as the shape, size and exact location of each region. All that matters is which regions share boundaries, although we do require all regions to be connected; Michigan, with its separate upper peninsula, doesn\u2019t actually prevent the U.S. map from being four-colorable, but it could, mathematically.<\/p>\n To focus on the information that matters, we can encode these relationships using a graph, also known as a network, where dots (vertices) are connected by lines (edges). Replace each region of the map with a vertex and connect the vertices of neighboring regions with an edge. If it helps, we can imagine that the vertices are the capital cities and the edges are roads joining them.<\/p>\n In this way, the map coloring problem becomes a graph coloring problem: Color the vertices so neighbors are different colors. The minimum number of colors is called the chromatic number of the graph. We can ask about the chromatic number of any graph, but graphs that come from maps have special properties. These graphs are simple, meaning there are no edges starting and ending at the same vertex (called loops), and two vertices can only be joined by one edge. The graph is also planar, meaning it can be drawn so no edges cross.<\/p>\n We can now restate Francis Guthrie\u2019s problem: Prove that the chromatic number of every simple planar graph is at most four.<\/p>\n Here\u2019s a sketch of Kempe\u2019s argument, described in modern terms using graphs rather than maps. He started by observing that a graph with one vertex \u2014 perhaps the map is a lone island \u2014 requires only one color. He then used a clever argument to build upward from there, arguing that it\u2019s possible to use at most four colors to color a graph with two vertices, then three vertices and so on. Here\u2019s how.<\/p>\n Suppose we can color all simple planar graphs with n <\/em>vertices with at most four colors \u2014 this is trivial for n<\/em> less than 5 \u2014<\/em> and we are then handed one with n <\/em>+ 1 vertices. How can we show that it, too, will be colorable with at most four colors?<\/p>\n First, Kempe showed, using a careful counting argument, that every simple planar graph has something in common: It must contain at least one vertex with at most five neighbors. Taking all the options into account, this means that every possible graph based on a map contains one of six special configurations of vertices.<\/span><\/p>\n If we remove this vertex, and all the edges that connect to it, we leave behind a graph with n<\/em> vertices \u2014 which we already know can be colored using four colors. We actually do so as the next step. Now, look at the vertices adjacent to the removed vertex. If they exhibit three or fewer colors, we can color the removed vertex one of the remaining colors, and we\u2019re done: We\u2019ve just shown that the graph with n<\/em> + 1 vertices can be colored with four colors. And if the adjacent vertices include all four colors, Kempe devised a clever method of recoloring certain vertices to free up a color for the removed vertex, again showing that the graph with n<\/em> + 1 vertices needs only four colors.<\/p>\n In 1890, the mathematician Percy Heawood identified Kempe\u2019s error. There was a special case in which Kempe\u2019s clever method failed. Heawood remarked that although his own work appeared \u201cdestructive [rather] than constructive,\u201d he showed that Kempe\u2019s technique could prove that every map can be colored with five or fewer colors \u2014 not quite the original goal, but still impressive.<\/p>\n Heawood also investigated maps drawn on more complicated surfaces. He proved that a map on a doughnut with g<\/em> holes may need as many as $latex frac{mathrm 1}{mathrm 2} left( 7+sqrt{ 1+48g} right) $ colors (where this value is rounded down to the nearest integer). So decorating an ordinary doughnut may require as many as seven colors of frosting. Yet, in what was becoming a pattern, his proof for general surfaces was incomplete, and we didn\u2019t have a full proof until 1968.<\/span><\/p>\n But even when Heawood\u2019s theorem for general surfaces was proved, the four-color problem remained unsolved. Thanks to decades of hard work, though, a proof was in sight.<\/p>\n At a conference in 1976, 124 years after Guthrie posed the problem, Wolfgang Haken announced a proof in collaboration with Kenneth Appel and with assistance from the graduate student John Koch. Reactions were mixed. \u201cI had expected the audience to erupt with a great ovation,\u201d wrote Don Albers<\/a>, who was present at the talk. \u201cInstead, they responded with polite applause!\u201d It was because rather than producing a pencil-and-paper argument, the team relied heavily on a computer.<\/p>\n They didn\u2019t have a machine directly answer the question, since infinitely many planar graphs are possible, and a computer cannot check them all. However, much as Kempe proved that every graph contains one of six special configurations of vertices, Appel and Haken showed that every graph must have one of 1,936 special configurations. Proving the theorem amounted to showing that we need only four colors to color any graph containing those subgraphs. Breaking down Kempe\u2019s six special cases into 1,936 sub-cases gave them more fine-grained control and made each case easier to check \u2014 though the total number was now far too large for a human to verify without assistance. In fact, completing the calculations required over 1,000 hours of computer time.<\/p>\n The mathematical community only grudgingly accepted the results, believing that a proof should be understandable and verifiable entirely by humans. While it was acceptable for computers to perform routine arithmetic, mathematicians were not prepared to cede logical reasoning to a computing device. This conservatism and reluctance to embrace time-saving advancements was not new. In the 17th century, there was similar outcry when some mathematicians used newfangled algebraic techniques to solve problems in geometry. Similar drama may play out again with the rise of machine learning<\/a>: Will mathematicians accept a theorem discovered and proved by an opaque algorithm?<\/p>\n The proof of the four-color problem was, of course, only the beginning of the computer revolution in mathematics. In 1998 Thomas Hales used a computer to prove the famous conjecture of Johannes Kepler\u2019s<\/a> that the most efficient way to stack spheres is the one routinely employed to stack oranges in a grocery store. And recently computers helped find \u201cGod\u2019s number\u201d \u2014 the maximum number of twists required to solve a Rubik\u2019s cube (20 face turns or 26 if half turns count as two.)<\/p>\n
\nThe Colorful Problem That Has Long Frustrated Mathematicians<\/br>
\n2023-03-30 21:58:02<\/br><\/p>\n