YEP (Young European Probabilists) 2005
Workshop on self-similar random structures
Hausdorff dimension and branching
EURANDOM, Eindhoven, The Netherlands
March 14-18, 2005

ABSTRACTS

Gidi Amir

1-Dimensional Diffusion Limited Aggregation
Joint work with O. Angel, I. Benjamini and G. Kozma

In a paper from 1981 Sanders and Whiten introduced the (2-Dim) DLA process --- a stochastic growth model, in which a "Discrete fractal" subset of $Z^2$ is grown from the origin in an inductive process, where in each step a particle, starting at "infinity" makes a simple random walk on $Z^2$ until it becomes a neighbor of the aggregate, then glues to it. The process turned out to be extremely difficult to analyze, and in spite of attracting a lot of attention, very little is known on the structure of the n-th step set or the limit set.

In this problem session we will define a family of 1-dimensional analogs of the standard DLA process - the 1-DLA process, which are more prone to analysis. The process is parameterized by an integer random variable $X$, which we will call the step distribution. The aggregates are subsets of $Z$ built inductively by starting with the set $A_0 = \{0\}$ and then at each step releasing a particle "near infinity" , letting it make a random walk with jump distribution $X$ until it hits $A_n$. If the particle first hits the set $A_n$ by making a jump from $x\not\in A_n$ to $a\in A_n$ then we set $A_{n+1} = A_n \cup \{x\}$. (precise definitions will be given). We will analyze this process for various choices of the step distribution, getting bounds for the growth of the diameter, and show a transient walk for whom the limit aggregate is the whole of $Z$ despite the diameter growing super exponentially. We will then discuss some open questions, an emphasis will be put on the limit aggregate and the "structure" of the aggregates, which seems to be necessary to produce better bounds.

Vincent Beffara

Critical percolation on a regular triangulation

We investigate possible generalizations of  Smirnov's proof for Cardy's formula (giving limit crossing probabilities for critical percolation on the triangular lattice) to other lattices, and show that under a (presumably) mild condition on the graph, namely a-priori estimates of the type RSW, crossing probabilities have the same scaling limit for a suitable choice of the embedding.

Julien Berestycki

Some self-similar structures in the fragmentation - coalescence context

Fragmentation and coalescence processes describe an object that falls appart as time runs or a system of masses which agregate and merge. Clearly these objects exhibit a strong genealogical structure -Kingman's coalescent was first introduced for modelling purposes in the field of population genetics- which explain the deep connection with ideas such as branching processes and random trees. Hence, it is not surprinsing that random self-similar objects naturally appear in this context. I will try to introduce several instances of fragmentations and coalescences which give rise to interesting random fractal strutures.

Noam Berger

Non-uniqueness for specifications in lp with p > 2
Joint work with Christopher Hoffman and Vladas Sidoravicius

Keane, Berbee and others have studied the question of which specifications (aka $g$-functions) admit a unique Gibbs measure. Bramson and Kalikow constructed the first example of a regular and continuous specification which admits multiple measures. For every $p>2$, we construct a regular and continuous specification, whose variation is in $\ell^p$, that admits multiple Gibbs measures. This shows that a recent condition of Oberg and Johansson is tight.

Jochen Blath

Two probably difficult but stimulating problems related to the long-term behaviour of branching particle systems

In a recent project carried out in collaboration with Alison Etheridge and Mark Meredith we proved that under certain conditions two competing systems of spatially interacting diffusions exhibit longterm coexistence with positive probability. As a spin-off result, using a duality relation, we also obtained a result about the persistence of certain branching annihilating random walks. But several interesting questions remain unsolved and lead to various conjectures.

The first conjecture I would like to present is that one should be able to obtain coexistence under much weaker conditions than we do. I would be especially interested in capturing an effect called 'heteromyopia' by population biologists. That would require much finer methods than the ones currently used by us (mainly comparison to discrete IPS), but might in return have considerable impact to the population biology community.

The second problem is related to the long-term behaviour of branching-annihilating random walk (BARW). Recently, physicists Cardy and T\"auber investigated BARW using perturbation theory and renormalisation group calculations, which suggest stronger dimension-dependent persistence results than the ones we are able to produce so far.

Any progress in one of the above directions would be very interesting, but it is also likely to be a challenging task.

Erik Broman

Dynamic Stability of Percolation for some Interacting Particle Systems and $\epsilon-$movability

Dynamical Percolation for i.i.d. systems was first introduced by Haggstrom, Peres and Steif (1997). This talk will briefly explain their model and then focus on some recent results obtained with J. Steif, in which the concept of Dynamical Percolation is developed for some Interacting Particle Systems. A central tool in this work is the concept of $\epsilon-$movability which we also discuss.

Christina Goldschmidt
Joint work with James Martin (CNRS and Paris 7)

Random recursive trees and the Bolthausen-Sznitman coalescent

The Bolthausen-Sznitman coalescent is a Markov process taking values in the set of partitions of the natural numbers. It is a very beautiful mathematical object, with some remarkable properties. In this talk, I will describe a new representation for the Bolthausen-Sznitman coalescent in terms of random recursive trees. I will use this representation to prove some results about the last collision of the coalescent restricted to {1,2,...,n}, as n tends to infinity. I will also consider the discrete-time Markov chain giving the number of blocks after each collsion of the coalescent restricted to {1,2,...,n}. I will show that the transition probabilities of the time-reversal of this Markov chain have limits as n tends to infinity, which I will make explicit.

Matthias Heveling

Lilypond systems
Joint work with Günter Last

The lilypond system based on a locally finite subset $\varphi$ of the Euclidean space $\R^n$ is defined as follows. At time $0$ every point of $\varphi$ starts growing with unit speed in all directions to form a system of balls in which any particular ball ceases its growth at the instant that it collides with another ball. It will be shown that this growth protocol always leads to a well defined and unique system of non-overlapping spheres. Surprisingly, this result can be generalized to the far more general setting, where $\varphi$ is a locally finite subset of some space $\X$ equipped with a pseudo-metric $d$. Several examples will illustrate our general results.

Wolfgang König

Ordered random walks and the corner-growth model

Ordered random walks, in special cases often called vicious walkers or non-colliding paths, are a system of finitely many independent one-dimensional random walks, conditioned on being in the same order for all times. The construction is in the sense of a Doob $h$-transformation. The well-known continuous counterpart is Dyson's Brownian motion, introduced in 1962 by F. Dyson as a dynamic model for the eigenvalues of random matrices.

The corner-growth model is a random growth model on the two-dimensional lattice that is equivalent to, resp. related to, a number of statistical mechanics models, like first and last passage directed percolation or directed polymers in a random environment. One starts with one particle at the origin, and after an individual independent waiting time, each site whose lower and left neighbour already belongs to the growing set is added. The question is after the long-time asymptotics of the growth of this two-dimensional set, including the fluctuations. Two particular waiting time distributions have been fully analysed by Johansson, and there is some recent progress by Baik and Suidan, but the general case is widely open.

Various results of the last couple of years suggest by analogy that there is a deeper connection between the two models, but the nature of this connection is unclear yet. In my talk I try to summarize the existing knowledge on the two models and the connections in special cases.

Russell Lyons

Random Walks, Tree Entropy, and Unimodularity

Recent investigations have uncovered important links among random walks (stationarity and return probabilities), enumerating spanning trees in graphs, and forms of the Mass-Transport Principle (fixed and random graphs). This mini-course will explain the basic ideas and proofs behind these connections. Several accessible open questions will be presented.

Gregory Miermont
Joint work with Jean-Francois Marckert, from the Universite de Versailles

An invariance principle for labeled branching mobiles, and its consequences on a class of random bipartite planar maps

A labeled mobile is a tree constituted of integer-labeled white vertices and black unlabeled vertices, so that two neighbors are of different colors. We show that a wide class of random mobiles, generated as a degenerate class of 2-type Galton-Watson trees, and coupled with spatial motion, converge to the so-called Brownian snake, i.e. a continuum random genealogy coupled with a Brownian spatial motion. Exploiting a bijection between labeled mobiles and planar maps due to Bouttier-di Francesco-Guitter, we deduce asymptotic results on the structure of a wide class of random planar maps.

Eulalia Nualart

Capacity, Hausdorff measure and hitting probabilites for stochastic partial differential equations
Joint work with R.C.Dalang.

In this talk we are interested in one of the basic poblems of potential theory for stochastic processes : when does a stochastic process hit a given set K with positive probability ? Probabilistic potential theory allows us to compute this probabilistic quantity in terms of analytic functions determined by the 'geometry' of the set, namely the capacity and Hausdorff measure of the set. We solve this problem for two systems of nonlinear stochastic partial differential equations, which are the nonlinear wave and heat equations perturbed by a space-time white noise. The main tool will be the use of the theory of Malliavin calculus.

Florian Sobieczky

Annealed Return Probability of a Random Walk on a stationary Random Partial Graph of the Cayley Graph of an amenable Group

For a finitely generated, amenable group the sub graph of its Cayley graph is considered, which results in removing edges at random. The process is required to be stationary ergodic with respect to the action of the group. Then, by the point wise ergodic theorem, the mean n-step return probability shows to obey estimates involving the number of open clusters per vertex and moments of the cluster size. The method proposed improves standard bounds by imposing less restrictive moment conditions at the same convergence rate.

In addition, as a problem open for discussion, I would like to address the problem of:

Extending the range of applicability of the method to non-amenable groups, in particular: effect of the existence of infinitely many connected components.

Jan Swart

Pathwise uniqueness for an SDE with non-Lipschitz coefficients

In Swart (2002), it is proved that pathwise uniqueness holds for the SDE $dX=sqrt{(1-|X|^2}dB -cXdt$ on the unit ball in $R^d$ with $d\geq 2$ if the constant $c$ satisfies $c=0$ or $c\geq 1$. These results have recently been improved in DeBlassie (2005), but the general case is still open. D. DeBlassie: Uniqueness for diffusions degenerating at the boundary of a smooth bounded set. To appear in Ann. Probab. J. M. Swart: Pathwise uniqueness for a SDE with non-Lipschitz coefficients Stochastic Processes Appl. 98 (2002) 131-149.

Elmar Teufl

Simple Random Walk on Fractal-like Graphs

In this problem session we discuss simple random walk on two classes of graphs, which exhibit interesting phenomena:

In the early 1980s physicists (R. Rammal, G. Toulouse and others) investigated random walks on the discrete analogon of the Sierpinski gasket. Since then several mathematicians created a theory of analysis and stochastic processes on self-similar structures. We introduce a special class self-similar graphs, which are especially capable for generating function techniques, and present some results about random walks on this class.

In 1995 E. Burioni and D. Cassi studied simple random walks on a fractal-like trees. These trees are defined recursively and are radial with respect to the root. We generalize this construction, which has a similarity to the blow-up construction of self-similar graphs, and discuss a result on return probabilities. We try point out similarities concerning results and methods for these two classes of graphs.

Percolation on non unimodular graphs

It is one of the central questions in percolation theory wether for any transitive graph there are infinite clusters for critical Bernoulli percolation. While the amenable case is unsolved for many basic examples (such as $Z^3$), the fact that there are no infinite clusters was proved for nonamenable unimodular graphs by Benjamini, Lyons, Peres and Schramm. The nonunimodular case remained open, since the so called Mass Transport Principle" is not really effective in this context. We show that there are no infinitely many infinite clusters at critical percolation for nonunimodular graphs. Other similarities and surprising differences compared to the unimodular case are also presented.

Benedek Valko

Random trees and general branching processes

We consider the following random tree model. We start with a single vertex and then in every step we connect a new vertex randomly to one of the old ones with probabilities proportional to a given function of its degree in the old tree. There have been some results concerning the case when this function is linear, it has been shown that the asymptotic degree distribution of the tree converges to a distribution with a power tail. We extend these results to a wide range of functions providing not only the asymptotic degree distribution, but also a limit theorem for the tree itself as viewed from a random point. The main idea is to consider the process in continuous time and to apply some classical results about general branching processes.

Anita Winter

Subtree Prune and Regraft: a reversible real tree valued Markov process

The real trees form a class of metric spaces that extends the class of trees with edge lengths by allowing behavior such as infinite total edge length and vertices with infinite branching degree. A well-known example for an R-tree is David Aldous’s Brownian continuum random tree (CRT), i.e. the tree inside a standard Brownian excursion.

The Brownian CRT arises as the scaling limit as of a critical finite variance Galton-Watson tree conditioned to have total population size .

We use Dirichlet form methods to construct and analyze a reversible Markov process whose stationary distribution is the Brownian CRT. This process is inspired by the subtree pruning and regrafting Markov chain that appears in phylogenetic analysis.

A key technical ingredient in this work is the use of a Hausdorff–Gromov type distance to metrize the space whose elements are compact real trees equipped with a probability measure.