Let TT be a uniform random tree on nn vertices. We are interested in the distribution of F(T)F(T), where the function FF could depend significantly on the tree structure. It is natural to use Prüfer codes to define a martingale for F(T)F(T). It turns out to be advantageous to do this in two steps: first specify the degree sequence and then use the Doob martingale process which exposes deleted leaves. As a working example we will show the asymptotic normality of the number of three-paths in TT. Other straightforward applications include the distribution of the number of vertices of a given degree and the number of two-paths.


Mikhail Isaev

Research Area

UNSW Sydney


Thu, 18/05/2017 - 1:00pm


RC-4082, The Red Centre, UNSW