(The new SIGACT News chair wnated me to post a letter he send to all SIGACT members on my blog in case you are not in SIGACT. He thinks you should be. I think so to so next year he won't ask me to do this. Here is his letter: here)
As many of you know there was a BREAKTHROUGH on the problem of the The Chromatic Number of The Plane. There have been fine blog posts on this by Gil Kalai here amd Scott Aaronson here. Rather than blog on it ourselves we have recruited and expert in the field, Alexander Soifer. He has written a book on the history and mathematics of coloring problems (see here for the amazon link to the book and here for my review of the book). The Chromatic Number of the Plane is his favorite problem. Much of the work on it is either by him or inspired by him. Much of the book is on it.
Alexander also is the editor of a journal on problems like this called GEOCOMBINATORICS (oddly enough. Geometric Combinatorics is a different field). See here for that journal- which I recommend!
He wrote an 8-page essay, which is a concise version of an essay that will appear in a Special Issue XXVIII (1) of Geocombinatorica (July 2018, 5-17), dedicated to 5-chromatic unit distance graphs. The essay includes contributions from Aubrey D.N.J de Grey, Marijn J.H. Heule, and Geoffrey Exoo
and Dan Ismailescu.
What I find remarkable is that even though the result is new, the essay contains NEWER results. The modern world moves fast!
Without further ado, here is that essay: here.
So there exists at least one example unit distance graph that cannot be 4-colored in a way that no adjacent points have the same color?
ReplyDelete