Amateur mathematician makes key advance in classic graph theory problem

Introduction

In a curious turn of events, British biogerontologist Aubrey de Grey, a well-known author and Chief Science Officer of the SENS Research Foundation, which is devoted to “reversing the negative effects of aging” and “significantly extending the human lifespan,” has made a significant advance in a 60-year-old graph theory problem.

Needless to say, in this day and age when almost all frontier-level mathematical research requires substantial training and, regrettably, specialization, it is not very often that an person without graduate-level formal training in mathematics, and whose professional life is focused almost entirely in a completely different field, makes a notable advance in the mathematics. One struggles to think of any other comparable example, or even an apt analogy: A Silicon Valley CEO who discovers a new species of hominin fossils? A Wall Street quant mathematician who publishes a key advance in biogenesis? In this light, de Grey’s paper The chromatic number of the plane is at least 5 is even more remarkable.

de Grey is not a complete stranger to graph theory. Several decades ago, de Grey was an avid player of “Othello” (a computer-based version of Reversi). In the process he befriended some mathematicians, who in turn introduced him to graph theory. de Grey still works on graph theory from time to time: “Occasionally, when I need a rest from my real job, I’ll think about math” (see this Quanta article for more details). Still, his latest achievement is pretty impressive.

The planar chromatic number problem

The problem in question is now known as the Hadwiger-Nelson problem, also known as the “planar chromatic number” problem or simply the “graph coloring problem”: What is the smallest number of colors required to color the vertices of a graph, where all connecting lines are the same length, with the restriction that no pair of connected points can have the same color?

Shortly after this problem was first posed by Edward Nelson in 1950, Nelson himself observed that a simple 7-vertex graph known as the Moser spindle requires at least four colors. Subsequently it was shown that the chromatic number does not exceed seven. But since 1950, until de Grey’s paper, no improvement had been made to either bound.

de Grey’s construction

de Grey demonstrated that the planar chromatic number must exceed five by exhibiting a 1581-vertex graph, with all segments of unit length, and showing that it cannot be colored with just four colors. A brief sketch of his construction is as follows:

1. Noting that a 7-vertex regular hexagon H can be colored with at most four colors in four essentially distinct ways.
2. Constructing a unit-distance graph L containing 52 copies of H, and showing that in all four-colorings of L, at least one copy of H contains a monochromatic triple.
3. Constructing a unit-distance graph M, and a larger graph N with 52 copies of M that is not four-colorable.
4. Using a computer to identify smaller unit-distance graphs that are not four-colorable, by deleting vertices that preserve the non-four-coloring property and also by more elaborate methods.

de Grey’s 1581-vertex non-four-colorable graph is illustrated at the right. For additional details, see this very nice Quanta article by Evelyn Lamb, as well as de Grey’s well-written paper itself.

Subsequent work

Even though de Grey’s paper is only 12 days old, as of this writing, other mathematicians have already discovered other non-four-colorable graphs with even fewer vertices. In particular, mathematicians working on the PolyMath project (an Internet-based collaborative mathematical project organized by UCLA mathematician Terence Tao) reduced the size of known non-four-colorable unit-distance graphs to 1577, then, in a dramatic reduction, to 874 and finally to 826 (as of this writing).

Congratulations to de Grey, and to those other mathematicians who have further developed this interesting work!