# four colour theorem

12 results back to index

pages: 236 words: 50,763

The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow

Kentucky is surrounded by Tennessee, Virginia, West Virginia, Ohio, Indiana, Illinois, and Missouri. Again, you need three colors to color Tennessee, Virginia, West Virginia, Ohio, Indiana, Illinois, and Missouri, and a fourth to color Kentucky. Figure 6-2. U.S. Map. Take any map where there is some state surrounded by a ring of an odd number of other states and that map needs four colors. Here is a map of the provinces of Armenia. Figure 6-3. Armenia. There are only two provinces that lie entirely within Armenia. Kotayk’ has six neighbors and the capital province of Yerevan has four neighbors. Every state that doesn’t border the ocean has an even number of neighbors. So the heuristic says we might be able to color this map with three colors, and we can. Figure 6-4. Armenia Colored.

Chapter 2 Nearly everything in this chapter, except the section on Occam’s razor, is a figment of my imagination meant to illustrate the unlikely world of P = NP. Chapter 3 On Milgram’s experiment, see Stanley Milgram, “The Small World Problem,” Psychology Today 2, no. 1 (1967): 60–67. The Bacon number calculation is from the Internet Movie Database. For a readable story of the four-color problem, see Robin Wilson, Four Colors Suffice: How the Map Problem Was Solved (Princeton, NJ: Princeton University Press, 2004). Chapter 4 The quotation from Cook is actually a paraphrase in modern terminology of the original quotation from his seminal paper. The original reads as follows: The theorems suggest that {tautologies} is a good candidate for an interesting set not in L*, and I feel it is worth spending considerable effort trying to prove this conjecture.

pages: 229 words: 67,599

The Logician and the Engineer: How George Boole and Claude Shannon Created the Information Age by Paul J. Nahin

He has described problems that would remain beyond the power of even a quantum computer to solve efficiently.16 One such problem is the following: given an arbitrary planar map, can it be colored with just three colors so that no two countries that share a common border have the same color? Since the 1976 computer-based proof that, in general, it requires four colors to color a planar map, we know that there are maps for which three colors would not be sufficient. But, nevertheless, there are particular maps for which three colors are enough. There is, alas, no efficient algorithm known that can distinguish between three-color and four-color maps, and so having a quantum computer available would be of no help. And even when a quantum algorithm is known, it may not result in a polynomial time computation. Grover’s search algorithm is such a case because, while is indeed faster than N, we know from our earlier discussion of the factoring problem that is still exponential and not polynomial. A quantum computer makes direct use of one of numerous available quantum mechanical phenomenan to manipulate information.

pages: 407 words: 116,726

Infinite Powers: How Calculus Reveals the Secrets of the Universe by Steven Strogatz

But I think a scenario like this is not out of the question. In parts of mathematics and science, we are already experiencing the dusk of insight. There are theorems that have been proved by computers, yet no human being can understand the proof. The theorems are correct but we have no insight into why. And at this point, the machines cannot explain themselves. Consider the famous long-standing math problem called the four-color map theorem. It says that under certain reasonable constraints, any map of contiguous countries can always be colored with just four colors such that no two neighboring countries are colored the same. (Look at a typical map of Europe or Africa or any other continent besides Australia and you’ll see what I mean.) The four-color theorem was proved in 1977 with the help of a computer, but no human being could check all the steps in the argument.

See formulas Eratosthenes, 42, 49 Erdős, Paul, 294 Euclid, 32, 90–91, 188, 236 Eudoxus, method of exhaustion used by, 32 exponential functions, 127–28 exponential growth and decay, 137–39, 220–24, 251 F facial surgery, 53–56, 56 falling bodies, 66–69 Faraday, Michael, x–xi FBI fingerprinting technology, 107–13, 257 feedback loop, 138 Ferguson, Samuel, 294 Fermat, Pierre de analytic geometry, 101–3 background, 100 contributions of, 93, 120–21, 194 Descartes rivalry, 98–99 FBI fingerprinting technology, 107–13 optimization, 103–7 principle of least time, 113–18, 319n118 tangents, 118–20 xy plane, 96–97 Feynman, Richard, vii, viii–ix, 295–97 Finding Nemo (movie), 50 fingerprints database, 107–13 finite decimals, 10 fluxions, 184 foci (focal points), 81–82 force, 230–31, 252, 258 formulas circle, area of, 7, 33 force and motion, 230–31, 252, 258 functions of one variable, 124 fundamental theorem, 179–80, 211 HIV decay, 221–22 Kepler’s third law, 85 parabolic segment, 38, 39 pi, bounds of, 32 power series (area of circular segment), 190, 191 sine waves, derivative of, 258 velocity, 173 forward problem, 144–46, 175, 179–80 four-color map theorem, 293 Fourier, Jean Baptiste Joseph applications of work, 256 Fourier analysis, 267 heat flow, 249–52 string theory, 252–56 Fourier analysis, 267 Fourier series, 254 fourth dimension, 287–91 frequencies, 254, 256, 259–60 friction, 69–70, 232–33, 245 Fuller, Brock, 275 functions applications of, 125–26 exponential functions, 127–28 exponential growth and decay, 137–39 linear functions, 146–49 logarithms, 131–34 natural base (e), 134–37 nonlinear equations, 149–54 power functions, 126–27, 182 scientific notation, 128–31 three central problems of, 144–46 xy plane, 124–25 See also derivatives fundamental theorem backward problem, 180–85 constant acceleration, 172–75 differentials, 209–11 discovery of, 168–69 equation for, 179–80, 211 Leibniz’s approach to, 211–18, 213 local vs global operations, 185–86 meaning of, 179–80 motion and change, 169–72 Newton on, 182, 193–94 “paint-roller” proof, 175–79, 178 future directions, 271–94 chaos, 281–82 computers, 285–87 determinism, 277–79 dimensions, four or more, 287–91 DNA, 273–76 nonlinearity, 279–80 Poincaré’s vector fields, 282–84 predictions, 273 radar, 284–85 G Galilei, Galileo, 64–76 background, 64 constant acceleration, 173 contributions of, 59–60, 86–88 Discourses and Mathematical Demonstrations Concerning Two New Sciences, 65 falling bodies, 66–69 functions of one variable, 124 house arrest, 65–66 ideal conditions, 69–71 vs Kepler, 85–86 observations with telescope, 65 pendulums, 71–77 power functions, 126–27 principle of inertia, 231 religious beliefs, 65 Two New Sciences, 68, 70, 71–72 Galilei, Virginia (Maria Celeste), 64, 65 Gamba, Marina, 64 Gauss, Carl Friedrich, 261 geometric series, 39 geometry algebra, merge with, 93–96, 98 analytic geometry, 101–3 area of a circle, 4–8 birthplace of, 90 harmony and, 49 Kepler on, 60, 79–80, 82 in Nature, 70 Plato on, 60 Geometry (Descartes), 119 Geri’s Game (movie), 51–52, 52 Germain, Sophie, 260, 261–62 Gilbert, William, 87 Glenn, John, 237–38 global operations.

pages: 295 words: 66,824

A Mathematician Plays the Stock Market by John Allen Paulos

Given the payoffs and human psychology, the most likely outcome is for both to confess; the best outcome for the pair as a pair is for both to remain silent; the best outcome for each prisoner as an individual is to confess and have one’s partner remain silent. The charm of the dilemma has nothing to do with any interest one might have in prisoners’ rights. (In fact, it has about as much relevance to criminal justice as the four-color-map theorem has to geography.) Rather, it provides the logical skeleton for many situations we face in everyday life. Whether we’re negotiators in business, spouses in a marriage, or nations in a dispute, our choices can often be phrased in terms of the prisoner’s dilemma. If both (all) parties pursue their own interests exclusively and do not cooperate, the outcome is worse for both (all) of them; yet in any given situation, any given party is better off not cooperating.

pages: 285 words: 83,682

The Lies That Bind: Rethinking Identity by Kwame Anthony Appiah

That would be tempting, but the economic dimension here is anything but incidental or contingent, and not every form of status relates to class status. (The elite members of a football team have an advantage in honor, as well as in earnings, over its benchwarmers, but class isn’t the right way to describe the arrangement.) Heritability is part of the picture; so is the prospect of upward or downward mobility. The connection between class and wealth, though complex, is indissoluble. You can start to see why class became the four-color-map problem of the social sciences. The more variables we try to account for, the harder it is to solve. Indeed, given the uncertainties about precisely how class identities might be defined or demarcated, a number of sociologists have, over the decades, sought to banish the term—to abolish “class,” if not class. But, like Svevo’s character Zeno, who is constantly trying, and failing, to give up smoking, we haven’t quite bridged the vow to the deed.

pages: 245 words: 12,162

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook

We can thus color these inner regions with two colors, switching every time we cross one of the non-circuit edges. The same trick allows us to two-color the regions lying outside of the Hamiltonian circuit, yielding altogether a four-coloring of the map. In the example, the inner regions are colored dark yellow and light yellow, and the outer regions are colored dark blue and light blue. Tait knew that not all maps have Hamiltonian circuits through their borders (the map of the continental United States is a ready example), but available tricks allowed the four-color problem to be restricted to maps such that each vertex of the border graph meets exactly three edges. Furthermore, the border graph could be assumed to be three-connected, that is, it is impossible to break the graph into two parts by deleting one or Origins of the Problem two vertices.

pages: 913 words: 265,787

How the Mind Works by Steven Pinker

Something must have kept Spock from spending his days calculating pi to a quadrillion digits or memorizing the Manhattan telephone directory. Something must have impelled him to explore strange new worlds, to seek out new civilizations, and to boldly go where no man had gone before. Presumably it was intellectual curiosity, a drive to set and solve problems, and solidarity with allies—emotions all. And what would Spock have done when faced with a predator or an invading Klingon? Do a headstand? Prove the four-color map theorem? Presumably a part of his brain quickly mobilized his faculties to scope out how to flee and to take steps to avoid the vulnerable predicament in the future. That is, he had fear. Spock may not have been impulsive or demonstrative, but he must have had drives that impelled him to deploy his intellect in pursuit of certain goals rather than others. A conventional computer program is a list of instructions that the machine executes until it reaches STOP.

pages: 1,509 words: 416,377

Under the Loving Care of the Fatherly Leader: North Korea and the Kim Dynasty by Bradley K. Martin

Trying to lure investors there—regardless of how the multinational negotiations might turn out—clearly was a big part of what the government had in mind when it admitted our group of visitors. Rajin and Sonbong port officials planned to expand cargo capacity from six million to 50 million tons a year in two stages—and also planned to build a brand new port in the area with annual capacity of another 50 million tons. Unlike some nearby Russian ports, they boasted, the North Korean ports didn’t freeze up in winter. A slick brochure complete with four-color maps projected that the population of 131,000 North Koreans living in the vicinity of the two ports would grow into a modern industrial city of a million people. Conceivably a purely North Korean economic zone could work, if South Korean, Japanese or other foreign interests invested in factories there. But Yasuhiro Kawashima, deputy director-general of the Bureau of Port and Airport Development of Japan’s Niigata Prefecture, cautioned that proposals to expand port facilities in Rajin, Sonbong and nearby Chongjin might go nowhere unless Pyongyang persuaded neighbors to trans-ship cargoes through the North Korean ports.

Prime Obsession:: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics by John Derbyshire

pages: 158 words: 49,168

Infinite Ascent: A Short History of Mathematics by David Berlinski

pages: 323 words: 94,156

Chasing New Horizons: Inside the Epic First Mission to Pluto by Alan Stern, David Grinspoon

Closely married with Alice, is the “Ralph” instrument. Its name came from a silly joke referring to the old Honeymooners’ TV show characters, Ralph and Alice Kramden. Whereas Alice’s objective was primarily to study Pluto’s atmosphere, Ralph’s objective was to map and also determine the composition of Pluto’s surface. The size of a hat box, Ralph contains two black-and-white cameras, four color filter cameras, and an “infrared mapping spectrometer” to map surface compositions. Ralph can see colors that are redder than any red humans can see, at wavelengths which are called infrared, where minerals and ices have characteristic spectral features that can be used to reveal the surface materials at any given location in Ralph’s field of view. Ralph’s spectrometer splits infrared light up into 512 spectral channels from 1.25 to 2.5 microns.

pages: 326 words: 91,559

Everything for Everyone: The Radical Tradition That Is Shaping the Next Economy by Nathan Schneider