1103.3445 (Sigurdur Orn Stefansson)

Markov branching in the vertex splitting model    [PDF]

Sigurdur Orn Stefansson

We study a special case of the vertex splitting model which is a recent model
of randomly growing trees. For any finite maximum vertex degree $D$, we find a
one parameter model, with parameter $\alpha \in [0,1]$ which has a so--called
Markov branching property. When $D=\infty$ we find a two parameter model with
an additional parameter $\gamma \in [0,1]$ which also has this feature. In the
case $D = 3$, the model bears resemblance to Ford's $\alpha$--model of
phylogenetic trees and when $D=\infty$ it is similar to its generalization, the
$\alpha\gamma$--model. For $\alpha = 0$, the model reduces to the well known
model of preferential attachment. In the case $\alpha > 0$, we prove
convergence of the finite volume probability measures, generated by the growth
rules, to a measure on infinite trees which is concentrated on the set of trees
with a single spine. We show that the annealed Hausdorff dimension with respect
to the infinite volume measure is $1/\alpha$. When $\gamma = 0$ the model
reduces to a model of growing caterpillar graphs in which case we prove that
the Hausdorff dimension is almost surely $1/\alpha$ and that the spectral
dimension is almost surely $2/(1+\alpha)$. We comment briefly on the
distribution of vertex degrees and correlations between degrees of neighbouring
vertices.

View original: http://arxiv.org/abs/1103.3445