Discrete differentiation and local rigidity of smooth sets in the plane
Seminar Room 1, Newton Institute
We exhibit an infinite doubling metric space whose n-point subsets
require distortion sqrt(log n/log log n) to embed into L_1. This
nearly matches the upper bound of sqrt(log n) (Gupta-Krauthgamer-Lee 2003)
and improves over the best previous bound of (log n)^c for some c > 0
(Cheeger-Kleiner-Naor 2009). Furthermore, this offers a nearly tight
integrality gap for a weak version of the Goemans-Linial SDP for Sparsest Cut, matching the upper bound of Arora-Lee-Naor (2005). We discuss how our results might lead to a resolution of the full Goemans-Linial conjecture.
Following the general approach developed by Cheeger and Kleiner (2006), our lower bound uses a differentiation argument to achieve local control on the cut measure, followed by a classification step of the cuts that can appear. In order to get tight bounds, the classification step has to deal with sets which satisfy only a weak average regularity assumption, meaning that we have to control not just "99%-structured sets," but "1%-structured" sets as well. This weak regularity is achieved via a random differentiation
argument which measures the variation of the function along randomly chosen subdivisions of geodesics.
Our lower bound space is a 2-dimensional complex which takes inspiration from both the Heisenberg group and the diamond graphs.
This is joint work with James R. Lee (University of Washington).