Economical toric spines via Cheeger's Inequality
| dc.creator | Alon, Noga | |
| dc.creator | Klartag, Bo'az | |
| dc.date | 2008-09-18 | |
| dc.date.accessioned | 2026-07-07T10:03:46Z | |
| dc.date.available | 2026-07-07T10:03:46Z | |
| dc.description | Let $G_{\infty}=(C_m^d)_{\infty}$ denote the graph whose set of vertices is $\{1,..., 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ás, 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. Our 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. | |
| dc.identifier | https://arxiv.org/abs/0809.3169 | |
| dc.identifier | http://arxiv.org/abs/0809.3169 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/169411 | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.title | Economical toric spines via Cheeger's Inequality | |
| dc.type | text |