Geodesic
The maximum tree of a random forest in the configuration graph
Sbornik. Mathematics, Tome 212 (2021) no. 9, pp. 1329-1346 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Galton-Watson random forests with a given number of root trees and a known number of nonroot vertices are investigated. The distribution of the number of direct offspring of each particle in the forest-generating process is assumed to have infinite variance. Branching processes of this kind are used successfully to study configuration graphs aimed at simulating the structure and development dynamics of complex communication networks, in particular the internet. The known relationship between configuration graphs and random forests reflects the local tree structure of simulated networks. Limit theorems are proved for the maximum size of a tree in a random forest in all basic zones where the number of trees and the number of vertices tend to infinity. Bibliography: 14 titles.
Keywords: random forest, tree size, limit theorems.
Mots-clés : configuration graph 
@article{SM_2021_212_9_a6,
     author = {Yu. L. Pavlov},
     title = {The maximum tree of a~random forest in the configuration graph},
     journal = {Sbornik. Mathematics},
     pages = {1329--1346},
     year = {2021},
     volume = {212},
     number = {9},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2021_212_9_a6/}
}
TY  - JOUR
AU  - Yu. L. Pavlov
TI  - The maximum tree of a random forest in the configuration graph
JO  - Sbornik. Mathematics
PY  - 2021
SP  - 1329
EP  - 1346
VL  - 212
IS  - 9
UR  - http://geodesic.mathdoc.fr/item/SM_2021_212_9_a6/
LA  - en
ID  - SM_2021_212_9_a6
ER  - 
%0 Journal Article
%A Yu. L. Pavlov
%T The maximum tree of a random forest in the configuration graph
%J Sbornik. Mathematics
%D 2021
%P 1329-1346
%V 212
%N 9
%U http://geodesic.mathdoc.fr/item/SM_2021_212_9_a6/
%G en
%F SM_2021_212_9_a6
Yu. L. Pavlov. The maximum tree of a random forest in the configuration graph. Sbornik. Mathematics, Tome 212 (2021) no. 9, pp. 1329-1346. http://geodesic.mathdoc.fr/item/SM_2021_212_9_a6/

[1] Yu. L. Pavlov, “Conditional configuration graphs with discrete power-law distribution of vertex degrees”, Sb. Math., 209:2 (2018), 258–275 | DOI | DOI | MR | Zbl

[2] B. Bollobás, “A probabilistic proof of an asymptotic formula for the number of labelled regular graphs”, European J. Combin., 1:4 (1980), 311–316 | DOI | MR | Zbl

[3] R. van der Hofstad, Random graphs and complex networks, v. 1, Camb. Ser. Stat. Probab. Math., 43, Cambridge Univ. Press, Cambridge, 2017, xvi+321 pp. | DOI | MR | Zbl

[4] R. Hofstad, Random graphs and complex networks, v. 2, Camb. Ser. Stat. Probab. Math., Cambridge Univ. Press, Cambridge (to appear); 2021, xx+510 pp. https://www.win.tue.nl/~rhofstad/

[5] H. Reittu, I. Norros, “On the power-law random graph model of massive data networks”, Performance Evaluation, 55:1-2 (2004), 3–23 | DOI

[6] Yu. L. Pavlov, Random forests, VSP, Utrecht, 2000, 122 pp. | DOI

[7] N. I. Kazimirov, Yu. L. Pavlov, “A remark on Galton–Watson forests”, Discrete Math. Appl., 10:1 (2000), 49–62 | DOI | DOI | MR | Zbl

[8] V. M. Zolotarev, One-dimensional stable distributions, Transl. Math. Monogr., 65, Amer. Math. Soc., Providence, RI, 1986, x+284 pp. | DOI | MR | MR | Zbl | Zbl

[9] Yu. L. Pavlov, “Limit distribution of the number of trees of given size in a random forest”, Discrete Math. Appl., 6:2 (1996), 117–133 | DOI | DOI | MR | Zbl

[10] V. F. Kolchin, Random mappings, Transl. Ser. Math. Engrg., Optimization Software, Inc., Publications Division, New York, 1986, xiv+207 pp. | MR | MR | Zbl | Zbl

[11] W. Feller, An introduction to probability theory and its applications, v. 2, 2nd ed., John Wiley Sons, Inc., New York–London–Sydney, 1971, xxiv+669 pp. | MR | MR | Zbl | Zbl

[12] I. A. Ibragimov, Yu. V. Linnik, Independent and stationary sequences of random variables, Wolters-Noordhoff Publishing, Groningen, 1971, 443 pp. | MR | MR | Zbl | Zbl

[13] A. Erdélyi, W. Magnus, F. Oberhettinger, F. G. Tricomi, Higher transcendental functions, Based, in part, on notes left by H. Bateman, v. 2, McGraw-Hill Book Company, Inc., New York–Toronto–London, 1953, xvii+396 pp. | MR | MR | Zbl | Zbl

[14] A. B. Mukhin, “Local limit theorems for lattice random variables”, Theory Probab. Appl., 36:4 (1992), 698–713 | DOI | MR | Zbl