Economical elimination of cycles in the torus

Research output: Contribution to journalArticle

Abstract

Let m > 2 be an integer, let C2m denote the cycle of length 2m on the set of vertices [m, m) = {m, m + 1,⋯, m 2, m 1}, and let G = G(m, d) denote the graph on the set of vertices [m, m)d, in which two vertices are adjacent if and only if they are adjacent in C2m in one coordinate, and equal in all others. This graph can be viewed as the graph of the d-dimensional torus. We prove that one can delete a füraction of at most O (log d/m)$ of the vertices of G so that no topologically non-trivial cycles remain. This is tight up to the logd factor and improves earlier estimates by various researchers.

Original languageEnglish (US)
Pages (from-to)619-627
Number of pages9
JournalCombinatorics Probability and Computing
Volume18
Issue number5
DOIs
StatePublished - Sep 1 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Economical elimination of cycles in the torus'. Together they form a unique fingerprint.

  • Cite this