Random walks on random subgraphs of transitive graphs

Random walks on percolative graphs on the Euclidean lattice has been subject of intensive study during recent years: the return probability of the simple random walk on the supercritical, giant percolation cluster has been investigated by Benjamini and Mossel [10], Heicklen and Hoffmann [28], Mathieu and Remy [39], Barlow[5] and Fontes and Mathieu [19]. Usually the assumptions concern Bernoulli percolation and the continuous time simple random walk. There has been intensive discussion going on, while the properties of the infinite supercritical component, such as isoperimetry [39] and growth [5], have played an important role. Without mentioning random walks, the topic of generalizing results from percolation theory on the Euclidean lattice to general transitive graphs has been going on somewhat earlier (see Lyons [38] for a discussion of the then open problems), when an old concept initially rediscovered by Häggström [23] as the `mass-transport-principle had been found in [8] to be a general recipe to calculate expected values of arithmetic means, similar to the ones appearing in the ergodic theorem in the less general case of (Cayley graphs of) amenable groups [36]. A key assumption for this principle to be of equal use is the condition of the unimodularity of the transitive `host graph` of the percolation process - equally for bond- and site percolation, without restriction to the Bernoulli (independent) case, i.e. for all automorphism invariant percolations: the automorphism group must contain a unimodular transitive subgroup. Finally, as a suggestion to answer the question of the existence of a (vertex-)transitive graph which is not quasi- isometric to some Cayley graph of a finitely-generated group posed by Woess in the early nineties, the Diestel- Leader graphs were (and still are today: [C] ) investigated: they contain a subclass of amenable, and therefore unimodular graphs - the Cayley graphs of the lamplighter groups, while the majority of them is not unimodular. A result linking these three domains of questions together is given by a result on Random Walks of Bartholdi and Woess [7], part of which had been found by Revelle, before: The asymptotic form of the return probability on the unimodular and non-unimodular DL-graphs differ by a characterstic prefactor, differing between each other by a factor of n (discrete time). Our motivation is, by the examination of the asymptotic return probabilities of random walks to find changes in some type (e.g. amenability), i.e. phase transitions, of percolative partial graphs `interpolating` between different types of transitive graphs at the ends of the intervall of the retention probability. To this end, ou first effort belongs to bounding the return probability.

Goals of the Project: The purpose of the project was to find estimates of the expected return probability (equivalently the heat kernel, or the integrated density of states) of random walks on graphs by an eigenvalue comparison technique called `interlacing`. Instead of restricting the study to the Euclidean lattice, invariant percolation on transitive graphs with a unimodular transitive subgroup of the automorphism group was in the focus. A. The main task is to obtain and improve upper and lower bounds for the return probability of random walks on graphs using comparison techniques (e.g. interlacing). B. The most obvious application of the results of A. is to percolation subgraphs, in particular with measure that have heavy-tailed cluster-size distributions (e.g. critical percolation). Here, the expected return probability (or, equivalently, the integrated density of states) is the object of interest. C. A quality of graphs, which intimately belonds to the random walks circle of problems is the question of amenability. For a random family of exponentially growing graphs called horocyclic products, it is of interest to understand the transition between (almost sure) amenability and non-amenability. Results achieved: 1.): `An interlacing technique for spectra of random walks and its application to finite percolation clusters`; accepted for publication by: Journal of Theoretical Probability, arXiv:math/0504518v4, (2008) (A. / B.) 2.): `Bounds for the annealed return probability on large finite random percolation clusters`; submitted to `Mathematische Zeitschrift`, arXiv:0812.0117v4, (2010) (A. / B.) 3.): `Amenability of horocyclic products of percolation trees`; submitted to Markov Processes and Related Fields, arXiv:0903.3140v2, (2008) (C.) 4.) (with V. Kaimanovich) `Stochastic homogenization of horospheric tree products`: Proc. of the 1st MSJ-SI, "Probabilitstic Approach to Geometry", arXiv:0906.5296v1 (2009) (C.) 5.) F. Sobieczky, G. Rappitsch, E. Stadlober: `Inventories modelled by stable tandemqueues under perturbation`, submitted by invitation to QREI special issue (Quality and Reliability Engineering International), (2010) (A.) Furthermore, a proceedings-volume about the `Alp-workshop 2009` held in Styria will appear in the fall of 2010 in the Birkhaeuser-series `Progress in Probability`. Ongoing work is with Steven Lalley (A.) , Tatyana Turova (A,), Daniel Lenz and Ivan Veselic (C.), and with V. Kaimanovich (C.).