Abstract
We prove a quantitative bi-Lipschitz non-embedding theorem for the Heisenberg group with its Carnot–Carathéodory metric and apply it to give a lower bound on the integrality gap of the Goemans–Linial semidefinite relaxation of the sparsest cut problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ambrosio, L., Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces. Adv. Math., 159 (2001), 51–67.
Ambrosio, L., Fine properties of sets of finite perimeter in doubling metric measure spaces. Set-Valued Anal., 10 (2002), 111–128.
Ambrosio, L., Fusco, N. & Pallara, D., Functions of Bounded Variation and Free Discontinuity Problems. Oxford Mathematical Monographs. Oxford University Press, New York, 2000.
Aronszajn, N., Differentiability of Lipschitzian mappings between Banach spaces. Studia Math., 57 (1976), 147–190.
Arora, S., Lee, J. R. & Naor, A., Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21 (2008), 1–21.
Arora, S., Rao, S. & Vazirani, U., Expander flows, geometric embeddings and graph partitioning, in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 222–231. ACM, New York, 2004.
Arzhantseva, G., Drutu, C. & Sapir, M., Compression functions of uniform embeddings of groups into Hilbert and Banach spaces. J. Reine Angew. Math., 633 (2009), 213–235.
Assouad, P., Plongements Lipschitziens dans R n. Bull. Soc. Math. France, 111 (1983), 429–448.
Aumann, Y. & Rabani, Y., An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27 (1998), 291–301.
Avis, D. & Deza, M., The cut cone, L 1 embeddability, complexity, and multicommodity flows. Networks, 21 (1991), 595–617.
Bates, S., Johnson, W.B., Lindenstrauss, J., Preiss, D. & Schechtman, G., Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal., 9 (1999), 1092–1127.
Bourgain, J., On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52 (1985), 46–52.
Brendle, S. & Schoen, R., Manifolds with 1/4-pinched curvature are space forms. J. Amer. Math. Soc., 22 (2009), 287–307.
Burago, D., Burago, Y. & Ivanov, S., A Course in Metric Geometry. Graduate Studies in Mathematics, 33. Amer. Math. Soc., Providence, RI, 2001.
Chawla, S., Gupta, A. & Räcke, H., Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4 (2008), Art. 22, 18 pp.
Cheeger, J. & Colding, T. H., Lower bounds on Ricci curvature and the almost rigidity of warped products. Ann. of Math., 144 (1996), 189–237.
Cheeger, J. & Colding, T. H., On the structure of spaces with Ricci curvature bounded below. I. J. Differential Geom.,46 (1997), 406–480.
Cheeger, J. & Kleiner, B., On the differentiability of Lipschitz maps from metric measure spaces to Banach spaces, in Inspired by S. S. Chern, Nankai Tracts Math., 11, pp. 129–152. World Sci. Publ., Hackensack, NJ, 2006.
Cheeger, J. & Kleiner, B., Differentiability of Lipschitz maps from metric measure spaces to Banach spaces with the Radon–Nikodým property. Geom. Funct. Anal., 19 (2009), 1017–1028.
Cheeger, J. & Kleiner, B., Differentiating maps into L 1, and the geometry of BV functions. Ann. of Math., 171 (2010), 1347–1385.
Cheeger, J. & Kleiner, B., Metric differentiation, monotonicity and maps to L 1. Invent. Math., 182 (2010), 335–370.
Cheeger, J. & Kleiner, B., Realization of metric spaces as inverse limits, and bilipschitz embedding in L 1. Preprint, 2011. arXiv:1110.2406 [math.MG].
Cheeger, J. & Kleiner, B., Metric differentiation for PI spaces. In preparation.
Cheeger, J., Kleiner, B. & Naor, A., A (log n)Ω(1) integrality gap for the sparsest cut SDP, in Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 555–564. IEEE Computer Society, Los Alamitos, CA, 2009.
De Giorgi, E., Su una teoria generale della misura (r−1)-dimensionale in uno spazio ad r dimensioni. Ann. Mat. Pura Appl., 36 (1954), 191–213.
De Giorgi, E., Nuovi teoremi relativi alle misure (r−1)-dimensionali in uno spazio ad r dimensioni. Ricerche Mat., 4 (1955), 95–113.
Deza, M. M. & Laurent, M., Geometry of Cuts and Metrics. Algorithms and Combinatorics, 15. Springer, Berlin–Heidelberg, 1997.
Enflo, P., On the nonexistence of uniform homeomorphisms between L p -spaces. Ark. Mat., 8 (1969), 103–105.
Franchi, B., Serapioni, R. & Serra Cassano, F., Rectifiability and perimeter in the Heisenberg group. Math. Ann., 321 (2001), 479–531.
Franchi, B., Serapioni, R. & Serra Cassano, F., On the structure of finite perimeter sets in step 2 Carnot groups. J. Geom. Anal., 13 (2003), 421–466.
Goemans, M. X., Semidefinite programming in combinatorial optimization. Math. Program., 79 (1997), 143–161.
Gromov, M., Asymptotic invariants of infinite groups, in Geometric Group Theory, Vol. 2 (Sussex, 1991), London Math. Soc. Lecture Note Ser., 182, pp. 1–295. Cambridge University Press, Cambridge, 1993.
Gromov, M., Metric Structures for Riemannian and Non-Riemannian Spaces. Modern Birkhäuser Classics. Birkhäuser, Boston, MA, 2007. Based on the 1981 French original.
Grötschel, M., Lovász, L. & Schrijver, A., Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, 2. Springer, Berlin–Heidelberg, 1993.
Gupta, A., Krauthgamer, R. & Lee, J. R., Bounded geometries, fractals, and lowdistortion embeddings, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 534–543. IEEE Computer Society, Los Alamitos, CA, 2003.
Hajłasz, P. & Koskela, P., Sobolev met Poincaré. Mem. Amer. Math. Soc., 145:688 (2000).
Heinonen, J., Lectures on Analysis on Metric Spaces. Universitext. Springer, New York, 2001.
Heinonen, J. & Koskela, P., From local to global in quasiconformal structures. Proc. Nat. Acad. Sci. U.S.A., 93 (1996), 554–556.
Johnson, W. B. & Lindenstrauss, J., Extensions of Lipschitz mappings into a Hilbert space, in Conference in Modern Analysis and Probability (New Haven, CT, 1982), Contemp. Math., 26, pp. 189–206. Amer. Math. Soc., Providence, RI, 1984.
Jones, P. W., Lipschitz and bi-Lipschitz functions. Rev. Mat. Iberoam., 4 (1988), 115–121.
Khot, S. & Vishnoi, N., The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ 1, in Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science (FOCS 2005), pp. 53–62. IEEE Computer Society, Los Alamitos, CA, 2005.
Krauthgamer, R., Lee, J. R., Mendel, M. & Naor, A., Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal., 15 (2005), 839–858.
Krauthgamer, R. & Rabani, Y., Improved lower bounds for embeddings into L 1, in Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 1010–1017. ACM, New York, 2006.
Kuratowski, K. & Ryll-Nardzewski, C., A general theorem on selectors. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 13 (1965), 397–403.
Laakso, T. J., Ahlfors Q-regular spaces with arbitrary Q>1 admitting weak Poincaré inequality. Geom. Funct. Anal., 10 (2000), 111–123.
Lang, U. & Plaut, C., Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87 (2001), 285–307.
Lee, J. R. & Naor, A., Extending Lipschitz functions via random metric partitions. Invent. Math., 160 (2005), 59–95.
Lee, J. R. & Naor, A., L p metrics on the Heisenberg group and the Goemans–Linial conjecture, in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 99–108. IEEE Computer Society, Los Alamitos, CA, 2006.
Leighton, T. & Rao, S., Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46 (1999), 787–832.
Lindenstrauss, J., On nonlinear projections in Banach spaces. Michigan Math. J., 11 (1964), 263–287.
Linial, N., Finite metric spaces—combinatorics, geometry and algorithms, in Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pp. 573–586. Higher Ed. Press, Beijing, 2002.
Linial, N., Squared ℓ 2 metrics into ℓ 1, in Open Problems on Embeddings of Finite Metric Spaces. 2002. Available at http://kam.mff.cuni.cz/~matousek/metrop.ps.
Linial, N., London, E. & Rabinovich, Y., The geometry of graphs and some of its algorithmic applications. Combinatorica, 15 (1995), 215–245.
Matoušek, J., Lectures on Discrete Geometry. Graduate Texts in Mathematics, 212. Springer, New York, 2002.
Montefalcone, F., Some relations among volume, intrinsic perimeter and onedimensional restrictions of BV functions in Carnot groups. Ann. Sc. Norm. Super. Pisa Cl. Sci., 4 (2005), 79–128.
Montgomery, R., A Tour of Subriemannian Geometries, their Geodesics and Applications. Mathematical Surveys and Monographs, 91. Amer. Math. Soc., Providence, RI, 2002.
Pansu, P., Métriques de Carnot–Carathéodory et quasiisométries des espaces symétriquesde rang un. Ann. of Math., 129 (1989), 1–60.
Rao, S., Small distortion and volume preserving embeddings for planar and Euclidean metrics, in Proceedings of the 15th Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), pp. 300–306. ACM, New York, 1999.
Shahrokhi, F. & Matula, D. W., The maximum concurrent flow problem. J. ACM, 37 (1990), 318–334.
Shmoys, D. B., Cut problems and their application to divide-and-conquer, in Approximation Algorithms for NP-hard Problems, pp. 192–235. PWS, Boston, MA, 1997.
Stein, E. M., Harmonic Analysis: Real-Variable Methods, Orthogonality, and Oscillatory Integrals. Princeton Mathematical Series, 43. Princeton University Press, Princeton, NJ, 1993.
Tessera, R., Quantitative property A, Poincaré inequalities, L p-compression and L p-distortion for metric measure spaces. Geom. Dedicata, 136 (2008), 203–220.
Wells, J. H. & Williams, L. R., Embeddings and Extensions in Analysis. Ergebnisse der Mathematik und ihrer Grenzgebiete, 84. Springer, New York, 1975.
Wojtaszczyk, P., Banach Spaces for Analysts. Cambridge Studies in Advanced Mathematics, 25. Cambridge University Press, Cambridge, 1991.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cheeger, J., Kleiner, B. & Naor, A. Compression bounds for Lipschitz maps from the Heisenberg group to L 1 . Acta Math 207, 291–373 (2011). https://doi.org/10.1007/s11511-012-0071-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11511-012-0071-9