The Brunn-Minkowski inequality and nontrivial cycles in the discrete torus

Noga Alon, Ohad N. Feldheim

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Let (Cmd) denote the graph whose set of vertices is Zmd in which two distinct vertices are adjacent iff in each coordinate either they are equal or they differ, modulo m, by at most 1. Bollobás, Kindler, Leader, and O'Donnell proved that the minimum possible cardinality of a set of vertices of (Cm d) whose deletion destroys all topologically nontrivial cycles is md - (m - 1)d. We present a short proof of this result, using the Brunn-Minkowski inequality, and also show that the bound can be achieved only by selecting a value xi in each coordinate i, 1 ≤ i ≤ d, and by keeping only the vertices whose ith coordinate is not xi for all i.

Original languageEnglish (US)
Pages (from-to)892-894
Number of pages3
JournalSIAM Journal on Discrete Mathematics
Volume24
Issue number3
DOIs
StatePublished - 2010
Externally publishedYes

Keywords

  • Brunn-Minkowski inequality
  • Discrete torus
  • Nontrivial cycles

Fingerprint

Dive into the research topics of 'The Brunn-Minkowski inequality and nontrivial cycles in the discrete torus'. Together they form a unique fingerprint.

Cite this