An interlacing technique for spectra of random walks and its application to finite percolation clusters

Florian Sobieczky

Published 2005-04-25, updated 2008-03-29Version 4

A comparison technique for finite random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be stationary with respect to some transitive subgroup of the automorphism group (`invariant percolation'). Given that this subgroup is unimodular, it is shown that stationarity strengthens the upper bound of the expected return probability, compared with standard bounds derived from the Cheeger inequality.