Markov branching in the vertex splitting model

Abstract

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.

30 pages,7 figures

References in corpus (12)

• The topological structure of scaling limits of large planar maps
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• The spectral dimension of generic trees
• On the spectral dimension of causal triangulations
• Condensation in nongeneric trees
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models
• Uniform infinite planar triangulation and related time-reversed critical branching process
• A growth model for RNA secondary structures
• Mass distribution exponents for growing trees
• The infinite volume limit of Ford's alpha model
• Appearance of vertices of infinite order in a model of random trees
• Random tree growth by vertex splitting

Cited by in corpus (1)

• Spectral dimension of trees with a unique infinite spine