Vertical perimeter versus horizontal perimeter
Vertical perimeter versus horizontal perimeter
复制标题
DOI：
10.4007/annals.2018.188.1.4
复制
发表时间：
2018-06-01
影响因子：
4.9
通讯作者：
Young, Robert
中科院分区：
文献类型：
--
作者：
Naor, Assaf;Young, Robert
给定 k epsilon N，第 k 个离散海森堡群，表示为 H-z(2k+1)，是由元素 a(1), b(1),..., a(k), b(k), c 生成的群，服从交换子关系 [a(1), b(1)] = ... = [a(k), b(k)] = c，而该生成集中的所有其他元素对都是必需的 交换，即，对于每个不同的 i, j epsilon {1,..., k}，我们有 [a(i), a(j)] = [b(i), b(j)] = [a(i),b(j)] = [a(i), c] = [b(i), c] = 1。（特别是，这意味着 c 位于 H-z(2k+1) 的中心。） （原文如此）（k）= {a（1），b（1），a（1）（-1），b（1）（-1），...，a（k），b（k），a（k）（-1），b（k）（-1）}。 H-z(2k+1) 的 Omega 子集的水平边界，表示为偏导数(h)Omega，是所有这些对 (x, y) epsilon Omega x (H-z(2k+1) \ Omega) 的集合，使得 x(-1) y epsilon (sic)(k)。 Omega 的水平周长是基数竖条偏导数(h)Omega 偏导数(h)Omega 的竖条；即，它是由 (sic)(k) 引起的凯莱图中与 Omega 相关的边总数。对于 t epsilon N，将偏导数 (t)(v)Omega 定义为所有这些对 (x, y) epsilon Omega x (H-z(2k+1) \ Omega) 的集合，使得 x(-1) y epsilon {c(t), c(-t)}。因此，竖条偏导数(t)(v)Omega竖条是由H-z(2k+1)的子集{c(t),c(-t)}引起的（断开的）凯莱图中与Omega相关的边的总数。 Omega 的垂直周长由竖条偏导数 (v)Omega 竖条=根 Sigma(无穷大)(t=1)竖条偏导数(t)(v)Omega 竖条(2)/t(2) 定义。此处显示，如果 k >= 2，则垂直条偏导数 (v)Omega 垂直条小于或类似于 1/k 垂直条偏导数 (h)Omega 垂直条。这种“垂直与水平等周不等式”的证明使用了一种新的结构结果，该结果将海森堡群中的有限周长组分解为允许“本征电晕分解”的片段。这允许人们从相应的低维 W-1,W-2 -> L-2(L-2) 有界性推导出某个奇异积分算子的端点 W-1,W-1 -> L-2(L-1) 有界性。除了其内在的几何兴趣之外，上述（尖锐）等周型不等式还有几个（尖锐）应用，包括对于每个 n epsilon N，由生成集 (sic)(2) 引起的 H-z(5) 上的字度量中半径为 n 的球的任何嵌入到 L-1(mu) 空间中都会导致双利普希茨畸变，该畸变至少是根对数的通用常数倍 名词作为近似算法的应用，对于每个 n epsilon N，针对大小为 n 的输入的稀疏割问题的 Goemans-Linial 半定程序的完整性差距至少是根 log n 的通用常数倍。
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.