## Abstract

Let (C_{m}^{d})_{∞} denote the graph whose set of vertices is Z_{m}^{d} 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 (C_{m} ^{d})_{∞} whose deletion destroys all topologically nontrivial cycles is m^{d} - (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 x_{i} in each coordinate i, 1 ≤ i ≤ d, and by keeping only the vertices whose ith coordinate is not x_{i} for all i.

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

Pages (from-to) | 892-894 |

Number of pages | 3 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 24 |

Issue number | 3 |

DOIs | |

State | Published - 2010 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Keywords

- Brunn-Minkowski inequality
- Discrete torus
- Nontrivial cycles