### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 101-111 |

Number of pages | 11 |

Journal | Journal of Topology and Analysis |

Volume | 1 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1 2009 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Analysis
- Geometry and Topology

### Keywords

- Cheeger's inequality
- parallel repetition
- torus

## Fingerprint Dive into the research topics of 'Economical toric spines via Cheeger's inequality'. Together they form a unique fingerprint.

## Cite this

*Journal of Topology and Analysis*,

*1*(2), 101-111. https://doi.org/10.1142/S1793525309000096