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
Department of Mathematics, College of Science, Southern Illinois University Carbondale, Carbondale 62901-4408, IL, USA
Received 23 March 2004; Revised 8 November 2005
Copyright © 2005 Lane Clark. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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.