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.