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

Abstract

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.

The improvements over the last version include: New results on critical percolation (2-D Bernoulli-Bond percolation and binary tree); proof of Theorem 1.11 (formerly Theorem 1.8) and Lemma 3.1 revised for greater rigor and readability

References in corpus (6)

• Random walks on supercritical percolation clusters
• Spectral computations on lamplighter groups and Diestel-Leader graphs
• Spectral properties of the Laplacian on bond-percolation graphs
• Sharpness of the phase transition and exponential decay of the subcritical cluster size for percolation on quasi-transitive graphs
• Uniform existence of the integrated density of states for models on $\ZZ^d$
• Anchored expansion, percolation and speed

Cited by in corpus (1)

• Bounds for the annealed return probability on large finite percolation clusters