Anchored expansion and random walk |
| |
Authors: | B Virág |
| |
Institution: | (1) Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA, e-mail: balint@math.mit.edu, US |
| |
Abstract: | This paper studies anchored expansion, a non-uniform version of the strong isoperimetric inequality. We show that every graph
with i-anchored expansion contains a subgraph with isoperimetric (Cheeger) constant at least i. We prove a conjecture by Benjamini, Lyons and Schramm (1999) that in such graphs the random walk escapes with a positive
lim inf speed. We also show that anchored expansion implies a heat-kernel decay bound of order exp(—cn
1/3).
Submitted: September 1999, Revision: January 2000. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|