Economical toric spines via Cheeger's Inequality

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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\'as, 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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Economical toric spines via Cheeger's Inequality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Economical toric spines via Cheeger's Inequality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Economical toric spines via Cheeger's Inequality will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-281684

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.