Séminaire de statistique, Université Laval, 2 février 2012

le 30 janvier 2012 à 11:01

Le jeudi 2 février 2012, à 13 h 30, en la salle 1240 du pavillon Alexandre-Vachon

Cutting down trees with a Markov chainsaw
Let $T_n$ be a uniformly random rooted tree on labels $1,\ldots, n$. Removing an edge from $T_n$ separates $T_n$ into two components. Throw away the component not containing the root. Repeat this process until all that is left is the root, and call the number of edge removals (cuts) $C_n$. In 2003, Panholzer showed that $C_n/n^{1/2}$ converges in distribution to a Rayleigh random variable; Janson (2005) generalized the result to all critical conditioned Galton-Watson trees with finite variance offspring distribution.