λ∞, Vertex isoperimetry and concentration

S. Bobkov, C. Houdré, P. Tetali

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

Cheeger-type inequalities are derived relating various vertex isoperimetric constants to a Poincaré-type functional constant, denoted by λ∞. This approach refines results relating the spectral gap of a graph to the so-called magnification of a graph. A concentration result involving λ∞ is also derived.

Original languageEnglish (US)
Pages (from-to)153-172
Number of pages20
JournalCombinatorica
Volume20
Issue number2
DOIs
StatePublished - 2000

Bibliographical note

Funding Information:
* Research supported in part by th e Russian Foundation for Fundamental Research , Grant No. 96-01-00201. † Th is auth or greatly enjoyed th e h ospitality of CIMAT, Gto, Mexico wh ile part of th is work was carried out; research supported in part by NSF Grant No. 9803239. ‡ Research supported in part by NSF Grant No. DMS–9800351.

Fingerprint Dive into the research topics of 'λ∞, Vertex isoperimetry and concentration'. Together they form a unique fingerprint.

Cite this