Abstract:
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<C_1\le N/\sqrt{n}\le C_2<\infty$.
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.
Fulltext:
PDF file (1012 kB)