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. (April 21) A great blog post (French) on Automath.
(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.
Combinatorics and more 
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?
Hmm, my guess is that it is not the same problem and perhaps for
the chromatic number is finite and small.
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.
Pingback: The chromatic number of the plane is at least 5 – Short, Fat Matrices
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):
https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/#comment-3748
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.
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. —
Pingback: Shtetl-Optimized » Blog Archive » Amazing progress on longstanding open problems
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:
https://mathoverflow.net/questions/236392/has-there-been-a-computer-search-for-a-5-chromatic-unit-distance-graph#297407
Pingback: Coloring Problems for Arrangements of Circles (and Pseudocircles) | Combinatorics and more
Pingback: 5 nuances d’Aubrey de Grey | Automaths
Pingback: The BREAKTHROUGH on Chromatic Number of the Plane (guest post) – Site Title
Pingback: When is one 'ready' to make original contributions to mathematics? - My Blog
Pingback: Greatest Hits 2015-2022, Part I | Combinatorics and more