Compression bounds for Lipschitz maps from the Heisenberg group to L₁

2009/10/11 by Jeff Cheeger, Bruce Kleiner, Cheeger, Jeff +3
Computer Science · Mathematics · Physics and Astronomy · #Advanced Differential Geometry Research #Data Structures and Algorithms (cs.DS) #Differential Geometry (math.DG) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Geometric Analysis and Curvature Flows #Group Theory (math.GR) #Metric Geometry (math.MG) #Point processes and geometric inequalities #cs.DS #math.DG #math.FA #math.GR #math.MG

paper · pdf · doi:10.48550/arxiv.0910.2026

arxiv created 2009/10/11 · openalex publication_date 2009/10/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove a quantitative bi-Lipschitz nonembedding 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.

Citations

• Lower Bounds on Ricci Curvature and the Almost Rigidity of Warped Products
• Manifolds with 1/4-pinched curvature are space forms
• Differentiability of Lipschitz maps from metric measure spaces to Banach spaces with the Radon Nikodym property
• Metriques de Carnot-Caratheodory et Quasiisometries des Espaces Symetriques de rang un

Related

• A (log n)^Ω(1) integrality gap for the Sparsest Cut SDP
• L₁ embeddings of the Heisenberg group and fast estimation of graph isoperimetry
• BV Minimizers of the area functional in the Heisenberg group under the bounded slope condition
• The strong geometric lemma for intrinsic Lipschitz graphs in Heisenberg groups
• The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √(log n)