Vertical perimeter versus horizontal perimeter

• 成果类型: Article
• 署名作者: Naor, Assaf; Young, Robert
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2018.188.1.4
• 发表日期: 2018
• 页码: 171-279
• 关键词: finite metric-spaces; poincare inequalities; quantitative nonembeddability; markov convexity; heisenberg-group; banach-spaces; l-p; EMBEDDINGS; distortion; approximation

摘要

Given k epsilon N, the k'th discrete Heisenberg group, denoted H-z(2k+1), is the group generated by the elements a(1), b(1),..., a(k), b(k), c, subject to the commutator relations [a(1), b(1)] = ... = [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 epsilon {1,..., k}, we have [a(i), a(j)] = [b(i), b(j)] = [a(i),b(j)] = [a(i), c] = [b(i), c] = 1. (In particular, this implies that c is in the center of H-z(2k+1).) Denote (sic)(k) ={a(1), b(1), a(1)(-1), b(1)(-1),...,a(k), b(k), a(k)(-1), b(k)(-1)}. The horizontal boundary of Omega subset of H-z(2k+1), denoted partial derivative(h)Omega, is the set of all those pairs (x, y) epsilon Omega x (H-z(2k+1) \ Omega) such that x(-1) y epsilon (sic)(k). The horizontal perimeter of Omega is the cardinality vertical bar partial derivative(h)Omega vertical bar of partial derivative(h)Omega; i.e., it is the total number of edges incident to Omega in the Cayley graph induced by (sic)(k). For t epsilon N, define partial derivative(t)(v)Omega to be the set of all those pairs (x, y) epsilon Omega x (H-z(2k+1) \ Omega) such that x(-1) y epsilon {c(t), c(-t)}. Thus, vertical bar partial derivative(t)(v)Omega vertical bar is the total number of edges incident to Omega in the (disconnected) Cayley graph induced by {c(t), c(-t)} subset of H-z(2k+1). The vertical perimeter of Omega is defined by vertical bar partial derivative(v)Omega vertical bar= root Sigma(infinity)(t=1)vertical bar partial derivative(t)(v)Omega vertical bar(2)/t(2). It is shown here that if k >= 2, then vertical bar partial derivative(v)Omega vertical bar less than or similar to 1/k vertical bar partial derivative(h)Omega vertical bar. The proof of this vertical versus horizontal isoperimetric inequality uses a new structural result that decomposes sets of finite perimeter in the Heisenberg group into pieces that admit an intrinsic corona decomposition. This allows one to deduce an endpoint W-1,W-1 -> L-2(L-1) boundedness of a certain singular integral operator from a corresponding lower-dimensional W-1,W-2 -> L-2(L-2) boundedness. Apart from its intrinsic geometric interest, the above (sharp) isoperimetric-type inequality has several (sharp) applications, including that for every n epsilon N, any embedding into an L-1(mu) space of a ball of radius n in the word metric on H-z(5) that is induced by the generating set (sic)(2) incurs bi-Lipschitz distortion that is at least a universal constant multiple of root log n. As an application to approximation algorithms, it follows that for every n epsilon N, the integrality 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 root log n.