TY - JOUR
T1 - Vertical perimeter versus horizontal perimeter
AU - Naor, Assaf
AU - Young, Robert
N1 - Funding Information:
Acknowledgments. A.N. was supported by BSF grant 2010021, the Packard Foundation and the Simons Foundation. R.Y. was supported by NSF grant 1612061, the Sloan Foundation, and the Fall 2016 program on Geometric Group Theory at the Mathematical Sciences Research Institute. The research that is presented here was conducted under the auspices of the Simons Algorithms and Geometry (A&G) Think Tank.
Publisher Copyright:
© 2018 Department of Mathematics, Princeton University.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - Given k ∈ N, the k'th discrete Heisenberg group, denoted Hℤ2k+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 Hℤ2k+1.) Denote b[cyrillic]k = [a1, b1, a1-1, b1-1, . . ., ak, bk, ak-1, bk-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 ∂vtΩ to be the set of all those pairs (x, y) ∈ Ω × (Hℤ2k+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] ⊆ 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 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 Hℤ5 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.
AB - Given k ∈ N, the k'th discrete Heisenberg group, denoted Hℤ2k+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 Hℤ2k+1.) Denote b[cyrillic]k = [a1, b1, a1-1, b1-1, . . ., ak, bk, ak-1, bk-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 ∂vtΩ to be the set of all those pairs (x, y) ∈ Ω × (Hℤ2k+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] ⊆ 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 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 Hℤ5 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.
KW - Approximation algorithms
KW - Heisenberg group
KW - Isoperimetric inequalities
KW - Metric embeddings
KW - Metrics of negative type
KW - Semidefinite programming
KW - Sparsest Cut Problem
UR - http://www.scopus.com/inward/record.url?scp=85048631868&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048631868&partnerID=8YFLogxK
U2 - 10.4007/annals.2018.188.1.4
DO - 10.4007/annals.2018.188.1.4
M3 - Article
AN - SCOPUS:85048631868
SN - 0003-486X
VL - 188
SP - 171
EP - 279
JO - Annals of Mathematics
JF - Annals of Mathematics
IS - 1
ER -