Vertical perimeter versus horizontal perimeter

Given k ∈ N, the k'th discrete Heisenberg group, denoted H_ℤ^2k+1, is the group generated by the elements a₁, b₁, . ., a_k, b_k, c, subject to the commutator relations [a1, b1] = · · · = [a_k, b_k] = 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 [a_i, a_j] = [b_i, bj ] = [a_i, b_j] = [a_i, c] = [b_i, c] = 1. (In particular, this implies that c is in the center of H_ℤ^2k+1.) Denote b[cyrillic]_k = [a₁, b₁, a₁^-1, b₁^-1, . . ., a_k, b_k, a_k^-1, b_k^-1]. The hori- zontal boundary of Ω ⊆ H_ℤ^2k+1, denoted ∂_hΩ, is the set of all those pairs (x, y) ∈ Ω ×(H_ℤ^2k+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 ∂_v^tΩ to be the set of all those pairs (x, y) ∈ Ω × (H_ℤ^2k+1\Ω) such that x^-1y ∈ [c^t, c^-t]. Thus, |∂_v^tΩ| is the total number of edges incident to Ω in the (disconnected) Cayley graph induced by [c^t, c^-t] ⊆ H_ℤ^2k+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 W^1,2 → L₂(L₁) boundedness of a certain singular integral operator from a corresponding lower-dimensional W^1,2 → L₂(L₂) 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 L₁(μ) space of a ball of radius n in the word metric on H_ℤ⁵ that is induced by the generating set b[cyrillic]₂ 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.