EVERY GRAPH WITH A POSITIVE CHEEGER CONSTANT CONTAINS A TREE WITH A POSITIVE CHEEGER CONSTANT

Authors
BENJAMINI I SCHRAMM O
Citation
I. Benjamini et O. Schramm, EVERY GRAPH WITH A POSITIVE CHEEGER CONSTANT CONTAINS A TREE WITH A POSITIVE CHEEGER CONSTANT, Geometric and functional analysis, 7(3), 1997, pp. 403-419
Citations number
14
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Geometric and functional analysis → ACNP
ISSN journal
1016443X
Volume
7
Issue
3
Year of publication
1997
Pages
403 - 419
Database
ISI
SICI code
1016-443X(1997)7:3<403:EGWAPC>2.0.ZU;2-M
Abstract
It is shown that every (infinite) graph with a positive Cheeger consta nt contains a tree with a positive Cheeger constant. Moreover, for eve ry nonnegative integer k there is a unique connected graph T(k) that h as Cheeger constant k, but removing any edge from it reduces the Cheeg er constant. This minimal graph, T(k), is a tree, and every graph G wi th Cheeger constant h(G) greater than or equal to k has a spanning for est in which each component is isomorphic to T(k).