×

Economical toric spines via Cheeger’s inequality. (English) Zbl 1185.05085

Summary: Let \(G_\infty=(C^d_m)_\infty\) denote the graph whose set of vertices is \(\{0,\dots,m-1\}^d\), where two distinct vertices are adjacent if and only if they are either equal or adjacent in the \(m\)-cycle \(C_m\) in each coordinate. Let \(G_1=(C^d_m)_1\) denote the graph on the same set of vertices in which two vertices are adjacent if and only if 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.

MSC:

05C38 Paths and cycles
05C10 Planar graphs; geometric and topological aspects of graph theory

References:

[1] DOI: 10.1007/BF02579166 · Zbl 0661.05053 · doi:10.1007/BF02579166
[2] T. H. Cormen, Introduction to Algorithms, 2nd edn. (MIT Press and McGraw-Hill, 2001) pp. 643–700.
[3] Schoen R., Lectures on Differential Geometry (1994) · Zbl 0830.53001
[4] DOI: 10.1007/s00493-004-0031-x · Zbl 1058.05033 · doi:10.1007/s00493-004-0031-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.