ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY

DOI10.1142/S1793525309000096zbMATH Open1185.05085arXiv0809.3169OpenAlexW2019374631MaRDI QIDQ3398972FDOQ3398972

Authors: Noga Alon, B. Klartag 

Publication date: 29 September 2009

Published in: Journal of Topology and Analysis (Search for Journal in Brave)

Abstract: Let $G_{infty}=(C_m^d{)}_{infty}$ denote the graph whose set of vertices is ${1,\mathrm{...},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(sqrtd{m}^{d-1})$ vertices of $G_1$ so that no topologically nontrivial cycles remain. This improves an $O(d^{lo{g}_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(sqrtd/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(sqrtd)$ 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.

Full work available at URL: https://arxiv.org/abs/0809.3169

Recommendations

• Economical elimination of cycles in the torus
• Eliminating Cycles in the Discrete Torus
• Eliminating cycles in the discrete torus
• The Brunn-Minkowski inequality and nontrivial cycles in the discrete torus
• A Simple Proof of the Karakhanyan–Riordan Theorem on the Even Discrete Torus

zbMATH Keywords

torusparallel repetitionCheeger's inequality

Mathematics Subject Classification ID

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

Cites Work

• Eigenvalues and expanders
• Title not available (Why is that?)
• A lower bound on the integrality gap for minimum multicut in directed networks

Cited In (7)

• Parallel repetition of two-prover one-round games: an exposition
• Economical elimination of cycles in the torus
• An integer parallelotope with small surface area
• Interactions of computational complexity theory and mathematics
• The Brunn-Minkowski inequality and nontrivial cycles in the discrete torus
• Eliminating Cycles in the Discrete Torus
• Spatio-spectral limiting on discrete tori: adjacency invariant spaces

This page was built for publication: ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3398972)