Random Growth Processes on Graphs

Abstract

In the present thesis, we consider three different random graph-theoretic growth models. These models are called ballistic deposition on finite graphs, Boolean percolation on directed graphs, and supercritical Galton-Watson branching processes with emigration.

For our ballistic deposition model on finite graphs, we obtain various results, which characterize the relationship between the asymptotic growth rate and the underyling graph. Moreover, we prove that the fluctuations around this growth rate always satisfy a central limit theorem.

In the context of Boolean percolation, we clarify under which conditions all but finitely many points of the graphs N_0^n and Z^n are covered. We also prove, for n ≥ 2, that it is impossible to cover the directed n-ary tree in this model. Besides, we present connections between this percolation model and the so-called random exchange process.

Finally, we study under which conditions supercritical branching processes with emigration become extinct almost surely, and whether the expected survival time is finite. We investigate the extinction probability in relation to the population size, and the asymptotic growth of the population. To some extent, supercritical branching processes with emigration behave similarly to subcritical branching processes with immigration.