Research Interests: Florian Sobieczky

Florian Sobieczky

Random Walks on Random Partial Graphs

This is the programme of the research project P18703 of the Austrian science fund (FWF - `Fonds fuer Wissenschaftliche Forschung').

Many properties of percolation on a transitive graph of bounded geometry are accessible if the graph is a Cayley graph of an amenable group. Examples include the number of open clusters per vertex [1][5] and the annealed n-step return probability of a random walk of nearest neighbour type on percolative partial graphs, following methods for the deterministic case [12]. The amenability enables the use of the ergodic theorem [7].

A much larger class of transitive graphs is given by those with a transitive, unimodular (subgroup of the) automorphism group, to which the Cayley graphs of amenable groups belong [9]. The mass-transport-principle [1][3] enables the calculation of averages in a way reminiscent of the ergodic theorem. For these unimodular graphs, we study estimates of the expected return probability of random walks on the finite components of invariant percolations [11]. The methods used involve interlacing techniques, which are similar to results in graph theoretical works [6][4]. They lead to comparison theorems between different finite random walks, which do not assume any special geometrical properties, as in the case of classical results of Poincare or Cheeger-Buser-type (see [10]). In particular, comparison of eigenvalues away from the spectral edge (i.e. from the `bulk-spectrum') are used.

1.) Return Probabilities of Random Walks on random Subgraphs

My present research concentrates on the extension of the results to (a) the percolations including infinite clusters, and, (b) invariant percolations on non-unimodular, transitive graphs. The difficulties involved in these generalisations are for (a) that the cluster size ceases to be a valid quantity characterizing the return probability, and for (b) that the mass transport principle may not be used in its simplest form. For both extensions, an approach initially reserved for the amenable groups and their Cayley graphs (with 'Foelner-sets') allows the use of interlacing techniques. In addition to assumptions about the graph carrying the percolation, additional assumptions about the law of the percolation may allow a further improvement, such as in [11], for exponentially decaying cluster-size distributions. Similarly, extensions (a) and (b), may require the percolation models to have special properties with respect to the geometries of their realizations (e.g. isoperimetry [8]).

2.) Speed of random walks on random partial graphs

B. Virag [12] has shown that positivity of the anchored isoperimetric constant implies positivity of the simple random walk's speed on any infinite connected graph. We study anchored expansion on horocyclic products of percolative subgraphs of homogeneous trees with respect to the question of a phase transition, i.e. the question of the possibility of a critical retention parameter in the open interval (0,1) at which the speed becomes positive is posed.

For a detailed description of my research project (FWF-P18703), see the project report .

I am currently applying for a research grant with the Austrian Science foundation. See here for the corresponding proposal.

Home

References quoted:

1.: M.Aizenman, H.Kesten, C.M.Newman: 'Uniqeness of the Infinite Cluster and Continuity of Connectivity Functions for Short and Long Range Percolation', Commun.Math:Phys. 111, 505-531 (1987)

2.: D. Aldous, R. Lyons: `Processes on unimodular random networks', to be published

3.: I. Benjamini, R. Lyons, Y. Peres, O. Schramm): `Group-invariant percolation on graphs', Geom. Funct. Anal. 9 (1999), 29--66.

4.: B. Bollob\'as, , V. Nikiforov: `Graphs and Hermitian matrices: eigenvalue interlacing', Discrete Math. 289 (2004), no. 1-3, 119--127.

5.: G.R.Grimmet: `On the number of clusters in the percolation model', J.London Math.Soc. (2), 13 (1976), 346-350

6.: W.H. Haemers: `Interlacing eigenvalues and graphs', Lin. Alg. App. 226/228, 593

7.: Lindenstrauss, Elon: 'Pointwise theorems for amenable groups', Invent. Math. 146 (2001), no. 2, 259--295.

8.: P.Mathieu, E. Remy: `Isoperimetry and heat kernel decay on percolation clusters', Annals of Probability, 32 1A, pp 100-128, 2004

9.: P.M. Soardi, W.Woess: `Amenability, unimodularity, and the spectral radius of random walks on infinite graphs', Math. Z. 205, 1990, 471-486

10: L.Saloff-Coste: `Lectures on finite Markov Chains', Saint-Flour, LNM 1665

11: F. Sobieczky: `Random Walks on the finite Components of random Partial Graphs of Transitive Graphs', (preprint) math.PR/0504518

12: B. Virag: `Anchored expansion and the speed of simple random walk', GAFA, 2000

13: W.Woess: `Random Walks on Infinite Graphs and Groups', Cambridge Tracts in Mathematics 138, Camb. Univ. Press, 2000, Prop. 15.4