International Journal of Mathematics and Mathematical Sciences
Volume 2005 (2005), Issue 23, Pages 3867-3882
doi:10.1155/IJMMS.2005.3867

Local extrema in random trees

Abstract

The number of local maxima (resp., local minima) in a tree T∈𝒯n rooted at r∈[n] is denoted by Mr(T) (resp., by mr(T)). We find exact formulas as rational functions of n for the expectation and variance of M1(T) and mn(T) when T∈𝒯n is chosen randomly according to a uniform distribution. As a consequence, a.a.s. M1(T) and mn(T) belong to a relatively small interval when T∈𝒯n.