Aubrey de Grey: The chromatic number of the plane is at least 5


A major progress on an old standing beautiful problem. Aubrey de Grey proved that the chromatic number of the plane is at least 5. (I first heard about it from Alon Amit.)

The Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance one from each other have the same color. The answer is referred to as the chromatic number of the plane. The problem was posed in 1950 by Edward Nelson, and related results already appeared in a paper by Hugo Hadwiger from 1945. Untill recently it was known that the answer can be 4,5,6 or 7. The Moser spindle is a simple example of a unit-distance graph with chromatic number 4, and there is a simple coloring of the plane, found by Isbell, based on the hexagonal packing with 7 colors so that no color contains a pair of points of distance 1.

Aubrey de Grey has constructed  a unit distance graph with 1567 vertices which is 5-chromatic!


Updates: Aubrey de Grey has made now a polymath proposal over the polymath blog aimed at finding simpler constructions, namely constructions with a smaller number of vertices, or where the computerized part of the proof is simpler. Of course, this project may lead to independent verification of the result, and perhaps even insights for what is needed to replace ‘5’ with ‘6’. Noam Elkies independently proposed over MathOverflow a polymath project following Aubrey de Grey’s paper. (April 14) Dustin Mixon and Aubrey de Grey have launched Polymath16 over at Dustin’s blog. The project is devoted to the chromatic number of the plane (Wikipage) following Aubrey de Grey’s example showing that the chromatic number of the plane is at least 5.

Here is an earlier Google+ post by Terry Tao and an earlier blogpost on the new result by Jordan Ellenberg proposing to use the polynomial method to tackle the upper bound. A blog post reporting on independent verification of some of the new results is over Dustin G. Mixon’s blog  Short, Fat Matrices. A post over Shtetl Optimized describes the new development along with another important development on quantum computation. Let me also mention two related old posts over Lipton and Regan’s blog (one, two). (April 19) An excellent article on Quanta Magazine by Evelyn Lamb.

(From Wikipedea: A seven-coloring of the plane, and a four-chromatic unit distance graph in the plane (the Moser spindle), providing upper and lower bounds for the Hadwiger–Nelson problem.) Below, two figures from Aubret de Grey’s paper.

Let me also mention the related Rosenfeld’s problem discussed in this post: Let G be the graph whose vertices are points in the plane and two vertices form an edge if their distance is an odd integer. Is the chromatic number of this graph finite?

These and related problems are discussed also in my survey article: Some old and new problems in combinatorial geometry I: Around Borsuk’s problem.

This entry was posted in Combinatorics, Geometry, Open problems, Updates and tagged , . Bookmark the permalink.

9 Responses to Aubrey de Grey: The chromatic number of the plane is at least 5

  1. JSE says:

    In that Rosenfeld problem, do you think it’s essentially the same problem if the vertices are points in Z^2 instead of points in R^2?

    • Gil Kalai says:

      Hmm, my guess is that it is not the same problem and perhaps for \mathbb Z^2 the chromatic number is finite and small.

    • Kevin Costello says:

      I think the usual checkerboard coloring works for 2 colors here — for two points to be an odd integer distance apart, one coordinate difference must be odd and the other even.

  2. Pingback: The chromatic number of the plane is at least 5 – Short, Fat Matrices

  3. ag24ag24 says:

    Update: the smallest case may need to be revised up to 1585 vertices. Many thanks to Brendan McKay and Gordon Royle for letting me know overnight that they had successfully 4-coloured my 1567er; as a result I found a bug in the part of my code that implements the relaxation described in section 5.4 and now it agrees. Mercifully this only means, in the worst case, that fewer than nine vertices can be removed from S to make Sa; the worst case is that we could remove none, which leaves the full graph with 1585 vertices, and I’m pleased to say that Dustin Mixon and Boris Alexeev have confirmed the non-4-colorability of that graph using a completely different algorithm than mine (a SAT solver):

    It will probably take me the rest of the day to determine how many vertices I can in fact remove from S to make Sa; I will post here when I have an answer.

  4. g a exoo says:

    the 1345 vertex graph in de Grey’s paper is solid. i also used a graph coloring program to verify the 1587? order example. it finishes remarkably fast. a well designed graph. —

  5. Pingback: Shtetl-Optimized » Blog Archive » Amazing progress on longstanding open problems

  6. ag24ag24 says:

    Update: after fixing my bug and re-running the code that seeks deletions from Sa, I now find that just two vertices can be deleted wtthout introducing a problematic (as defined in section 5.4) 4-coloring. This therefore leads to a size of 1581 for the full 5-chromatic graph (which contains two copies of Sa). I have just uploaded to the arxiv a revision of my paper (I gather it will go live within a few hours), incorporating this correction as well as making the construction clearer in section 6 (and adding a number of particularly apposite acknowledgements!). Whew! I will now post this update to the slew of other blogs I know of where the topic is being discussed, and I’ll also fix Wikipedia’s page on the H-N problem (I didn’t make the initial edit that reported 1567, but I think speed is of the essence for that).

    Thank you Geoffrey!

    And there is another confirmation of the 1585er noted here:

  7. Pingback: Coloring Problems for Arrangements of Circles (and Pseudocircles) | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s