On the Growth of a Ballistic Deposition Model on Finite Graphs

We revisit a ballistic deposition process introduced by Atar, Athreya and Kang. Let $\mathcal{G}=(V,E)$ be a finite connected graph. We choose independently and uniformly vertices in $\mathcal{G}$. If a vertex $x$ is chosen and the previous height configuration is given by $h=(h_y)_{y \in V} \in $\mathbb{N}$_0^V$,theheight$h_x$ is replaced by $${\tilde{h}}_x:=1+\underset{y\sim x}{\max }{h}_y\mathrm{.}$$ We study asymptotic properties of this growth model. We determine the asymptotic growth parameter $\gamma (\mathcal{G})$ for some graphs and prove a central limit theorem for the fluctuations around $\gamma ( $\mathcal{G}$)$. We also give a new graph-theoretic interpretation of an inequality obtained by Atar et al…