×

Height of a random tree. (English) Zbl 0964.05056

The author considers continuous time Markov chains in which the states are finite trees. For each vertex present in the tree, a new edge is attached to the vertex with rate \(\lambda> 0\) and edges are contracted with rate \(\mu\geq 0\). The author shows, among other things, that if \(\mu= 0\) the growth of the expected height of the tree is asymptotically linear; if \(\mu>\lambda\) the process is ergodic; and if \(0< \mu<\lambda\) the growth of the expected height is less than linear but “sufficiently close to linear”.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
60B99 Probability theory on algebraic and topological structures
05C12 Distance in graphs