An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters |
| |
Authors: | Florian Sobieczky |
| |
Institution: | 1.Institut für Mathematik C,TU-Graz,Graz,Austria;2.Mathematisches Institut,FSU-Jena,Jena,Germany |
| |
Abstract: | A comparison technique for 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 invariant with respect
to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it
is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds
such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive
graph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|