TY - JOUR

T1 - Economical toric spines via Cheeger's inequality

AU - Alon, Noga

AU - Klartag, Bo'Az

N1 - Funding Information:
Noga Alon was supported in part by an ERC Advanced grant, a USA-Israeli BSF grant, the Israel Science Foundation and the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Bo’az Klartag was supported in part by the Israel Science Foundation and a Marie Curie Reintegration Grant from the Commission of the European Communities.

PY - 2009/6

Y1 - 2009/6

N2 - Let G ∞=(C m d)∞ 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 C m in each coordinate. Let G ∞=(C m d)∞ 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 C m and equal in all others. Both graphs can be viewed as graphs of the d-dimensional torus. We prove that one can delete O(√dm d-1) vertices of G 1 so that no topologically nontrivial cycles remain. This improves an O(d log 2 (3/2)m d-1) estimate of Bollobás, 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 O(√d/m) 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 O(√d) 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.

AB - Let G ∞=(C m d)∞ 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 C m in each coordinate. Let G ∞=(C m d)∞ 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 C m and equal in all others. Both graphs can be viewed as graphs of the d-dimensional torus. We prove that one can delete O(√dm d-1) vertices of G 1 so that no topologically nontrivial cycles remain. This improves an O(d log 2 (3/2)m d-1) estimate of Bollobás, 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 O(√d/m) 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 O(√d) 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.

KW - Cheeger's inequality

KW - parallel repetition

KW - torus

UR - http://www.scopus.com/inward/record.url?scp=77955239307&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955239307&partnerID=8YFLogxK

U2 - 10.1142/S1793525309000096

DO - 10.1142/S1793525309000096

M3 - Article

AN - SCOPUS:77955239307

VL - 1

SP - 101

EP - 111

JO - Journal of Topology and Analysis

JF - Journal of Topology and Analysis

SN - 1793-5253

IS - 2

ER -