This is the second “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.
What follows is a summary of the progress made thus far:
Simplifying de Grey’s graph. There have been three strides along these lines. One is to decrease the size of the graph by iteratively removing vertices that are not necessary to be 5-chromatic. This approach has led to our current record holder, which has 826 vertices and 4273 edges. Another approach has been to hunt for more symmetric 5-chromatic graphs, in the hopes that such graphs might be easier to analyze by hand (e.g., see this and that). Finally, others have been hunting for extremely small alternatives to de Grey’s L and M graphs that are amenable to by-hand analysis, in the hopes that these would eventually lead to a 5-chromatic graph (e.g., see this and that).
Continue reading Polymath16, second thread: What does it take to be 5-chromatic?
Given the initial activity on the Polymath proposal page, Terry Tao suggested that Aubrey de Grey and I launch Polymath16 to make progress on the Hadwiger–Nelson problem. This project is a follow-up to Aubrey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.
The Hadwiger–Nelson problem is that of determining the chromatic number of the plane (CNP), defined as the minimum number of colours that must be assigned to the points of the plane in order to prevent any two points unit distance apart from being the same colour. It was first posed in 1950 and was reduced the following year to a finite graph problem; in particular, CNP is at least k if and only if there exists a finite graph of chromatic number k that can be drawn in the plane with each edge being a straight line of unit length. Such graphs are termed unit-distance graphs. It is easy to find 4-chromatic unit-distance graphs, the smallest being the 7-vertex Moser spindle.
Continue reading Polymath16, first thread: Simplifying de Grey’s graph
As a follow-up to my previous post, I wanted to discuss an overview of de Grey’s proof that the chromatic number of the plane is at least 5, as well as some recent progress that has been made on the polymath proposal page and elsewhere.
The core idea of de Grey’s proof is to select a finite point set H in the plane and a coloring property P, and then demonstrate two incongruous statements:
(a) For every proper k-coloring of the plane, there exists a copy of H whose inherited coloring satisfies P.
(b) For every proper k-coloring of the plane, every copy of H inherits a coloring that doesn’t satisfy P.
Indeed, if both statements hold, then there is no proper k-coloring of the plane. To prove (a) and (b), we pass to finite unit-distance graphs in the plane. Explicitly, to prove (a), one finds a finite point set L such that for every proper k-coloring of L, there exists a copy of H in L whose inherited coloring satisfies P. Similarly, to prove (b), one finds a finite superset M of H such that every proper k-coloring of M forces the inherited coloring of H to not satisfy P.
Continue reading The chromatic number of the plane is at least 5, part II
One of the coolest open problems in math is the chromatic number of the plane (CNP), that is, the Hadwiger–Nelson problem. Considering it has a unit-distance embedding in the plane, the Moser spindle ensures that CNP is at least 4. Furthermore, one may tile the plane with hexagons of the appropriate size and then color those tiles with 7 colors to prove that CNP is at most 7. Yesterday, Aubrey de Grey posted a paper on the arXiv that proves that CNP is at least 5 (see also announcements from Gil Kalai, Jordan Ellenberg and Terry Tao). As one might expect, the graphs in his proof feature an amalgam of spindle-type structures. de Grey describes a unit distance graph of 20,425 vertices that is not 4-colorable, and then he describes how to find smaller graphs with this property. He concludes with a description of a graph with 1567 vertices. He has since proposed a polymath project to decrease this number even further.
Continue reading The chromatic number of the plane is at least 5
Last week, I co-organized (with Joey Iverson and John Jasper) a special session on “Recent Advances in Packing” for the AMS Spring Central Sectional Meeting at the Ohio State University. All told, our session had 13 talks that covered various aspects of packing, such as sphere packing, packing points in projective space, applications to quantum physics, and connections with combinatorics. It was a great time! And after the talks, we learned how to throw axes!
What follows is the list of speakers and links to their slides. (I anticipate referencing these slides quite a bit in the near future.) Thanks to all who participated!
Continue reading Recent Advances in Packing
Smoothed analysis was introduced by Spielman and Teng to help explain how the simplex method efficiently solves real-world linear programs despite having a large worst-case complexity. Perhaps a natural analog to the simplex method for semidefinite programs (SDPs) is the Burer–Monteiro factorization method, in which the decision variable matrix is assumed to have rank at most , and is therefore replaced by for some matrix . Recently, Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain and Praneeth Netrapalli posted a paper on the arXiv that uses smoothed analysis to analyze the landscape of this factorized problem. In particular, they show that a large class of SDPs have the property that for every cost matrix, a random perturbation of the cost matrix will ensure that, with high probability, all approximate local optima of the Burer–Monteiro problem are approximately optimal in the perturbed SDP. (To be explicit, these approximate local optima are approximate second-order stationary points, or approximate SOSPs, which exhibit a small gradient and a nearly positive semidefinite Hessian.) I reached out to the authors to learn more, and ended up interviewing both Nicolas and Srinadh. I’ve lightly edited their responses for formatting and hyperlinks:
Continue reading Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Recall that . Perhaps the shortest proof of applies (the sophisticated) Parseval’s identity of the Fourier series to . By contrast, the simple (but long) proof in this paper, which was recently popularized by the video below, uses basic ideas from Euclidean geometry.
The following argument interpolates between these two, resulting in a proof that is both simple and short.
Continue reading Another simple solution to the Basel problem