Geodesic
Limit theorems for the sizes of trees of an unlabeled graph of a random mapping
Diskretnaya Matematika, Tome 16 (2004) no. 3, pp. 63-75 
Yu. L. Pavlov. Limit theorems for the sizes of trees of an unlabeled graph of a random mapping. Diskretnaya Matematika, Tome 16 (2004) no. 3, pp. 63-75. http://geodesic.mathdoc.fr/item/DM_2004_16_3_a2/
@article{DM_2004_16_3_a2,
     author = {Yu. L. Pavlov},
     title = {Limit theorems for the sizes of trees of an unlabeled graph of a random mapping},
     journal = {Diskretnaya Matematika},
     pages = {63--75},
     year = {2004},
     volume = {16},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_3_a2/}
}
TY  - JOUR
AU  - Yu. L. Pavlov
TI  - Limit theorems for the sizes of trees of an unlabeled graph of a random mapping
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 63
EP  - 75
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_3_a2/
LA  - ru
ID  - DM_2004_16_3_a2
ER  - 
%0 Journal Article
%A Yu. L. Pavlov
%T Limit theorems for the sizes of trees of an unlabeled graph of a random mapping
%J Diskretnaya Matematika
%D 2004
%P 63-75
%V 16
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2004_16_3_a2/
%G ru
%F DM_2004_16_3_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. 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.

[1] Kolchin V. F., Sluchainye otobrazheniya, Nauka, Moskva, 1984 | MR

[2] Stepanov V. E., “Predelnye raspredeleniya nekotorykh kharakteristik sluchainykh otobrazhenii”, Teoriya veroyatnostei i ee primeneniya, 14:4 (1969), 639–653 | MR | Zbl

[3] Pavlov Yu. L., “Asimptoticheskoe raspredelenie maksimalnogo ob'ema dereva v sluchainom lese”, Teoriya veroyatnostei i ee primeneniya, 22:3 (1977), 523–533 | MR | Zbl

[4] Pavlov Yu. L., “Predelnye teoremy dlya chisla derevev zadannogo ob'ema v sluchainom lese”, Matem. sb., 103:3 (1977), 392–403 | MR | Zbl

[5] Harris B., “Probability distributions related to random mappings”, Ann. Math. Stat., 31:4 (1960), 1045–1062 | DOI | MR | Zbl

[6] Meir A., Moon J. W., “On random mapping patterns”, Combinatorica, 4:1 (1984), 61–70 | DOI | MR | Zbl

[7] Kharari F., Palmer E., Perechislenie grafov, Mir, Moskva, 1977 | MR

[8] Otter R., “Chislo derevev”, Perechislitelnye zadachi kombinatornogo analiza, Mir, Moskva, 1979, 139–159 | MR

[9] Mutafchiev L. R., “Limit theorem concerning random mapping patterns”, Combinatorica, 8:4 (1988), 345–356 | DOI | MR | Zbl

[10] Ibragimov I. A., Linnik Yu. V., Nezavisimye i statsionarno svyazannye velichiny, Nauka, Moskva, 1965

[11] Esseen C. G., “On the concentration function of a sum of independent random variables”, Z. Wahrscheinlichkeitstheorie und Verw. Geb., 9:4 (1968), 290–308 | DOI | MR | Zbl