Tomasz \L uczak, Pozna\'n, Poland

The height of a random tree. How to estimate it quickly?

A simple argument will be presented, that one can use to study the behaviour of a greedy algorithm estimating the height of a random labelled rooted tree. In particular, we shall show that the expected height of a random rooted tree found by such an algorithm is $(1+o(1))C\sqrt n$, where $$C=\sqrt{\pi}{{\sqrt{2} \ln (\sqrt 2+1)-1}\over{2-\sqrt 2\ln (\sqrt 2+1)}} = 0.579686...$$ (which is roughly 23\% of the expected height of a random rooted tree).