๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The largest tree in certain models of random forests

โœ Scribed by Ljuben Mutafchiev

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
227 KB
Volume
13
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 1r2-and 3r2-stable probability densities are established. It turns out that 1r2-stability parameter appears when ลฝ the random forest consists of rooted trees only. Otherwise i.e., when it contains only . unrooted trees , this parameter is 3r2. 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.

๐Ÿ“œ SIMILAR VOLUMES

The largest induced tree in a sparse ran
The largest induced tree in a sparse random graph
โœ W. Fernandez de la Vega ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 192 KB ๐Ÿ‘ 1 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar

The distribution of nodes of given degre
The distribution of nodes of given degree in random trees
โœ Drmota, Michael; Gittenberger, Bernhard ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 391 KB ๐Ÿ‘ 2 views

Let T n denote the set of unrooted unlabeled trees of size n and let k โ‰ฅ 1 be given. By assuming that every tree of T n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value โˆผ ยต k n and variance โˆผ ฯƒ 2 k n with positive constants ยต