Vertical perimeter versus horizontal perimeter

Assaf Naor

doi:10.4007/annals.2018.188.1.4

Vertical perimeter versus horizontal perimeter

2018-07-01

33

OA

AI

DOI：10.4007/annals.2018.188.1.4

原文链接

原文求助

摘要

En 中文

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.

Keyword:

Heisenberg group

isoperimetric inequalities

metric embeddings

Sparsest Cut Problem

approximation algorithms

semidefinite programming

metrics of negative type

Vertical perimeter versus horizontal perimeter

摘要

期刊

机构

引用论文