Decades-Old Graph Problem Yields to Amateur Mathematician

Episode Summary

Executive Summary: The episode profiles Aubrey de Grey’s unexpected breakthrough on the Hadwiger-Nelson problem, a decades-old question in graph coloring about the minimum number of colors needed for the plane. It explains the math behind the problem, de Grey’s construction proving at least five colors are needed, and how open, collaborative “polymath” work is helping shrink the graph and explore whether the exact answer may be five, six, or seven.

Main Topics: The Hadwiger-Nelson problem (Priority: 5/5): A long-standing graph-coloring puzzle asks for the chromatic number of the plane: if every point in the plane is a vertex and edges connect points exactly one unit apart, how many colors are required so adjacent points differ? Aubrey de Grey’s breakthrough (Priority: 5/5): De Grey, a biologist rather than a professional mathematician, posted a preprint proving a unit-distance graph exists that cannot be colored with four colors, pushing the lower bound to at least five. Amateur contributions to mathematics (Priority: 4/5): The segment highlights that significant mathematical progress can come from non-professionals, citing de Grey and historical examples such as Marjorie Rice. Graph theory and the four-color theorem (Priority: 4/5): The episode compares the plane-coloring problem to the classic four-color theorem for maps and explains how both are translated into graph-theoretic language. Polymath collaboration and open problem-solving (Priority: 4/5): Terence Tao’s polymath framework is described as a way to crowdsource progress on problems that are easy to start and have clear success metrics, like minimizing the size of a five-color counterexample. Computational refinement of de Grey’s construction (Priority: 3/5): Researchers quickly reduced de Grey’s original 20,425-vertex example to smaller graphs, showing the problem may admit further advances through iterative search and ingenuity.

Key Arguments: De Grey’s result is the first major advance on the chromatic number of the plane in decades, showing the lower bound is at least five colors. The problem is accessible enough that non-mathematicians can contribute meaningful results, especially in combinatorics and graph theory. The lower-bound proof relies on constructing a finite unit-distance graph that cannot be colored with four colors, rather than solving the infinite plane directly. Polymath-style open collaboration is well suited to this problem because it has a clear objective: reduce the size of a graph that forces five colors. The episode suggests the eventual solution could come from either deep theory or clever construction, not necessarily from heavy technical machinery. Historical precedents such as Marjorie Rice show amateurs can produce real mathematical breakthroughs when the problem is approachable and concrete.

Data Points: Year the problem was posed: 1950 - Edward Nelson posed the graph-coloring question while a student at the University of Chicago. Known bounds before de Grey: 4 to 7 colors - Mathematicians had established that the plane can be colored with no fewer than four and no more than seven colors. Original graph size: 20,425 vertices - De Grey’s first construction of a unit-distance graph that required at least five colors. Reduced graph size: 1,581 vertices - De Grey later shrank his construction and verified it still resisted four-coloring. Further reduced graph size: 1,577 vertices - Found by Ohio State mathematician Dustin Mixon and collaborator Boris Alexiev. Further reduced graph size: 826 vertices - Found by computer scientist Marijn Holla at the University of Texas, Austin. Moser Spindle vertices: 7 vertices - A classic graph gadget used by de Grey as a building block in his construction. Moser Spindle edges: 11 edges - The Moser Spindle is described as having 11 edges and chromatic number four. Time scale of the open problem: 60 years - The episode frames the Hadwiger-Nelson problem as a 60-year-old open question. Related historical example: 4 new pentagons - Marjorie Rice added four new pentagons to the list of plane-tiling pentagons. Polymath origin: About 10 years ago - Timothy Gowers launched the polymath collaboration model roughly a decade before this episode.

Pivotal Quotes: "I feel, of course, that I got extraordinarily lucky." — Aubrey de Grey: De Grey reflects on solving a major math problem despite not being a professional mathematician. "The problem is easy to understand and start working on, and there's a clear measure of success." — Terence Tao: Why this problem is a good candidate for a public polymath collaboration. "If they're clever enough and cunning enough, they just might make a real contribution to the field." — Gordon Royal: On the ability of non-mathematicians to contribute to combinatorics.

Implications: The story shows that open, collaborative mathematics can accelerate progress on old problems and that amateurs can make meaningful contributions. It also leaves the chromatic number of the plane unresolved, but closer to a definitive answer.