Cutting down random trees

Extract

Let T_n denote a tree with n(≧ 2) labelled points: we assume T_n is rooted at a given point x, say the point labelled 1 (see [3] for definitions not given here). If we remove some edge e of T_n, then T_n falls into two subtrees one of which, say T_k, contains the root x. If k ≧ 2 we can remove some edge of T_k and obtain an even smaller subtree of T_n that contains x. If we repeat this process we will eventually obtain the subtree consisting of x itself. Let λ = λ(T_n) denote the number of edges removed from T_n before the root x is isolated. Our main object here is to determine the expected value μ(n) and variance σ²(n) of λ(T_n) under the assumptions (1) T_n is chosen at random from the set of nⁿ⁻² trees with n labelled points that are rooted at point x, and (2) at each stage the edge removed is chosen at random from the edges of the remaining subree containing x. It follows from our results that μ(n) ~ (½πn)½ and (2−½π)n ~ (2−½π)n as n tends to infinity. We also consider the corresponding problem for forests of rooted trees and for trees in which the degree of the root is specified. We are indebted to Professor Alistair Lachlan for suggesting the original problem to us.