# Vertical perimeter versus horizontal perimeter

Assaf Naor, Robert Young

Research output: Contribution to journalArticlepeer-review

## Abstract

Given k ∈ N, the k'th discrete Heisenberg group, denoted H2k+1, is the group generated by the elements a1, b1, . ., ak, bk, c, subject to the commutator relations [a1, b1] = · · · = [ak, bk] = c, while all the other pairs of elements from this generating set are required to commute, i.e., for every distinct i, j ∈ [1, . . . . k], we have [ai, aj] = [bi, bj ] = [ai, bj] = [ai, c] = [bi, c] = 1. (In particular, this implies that c is in the center of H2k+1.) Denote b[cyrillic]k = [a1, b1, a1-1, b1-1, . . ., ak, bk, ak-1, bk-1]. The hori- zontal boundary of Ω ⊆ H2k+1, denoted ∂hΩ, is the set of all those pairs (x, y) ∈ Ω ×(H2k+1\Ω) such that x-1y ∈ b[cyrillic]k. The horizontal perimeter of Ω is the cardinality |∂hΩ| of ∂hΩ; i.e., it is the total number of edges incident to Ω in the Cayley graph induced by b[cyrillic]k. For t ∈ N, define ∂vtΩ to be the set of all those pairs (x, y) ∈ Ω × (H2k+1\Ω) such that x-1y ∈ [ct, c-t]. Thus, |∂vtΩ| is the total number of edges incident to Ω in the (disconnected) Cayley graph induced by [ct, c-t] ⊆ H2k+1. The vertical perimeter of Ω is defined by |∂vjΩ|. It is shown here that if k ≥ 2, then |∂vΩ|≲ |∂vΩ| The proof of this \vertical versus horizontal isoperi- metric inequality" uses a new structural result that decomposes sets of finite perimeter in the Heisenberg group into pieces that admit an \in- trinsic corona decomposition. "This allows one to deduce an endpoint W1,2 → L2(L1) boundedness of a certain singular integral operator from a corresponding lower-dimensional W1,2 → L2(L2) boundedness. Apart from its intrinsic geometric interest, the above (sharp) isoperimetric-type inequality has several (sharp) applications, including that for every n ∈ N, any embedding into an L1(μ) space of a ball of radius n in the word metric on H5 that is induced by the generating set b[cyrillic]2 incurs bi-Lipschitz distortion that is at least a universal constant multiple of √ log n. As an application to approximation algorithms, it follows that for every n ∈ ℕ, the integral- ity gap of the Goemans-Linial semidefinite program for the Sparsest Cut Problem on inputs of size n is at least a universal constant multiple of √ log n.

Original language English (US) 171-279 109 Annals of Mathematics 188 1 https://doi.org/10.4007/annals.2018.188.1.4 Published - Jul 1 2018

## Keywords

• Approximation algorithms
• Heisenberg group
• Isoperimetric inequalities
• Metric embeddings
• Metrics of negative type
• Semidefinite programming
• Sparsest Cut Problem

## ASJC Scopus subject areas

• Statistics and Probability
• Statistics, Probability and Uncertainty

## Fingerprint

Dive into the research topics of 'Vertical perimeter versus horizontal perimeter'. Together they form a unique fingerprint.