-
Internal diffusion-limited aggregation (IDLA) is a stochastic growth model on
a graph $G$ which describes the formation of a random set of vertices growing
from the origin (some fixed vertex) of $G$. Particles start at the origin and
perform simple random walks; each particle moves until it lands on a site which
was not previously visited by other particles. This random set of occupied
sites in $G$ is called the IDLA cluster.
In this paper we consider IDLA on Sierpinski gasket graphs, and show that the
IDLA cluster fills balls (in the graph metric) with probability 1.
-
The divisible sandpile model is a growth model on graphs that was introduced
by Levine and Peres as a tool to study internal diffusion limited aggregation.
In this work we investigate the shape of the divisible sandpile model on the
graphical Sierpinski gasket SG. We show that the shape is a ball in the graph
metric of SG. Moreover we give an exact representation of the odometer function
of the divisible sandpile.
-
We introduce a family of stochastic processes on the integers, depending on a
parameter $p \in [0,1]$ and interpolating between the deterministic rotor walk
(p=0) and the simple random walk (p=1/2). This p-rotor walk is not a Markov
chain but it has a local Markov property: for each $x \in \mathbb{Z}$ the
sequence of successive exits from $x$ is a Markov chain. The main result of
this paper identifies the scaling limit of the p-rotor walk with two-sided
i.i.d. initial rotors. The limiting process takes the form
$\sqrt{\frac{1-p}{p}} X(t)$, where $X$ is a doubly perturbed Brownian motion,
that is, it satisfies the implicit equation \begin{equation} X(t) =
\mathcal{B}(t) + a \sup_{s\leq t} X(s) + b \inf_{s\leq t} X(s) \end{equation}
for all $t \in [0,\infty)$. Here $\mathcal{B}(t)$ is a standard Brownian motion
and $a,b<1$ are constants depending on the marginals of the initial rotors on
$\mathbb{N}$ and $-\mathbb{N}$ respectively. Chaumont and Doney [CD99] have
shown that the above equation has a pathwise unique solution $X(t)$, and that
the solution is almost surely continuous and adapted to the natural filtration
of the Brownian motion. Moreover, $\limsup X(t) = +\infty$ and $\liminf X(t) =
-\infty$ [CDH00]. This last result, together with the main result of this
paper, implies that the p-rotor walk is recurrent for any two-sided i.i.d.
initial rotors and any $0<p<1$.
-
A rotor-router walk on a graph is a deterministic process, in which each
vertex is endowed with a rotor that points to one of the neighbors. A particle
located at some vertex first rotates the rotor in a prescribed order, and then
it is routed to the neighbor the rotor is now pointing at. In the current work
we make a step toward in understanding the behavior of rotor-router walks on
random trees. More precisely, we consider random i.i.d. initial configurations
of rotors on Galton-Watson trees, i.e. on a family tree arising from a
Galton-Watson process, and give a classification in recurrence and transience
for rotor-router walks on these trees.
-
The aim of this note is to extend the result of Angel and Holroyd concerning
the transience and the recurrence of transfinite rotor-router walks, for random
initial configuration of rotors on homogeneous trees. We address the same
question on directed covers of finite graphs, which are also called trees with
finitely many cone types or periodic trees. Furthermore, we provide an example
of a directed cover such that the rotor-router walk can be either recurrent or
transient, depending only on the planar embedding of the periodic tree.
-
A rotor-router walk is a deterministic version of a random walk, in which the
walker is routed to each of the neighbouring vertices in some fixed cyclic
order. We consider here directed covers of graphs (called also periodic trees)
and we study several quantities related to rotor-router walks on directed
covers. The quantities under consideration are: order of the rotor-router
group, order of the root element in the rotor-router group and the connection
with random walks.
-
The two-dimensional comb lattice $C_2$ is a natural spanning tree of the
Euclidean lattice $\mathbb{Z}^2$. We study three related cluster growth models
on $C_2$: internal diffusion limited aggregation (IDLA), in which random
walkers move on the vertices of $C_2$ until reaching an unoccupied site where
they stop; rotor-router aggregation in which particles perform deterministic
walks, and stop when reaching a site previously unoccupied; and the divisible
sandpile model where at each vertex there is a pile of sand, for which, at each
step, the mass exceeding 1 is distributed equally among the neighbours. We
describe the shape of the divisible sandpile cluster on $C_2$, which is then
used to give inner bounds for IDLA and rotor-router aggregation.
-
We prove a shape theorem for rotor-router aggregation on the comb, for a
specific initial rotor configuration and clockwise rotor sequence for all
vertices. Furthermore, as an application of rotor-router walks, we describe the
harmonic measure of the rotor-router aggregate and related shapes, which is
useful in the study of other growth models on the comb. We also identify the
shape for which the harmonic measure is uniform. This gives the first known
example where the rotor-router cluster has non-uniform harmonic measure, and
grows with different speeds in different directions.
-
A language L over a finite alphabet is growth-sensitive (or entropy
sensitive) if forbidding any set of subwords F yields a sub-language L^F whose
exponential growth rate (entropy) is smaller than that of L. Let (X, E, l) be
an infinite, oriented, labelled graph. Considering the graph as an (infinite)
automaton, we associate with any pair of vertices x,y in X the language
consisting of all words that can be read as the labels along some path from x
to y. Under suitable, general assumptions we prove that these languages are
growth-sensitive. This is based on using Markov chains with forbidden
transitions.