Extremal values in recursive trees via a new tree growth process

Laura Eslava

Published 2017-01-06Version 1

We give convergence rates on the number of vertices with degree at least c ln n, in random recursive trees on n vertices. This allows us to extend the range for which the distribution of the number of vertices of a given degree is well understood. Conceptually, the key innovation of our work lies in a new tree growth process ((T_n , s_n),n>1) where T_n is a rooted labeled tree on n vertices and s_n is a permutation of the vertex labels. The shape of T_n has the same law as that of a random recursive tree. Interesting on its own right, this process obtains T_n from T_(n-1) by a procedure which attaches a vertex labeled n to T_(n-1) and rewires some of the edges in T_(n-1) towards the newly added vertex. Additionally, the new tree growth process can be understood as a new coupling of all finite Kingman's coalescents.