Premium
The largest tree in certain models of random forests
Author(s) -
Mutafchiev Ljuben
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199810/12)13:3/4<211::aid-rsa2>3.0.co;2-y
Subject(s) - limiting , mathematics , combinatorics , tree (set theory) , stability (learning theory) , scaling , distribution (mathematics) , statistical physics , statistics , mathematical analysis , physics , geometry , computer science , mechanical engineering , machine learning , engineering
We consider four families of forests on n vertices: labeled and unlabeled forests containing rooted and unrooted trees, respectively. A forest is chosen uniformly from one of the given four families. The limiting distribution of the size of its largest tree is then studied as n →∞. Convergences to discrete distributions depending on 1/2‐ and 3/2‐stable probability densities are established. It turns out that 1/2‐stability parameter appears when the random forest consists of rooted trees only. Otherwise (i.e., when it contains only unrooted trees), this parameter is 3/2. Furthermore, we show that the labels' deletion of forest's vertices does not change the corresponding limiting law in general; it changes the values of some scaling and additive parameters of the limiting distributions that we obtain. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13: 211–228, 1998