Public

Progress on the Hadwiger-Nelson problem! Thanks to a computer-assisted search, a finite collection of points in the plane has been located such that it is not possible to 4-color the points so that pairs of points a unit distance apart always have distinct colors. Hence the possible values of the chromatic number of the plane has now been narrowed down to 5, 6, or 7. (EDIT: the graph was found by hand, but the verification of non-4-colorability was computer assisted.)

The author (Aubrey de Grey, who incidentally was an amateur mathematician that had contributed to some previous Polymath projects) is interested in starting a project to reduce the amount of computer assistance required (right now one has to check that certain graphs with a couple thousand vertices are not 4-colorable, which is beyond the capability of human verification). For those interested in this, he can be reached on twitter at https://twitter.com/aubreydegrey

UPDATE: There is now a polymath proposal on this at polymathprojects.org/2018/04/10/polymath-proposal-finding-simpler-unit-distance-graphs-of-chromatic-number-5/

The author (Aubrey de Grey, who incidentally was an amateur mathematician that had contributed to some previous Polymath projects) is interested in starting a project to reduce the amount of computer assistance required (right now one has to check that certain graphs with a couple thousand vertices are not 4-colorable, which is beyond the capability of human verification). For those interested in this, he can be reached on twitter at https://twitter.com/aubreydegrey

UPDATE: There is now a polymath proposal on this at polymathprojects.org/2018/04/10/polymath-proposal-finding-simpler-unit-distance-graphs-of-chromatic-number-5/

View 5 previous comments

- thanks! As noted, I've suggested to Terry that there might be a Polymath project here, to find simpler examples with a stretch goal of obviating the need for computer assistance, and I think he will post my suggestion on the polymath blog shortly. What do you think?1w
- +Aubrey de Grey sounds like an excellent idea, and I think this is the kind of project that Polymath does well at (ie finding smaller graphs, pulling apart the construction so better understand it etc)1w
- I don't know enough about the problem, but have people tried applying an SMT solver like Z3 to simplifying the search? Z3, and SMT solvers in general, are amazing swiss army sledgehammers. When you can figure out how to use them, they can do amazing things.1w
- Oh, and, hello +Aubrey de Grey!1w
- Aubrey's polymath proposal is now on the blog: polymathprojects.org/2018/04/10/polymath-proposal-finding-simpler-unit-distance-graphs-of-chromatic-number-5/1w
- Thanks Terry! David, I'm glad you like it - yes, that's part of the reason for my enthusiasm too. I also like the fact that it's graph theory, which has such appeal to the non-specialist - and the interaction between theory and computation.1w

Add a comment...