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
I just returned from an amazing workshop in New Zealand organized by Shayne Waldron. The talks and activities were both phenomenal! Here’s a photo by Emily King that accurately conveys the juxtaposition:
A few of the talks gave me a lot to think about, and I wanted to take a moment to record some of these ideas.
Continue reading Tight Frames and Approximation 2018
The following tweet has been making the rounds on social media:
Notice that since the Democrats won overall, it would be impossible for Republicans to win all seven districts, no matter how the map was drawn. As such, you might say that Alabama has been gerrymandered as effectively as possible. Sure enough, you can find the usual tell-tale signs of gerrymandering: Some of the district boundaries exhibit strange jagged portions — these portions undoubtedly maneuver to include some parts of the map while avoiding others.
Continue reading Partisan gerrymandering with geographically compact districts