Eliminating cycles in the torus via isoperimetric inequalities


Let $G_{\infty}=(C_m^d)_{\infty}$ denote the graph whose set of vertices
is $\{1,\ldots ,m\}^d$, where two distinct vertices are adjacent iff
they are either equal or adjacent in $C_m$ in each coordinate. Let
$G_{1}=(C_m^d)_1$ denote the graph on the same set of vertices in which
two vertices are adjacent iff 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(\sqrt d m^{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\'as,
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(\sqrt d/m)$ 
fraction of the edges of $G_{\infty}$ so that no topologically nontrivial 
cycles remain in this graph. The 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(\sqrt 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.

Joint work with Bo'az Klartag.