Limit theorems for the sizes of trees of an unlabeled graph of a random mapping

Yu. L. Pavlov

Diskretnaya Matematika, Tome 16 (2004) no. 3, pp. 63-75

Résumé

We find limit distributions of the maximum size of a tree and of the number of trees of given size in an unlabelled random forest consisting of $N$ rooted trees and $n$ non-root vertices provided that $N,n\to\infty$ so that $0$. With the use of these results, for the unlabelled graph of a random single-valued mapping of the set $\{1,2,\ldots,n\}$ into itself we prove theorems on the limit behaviour of the maximum tree size and of the number of trees of size $r$ as $n\to\infty$ in the cases of fixed $r$ and $r/n^{1/3}\ge C_3>0$. This research was supported by grant 1758.2003.1 of the President of Russian Federation for support of the leading scientific schools.