Random Trees

In this first chapter we survey several types of random trees. We start with basic notions on trees and the description of several concepts of tree counting problems. In particular we distinguish between rooted and unrooted, plane and non-plane, and labelled and unlabelled trees. It is also possible to modify the counting procedure by putting certain weights on trees, for example, by using the degree distribution.

Generating functions are not only a useful tool to count combinatorial objects but also an analytic object that can be used to obtain asymptotics. They can be used to encode the distribution of random variables that are related to counting problems and, hence, asymptotic methods can be applied to obtain probabilistic limit theorems like central limit theorems.

Galton-Watson trees or simply generated trees are random trees that are obtained by Galton-Watson branching processes conditioned on the total progeny.¹ This is in fact a very natural and general concept of random trees that includes several kinds of combinatorial tree models like binary trees, planted plane trees, labelled rooted trees, etc. (compare with Section 1.2.7).

Chapter 4 was devoted to the horizontal profile of certain classes of trees and we have observed that this kind of profile can be approximated by the local time of the Brownian excursion.

Recursive trees and binary search trees can be considered as the result of a growth process and although they are of different structure (in particular, concerning their degree distribution) they have many properties in common.

Digital trees like tries or digital search trees are important in many computer science applications like data compression, pattern matching or hashing. For the popular Lempel-Ziv compression scheme [208] is strongly related to digital search trees.

At first sight planar graphs and trees have nothing in common despite the trivial fact that trees are planar. Nevertheless there are strong similarities in the combinatorial and asymptotic analysis of trees and planar graphs. Planar graphs contain several (hidden) tree or tree-like structures. The tree-decomposition into cut-vertices and blocks (2-connected components) is the most prominent one. The reduction to 3-connected components is more involved but uses so-called series-parallel networks that are obtained from series-parallel extensions of trees. Thus, it is natural that properly extended tree counting techniques and analytic techniques that have been developed for trees apply. However, these extensions are not straight forward. Several graph theoretical and and also topological concepts have to be combined with combinatorics on trees. There are also different levels of complexity in the asymptotics analysis. From this point of view outerplanar graphs and series-parallel graphs — these are two subclasses of planar graphs that we will study first — are more tree-like than the class of all planar graphs, since the singularity structure of the corresponding generating functions is of square root type \( \sqrt {R - x} \), whereas the class of all planar graphs has a dominant singularity of the form (R−x)^3/2. Geometrically this indicates that outerplanar graphs and series-parallel graphs are more or less governed by a one-dimensional topology (as trees) but the class of all planar graphs by a two-dimensional one.