RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2007 Volume 19, Issue 3, Pages 35–50 (Mi dm964)

This article is cited in 2 papers

On conditions for emergence of a giant tree in a random unlabelled forest

E. V. Khvorostyanskaya


Abstract: We consider the set of random forests consisting of $N$ rooted trees ordered in one of $N!$ possible ways and of $n$ nonroot unlabelled vertices. As $N,n\to\infty$, we find the limit distributions of the $(N-p)$th term of the set of order statistics obtained by arranging the sizes of the trees of a random unlabelled forest in nondescending order for fixed $p=1,2,\dots$ . We find that a giant tree (that is, a tree of size $n+o(n)$) emerges in the only case where $N,n\to\infty$ so that $N/\sqrt n\to0$.

UDC: 519.2

Received: 25.05.2006

DOI: 10.4213/dm964


 English version:
Discrete Mathematics and Applications, 2007, 17:5, 439–454

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025