Eliminating Cycles in the Discrete Torus.

In this paper we consider the following question: how many vertices of the discrete torus must be deleted so that no topologically nontrivial cycles remain? We look at two different edge structures for the discrete torus. For , where two vertices in are connected if their ℓ1 distance is 1, we show a nontrivial upper bound of on the number of vertices that must be deleted. For , where two vertices are connected if their ℓ∞ distance is 1, Saks, Samorodnitsky and Zosin [8] already gave a nearly tight lower bound of using arguments involving linear algebra. We give a more elementary proof which improves the bound to , which is precisely tight. [ABSTRACT FROM AUTHOR]