Danish-led team produces new proof of century-old four-color theorem
Researchers offer a more efficient algorithm and new insights into planar graphs, despite the proof being computationally complex.
What to know
- A Danish-led international team has produced a new computer-assisted proof of the four-color theorem, a famous 150-year-old mathematical problem that had resisted resolution until the 1970s.
- The new proof is computationally more intensive than previous versions but yields a significantly more efficient algorithm for coloring maps.
- Beyond confirming the theorem, the work uncovered new structural insights into planar graphs that could accelerate solutions to other long-standing problems in graph theory.
“Here we have a problem that even a child can understand. I think that's the reason why it has been such a big challenge.”
Carsten Thomassen, Graph theorist, Technical University of Denmark · Quanta Magazine ↗
Mikkel Thorup Computer scientist, University of CopenhagenCarsten Thomassen Graph theorist, Technical University of DenmarkKen-ichi Kawarabayashi MathematicianBojan Mohar MathematicianGeorges Gonthier Computer scientist, Inria Paris
How it unfolded 1 development · click the chart to see its coverage articlesposts
-
1
New four-color proof yields more efficient algorithm and graph insights
Quanta Magazine reports that the new proof, despite being computationally complex, provides a far more efficient way to color maps and uncovers new insights into planar graph properties that may enable progress on other stubborn graph theory problems. The team will present findings at the November Foundations of Computer Science conference.
“For such a simple statement, there must be a simpler reason why it is true. Or at least a more efficient way to demonstrate it.”
— Mikkel Thorup -
first by Quanta Magazine, 13d ago · also HN Frontpage, Quanta
-
By revisiting a famous problem first controversially solved with computer assistance in the 1970s, mathematicians have developed a rare new proof of the four-colour theorem and deepened understanding # science # mathematics # proofs https://www. quantamagazine.org/the-four-co…
2 more of the top 3 · 3 posts in this stretch
-
After nearly a decade of work, a team of researchers has re-proved the four-color theorem, a problem with a long history of false starts and dashed hopes. Their method opens up the potential for progress on many other stubborn problems in graph theory. — www.quantamagazine.org/the-four- col...
-
S
"[I]n the process of crafting their argument, the researchers provided a far more efficient way to color maps. And in doing so, they uncovered new insights into structural properties of important mathematical objects called planar graphs — opening up the potential for progress on many other stubborn problems in graph theory." https://www…
-
-
background
Thorup and Thomassen team posts new proof online — After nearly a decade of work, a team including Mikkel Thorup, Carsten Thomassen, Ken-ichi Kawarabayashi, Bojan Mohar, and colleagues from Denmark, Canada, and Japan posts a new computer proof of the four-color theorem online.
-
background
Simpler computer-assisted proof published — A more streamlined computer-assisted proof emerges as computers become more accepted in mathematical practice, partially resolving earlier skepticism about computational methods.
-
background
Original proof shown to be incorrect — After 11 years, the 1879 proof is discovered to be flawed, beginning a pattern of multiple incorrect attempts by lawyers, doctors, and mathematicians.
-
background
First purported four-color theorem proof announced — A claimed proof of the four-color theorem is announced, establishing the problem as a major mathematical puzzle.