×

Components of random forests. (English) Zbl 0793.05109

Summary: A forest \({\mathcal F}(n,M)\) chosen uniformly from the family of all labelled unrooted forests with \(n\) vertices and \(M\) edges is studied. We show that, like the Erdős-Rényi random graph \(G(n,M)\), the random forest exhibits three modes of asymptotic behaviour: subcritical, nearcritical and supercritical, with the phase transition at the point \(M= n/2\). For each of the phases, we determine the limit distribution of the size of the \(k\)th largest component of \({\mathcal F}(n,M)\). The similarity to the random graph is far from being complete. For instance, in the supercritical phase, the giant tree in \({\mathcal F}(n,M)\) grows roughly two times slower than the largest component of \(G(n,M)\) and the second largest tree in \({\mathcal F}(n,M)\) is of the order \(n^{2/3}\) for every \(M= n/2+ s\), provided that \(s^ 3 n^{-2}\to \infty\) and \(s= o(n)\), while its counterpart in \(G(n,M)\) is of the order \(n^ 2 s^{-2}\log(s^ 3 n^{-2})\ll n^{2/3}\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
Full Text: DOI

References:

[1] DOI: 10.2307/2046947 · Zbl 0672.41024 · doi:10.2307/2046947
[2] DOI: 10.1016/0304-3975(78)90009-9 · Zbl 0377.68024 · doi:10.1016/0304-3975(78)90009-9
[3] Ibragimov, Independent and Stationary Sequences of Random Variables (1971)
[4] DOI: 10.1137/0214010 · Zbl 0563.68043 · doi:10.1137/0214010
[5] DOI: 10.1016/0022-0000(82)90004-6 · Zbl 0499.68027 · doi:10.1016/0022-0000(82)90004-6
[6] Érd?s, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5 pp 17– (1960)
[7] Whittle, Ann. Discrete Math. 28 pp 337– (1985)
[8] Britikov, Math. Notes 43 pp 387– (1988) · doi:10.1007/BF01158847
[9] Whittle, Theory Probab. Appl. 24 pp 344– (1981)
[10] Bollobás, Random Graphs (1985)
[11] DOI: 10.2307/1999405 · Zbl 0579.05046 · doi:10.2307/1999405
[12] DOI: 10.2307/1426496 · Zbl 0421.60094 · doi:10.2307/1426496
[13] Blake, J. Assoc. Comput. Mach. 24 pp 591– (1977) · Zbl 0408.68061 · doi:10.1145/322033.322038
[14] Tkachuk, USSR Ser. Fiz.-Mat. Nauk 2 pp 30– (1973)
[15] DOI: 10.1002/rsa.3240010402 · Zbl 0747.05077 · doi:10.1002/rsa.3240010402
[16] DOI: 10.1137/1132091 · Zbl 0656.60021 · doi:10.1137/1132091
[17] DOI: 10.1137/1117028 · Zbl 0264.90048 · doi:10.1137/1117028
[18] DOI: 10.1137/1115027 · doi:10.1137/1115027
[19] DOI: 10.1137/1115004 · Zbl 0233.60006 · doi:10.1137/1115004
[20] DOI: 10.1007/BF01010478 · doi:10.1007/BF01010478
[21] Rényi, Publ. Math. Inst. Hungar. Acad. Sci. 4 pp 73– (1959)
[22] DOI: 10.1137/0150073 · Zbl 0743.60112 · doi:10.1137/0150073
[23] DOI: 10.1214/aop/1176990951 · Zbl 0743.60110 · doi:10.1214/aop/1176990951
[24] Pittel, Random Graphs ’87 pp 223– (1990)
[25] DOI: 10.1002/rsa.3240010306 · Zbl 0747.05080 · doi:10.1002/rsa.3240010306
[26] DOI: 10.2307/2001158 · Zbl 0658.05062 · doi:10.2307/2001158
[27] DOI: 10.1016/0196-6774(87)90040-X · Zbl 0618.68052 · doi:10.1016/0196-6774(87)90040-X
[28] Pavlov, Math. Notes 25 pp 387– (1979) · Zbl 0452.60031 · doi:10.1007/BF01224845
[29] DOI: 10.1137/1122061 · Zbl 0386.60011 · doi:10.1137/1122061
[30] Moon, Canadian Mathematica Congress (1970)
[31] Meir, Europ. J. Comb. 11 pp 581– (1990) · Zbl 0735.05008 · doi:10.1016/S0195-6698(13)80043-1
[32] Meir, Can J. Math. 30 pp 997– (1978) · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[33] DOI: 10.1016/S0021-9800(70)80012-6 · Zbl 0185.47001 · doi:10.1016/S0021-9800(70)80012-6
[34] Luczak, Trans. Amer. Math. Soc.
[35] Luczak, Random Structures & Algorithms 1 pp 217– (1990)
[36] Kolchin, Random Allocations (1978)
[37] DOI: 10.1137/1131058 · Zbl 0616.60013 · doi:10.1137/1131058
[38] Knuth, The Art of Computer Programming. 3. Sorting and Searching (1973) · Zbl 0302.68010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.