While mathematicians technically solved a nearly 175-year-old theorem known as the Four-Color Problem in 1976, the problem continues to vex researchers. For some in the field, their fascination with the perniciously complex concept runs so deep, that they liken their obsession to a lingering disease. But after a decade of analysis, an international team of mathematicians has made the first major breakthrough in the ongoing Four-Color Problem saga in 30 years. At this year’s Foundations of Computer Science (FOCS) conference, investigators laid out the optimal, most efficient algorithm that solves the Four-Color Problem.
What is the Four-Color Problem?
The underlying conceit to the Four-Color Problem is deceptively straightforward. In 1852, 19th century English mathematician Francis Guthrie posited that you only need a quartet of hues to fill every border-enclosed region on a map. Think all territories, regions, states, and nations filled in with only four colors. The first proof was introduced in 1879, and seemed solid for 11 years. That is, until Guthrie’s colleagues found an error in the calculations.
It took more than 85 years until a full proof arrived—a particularly notable moment, since it was also the first major theorem proven by a computer program. However, many in the mathematical community took issue with the digital discovery after having difficulty verifying it themselves.
A more accessible proof arrived in 1997, but even then, the algorithmic system became painfully slow as sample maps grew larger. A handful of mathematicians around the world have pondered new approaches to the problem ever since—including University of Copenhagen computer scientist Mikkel Thorup, who likens his interest to a “four-color disease.”
“I would guess that at least 1,000 mathematicians have caught the four-color disease, spending months trying to make it work but never quite succeeding,” Thorup said in a university profile. “It is the disease people have suffered from since 1852.”
Finding a cure for the four-color disease
It took years, but Thorup and his colleagues made progress after uncovering a novel detail regarding map-like surfaces known as planar graphs. The researchers realized these graphs feature many more reducible arrangements than experts previously assumed. This provided them a much more discreet set of starting points.
“Think of reducible configurations as handles you can grab hold on to start four-coloring,” added study co-author and Technical University of Denmark (DTU) mathematician Carsten Thomassen. “We show that graphs do not contain just one handle, but an astonishing number of them. Nobody knew that before.”
Instead of one or two handles in a graph, the team could now identify many more handles throughout any given map. This allowed them to simultaneously begin filling regions with four colors, which exponentially quickened the overall process. Thomassen said this boosted their algorithm from quadratic time (where calculation speed increases proportionally to the square of an input size) to linear time.
“This means that if a map contains ten times as many regions, the computation only becomes about ten times slower. With the previous algorithm, it would have become about 100 times slower,” he added.
Cheesy implications
But does this really change anything beyond theoretical mathematics? According to researchers, the answer is a resounding “yes.”
“The remarkable thing is that because there are so many handles, the idea can also be applied to other kinds of surfaces besides a flat map,” said Thorup. “For example, surfaces with holes, such as a swim ring or a piece of…cheese.”
Okay, so the implications may be somewhat subtle for most people’s day-to-day lives. That doesn’t change the fact that mathematicians finally worked through symptoms of their disease for the first time in 30 years. As to why Thorup and his colleagues spent a decade on a theorem whose major immediate implications are “cheese,” he had a relatively succinct explanation.
“Because mathematicians are slightly crazy. Most of what mathematicians work on consists of very nerdy questions,” he said. “We become obsessed with this type of problem because it challenges the human intellect. And if we find the answer, we’ll probably also find answers to other mathematical puzzles.”
The post Mathematicians make a breakthrough in 174-year-old problem appeared first on Popular Science.





