ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY
ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY
复制标题
通过 CHEEGER 不等式实现经济复曲面
DOI：
10.1142/s1793525309000096
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
B. Klartag
中科院分区：
文献类型：
--
作者：
N. Alon;B. Klartag
设图的顶点集为{0，.，m- 1}d，其中两个不同的顶点相邻当且仅当它们在m-圈Cm中的每个坐标上相等或相邻。设在同一顶点集上的图，其中两个顶点相邻当且仅当它们在Cm中的一个坐标上相邻，并且在所有其他坐标上相等。这两个图都可以看作是d维环面的图。我们证明了可以删除顶点G1，使没有拓扑非平凡的循环。这改进了Bollobas，Kindler，Leader和奥唐纳的O（dlog 2（3/2）md - 1）估计。我们还给出了一个简短的证明，结果隐含在最近的文件Raz：一个可以删除一小部分的G∞的边缘，使没有拓扑非平凡的周期留在这个图。我们的技术也产生了一个简短的证明最近的结果金德勒，奥唐纳，饶和Wigderson;有一个子集的连续d维环面的表面积相交的所有非平凡的周期。所有的证明都是基于相同的一般思想：考虑一个小的边界和没有非平凡的循环，其存在性是证明应用等周不等式的Cheeger或其顶点或边缘离散类似的机构的随机移位。
Let denote the graph whose set of vertices is {0,…,m - 1}d, where two distinct vertices are adjacent if and only if they are either equal or adjacent in the m-cycle Cm in each coordinate. Let denote the graph on the same set of vertices in which two vertices are adjacent if and only if they are adjacent in one coordinate in Cm and equal in all others. Both graphs can be viewed as graphs of the d-dimensional torus. We prove that one can delete vertices of G1 so that no topologically nontrivial cycles remain. This improves an O(dlog2 (3/2)md - 1) estimate of Bollobas, Kindler, Leader and O'Donnell. We also give a short proof of a result implicit in a recent paper of Raz: one can delete an fraction of the edges of G∞ so that no topologically nontrivial cycles remain in this graph. Our technique also yields a short proof of a recent result of Kindler, O'Donnell, Rao and Wigderson; there is a subset of the continuous d-dimensional torus of surface area that intersects all nontrivial cycles. All proofs are based on the same general idea: the consideration of random shifts of a body with small boundary and no nontrivial cycles, whose existence is proved by applying the isoperimetric inequality of Cheeger or its vertex or edge discrete analogues.