Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-22T06:58:42.554Z Has data issue: false hasContentIssue false
  • English
  • Français

Components of Random Forests

Published online by Cambridge University Press:  12 September 2008

Tomasz Łuczak  and
Boris Pittel
Tomasz Łuczak
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland.
Boris Pittel
Affiliation:
Department of Mathematics, Ohio State University, Columbus, Ohio 43210, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

A forest ℱ(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 Érdő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 ℱ(n, M). The similarity to the random graph is far from being complete. For instance, in the supercritical phase, the giant tree in ℱ(n, M) grows roughly two times slower than the largest component of G(n, M) and the second largest tree in ℱ(n, M) is of the order n⅔ for every M = n/2 +s, provided that s3n−2 → ∞ and s = o(n), while its counterpart in G(n, M) is of the order n2s−2 log(s3n−2) ≪ n⅔.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 1 , March 1992 , pp. 35 - 52
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Aldous, D.. A random tree model associated with random graphs. Random Structures & Algorithms 1 (1990), 383–402.CrossRefGoogle Scholar
[2] Blake, I. F. and Konheim, A. G.. Big buckets are (are not) better!. J. Assoc. Comput. Mach. 24 (1977), 591–606.CrossRefGoogle Scholar
[3] Bollobás, B.. The evolution of random graphs. Trans. Amer. Math. Soc. 286 (1984), 257–274.CrossRefGoogle Scholar
[4] Bollobás, B.. Random Graphs. Academic Press, London (1985).Google Scholar
[5] Britikov, V. E.. Asymptotic number of forests from unrooted trees. Math. Notes 43 (1988), 387–394.CrossRefGoogle Scholar
[6] Érdős, P. and Renyi, A.. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5 (1960), 17–61.Google Scholar
[7] Flaolet, P. and Odlyzko, A.. The average height of binary trees and other simple trees. J. Computer and System Sciences 25 (1982), 171–213.CrossRefGoogle Scholar
[8] Ibragimov, I. A. and Linnik, Yu. V.. Independent and Stationary Sequences of Random Variables. Wolters-Noordhoof Publishing (1971).Google Scholar
[9] Knuth, D. E.. The Art of Computer Programming. 3. Sorting and Searching. Addison-Wesley, Reading, Mass. (1973).Google Scholar
[10] Knuth, D. E. and Pittel, B.. A recurrence related to trees. Proc. Amer. Math. Soc. 105 (1989), 335–349.CrossRefGoogle Scholar
[11] Knuth, D. E. and Schönhage, A.. The expected linearity of a simple equivalence algorithm. Theoret. Comput. Sci. 5 (1978), 281–315.CrossRefGoogle Scholar
[12] Kolchin, V. F.. On the behavior of a random graph near a critical point. Theory Prob. Appl. 31 (1986), 439–451.CrossRefGoogle Scholar
[13] Kolchin, V. F., Sevast'yanov, B. A. and Chistyakov, V. P.. Random Allocations. John Wiley, New York (1978).Google Scholar
[14] Luczak, T.. Component behaviour near the critical point of the random graph process. Random Structures & Algorithms 1 (1990), 217–223.CrossRefGoogle Scholar
[15] Luczak, T., Pittel, B. and Wierman, J. C.. The structure of a random graph near the point of the phase transition. Trans. Amer. Math. Soc. to appear.Google Scholar
[16] Meir, A. and Moon, J. W.. The distance between points in random trees. J. Comb. Theory 8 (1970), 99–103.CrossRefGoogle Scholar
[17] Meir, A. and Moon, J. W.. On the altitude of nodes in random trees. Can J. Math. 30 (1978), 997–1015.CrossRefGoogle Scholar
[18] Meir, A. and Moon, J. W.. The asymptotic behaviour of coefficients of powers of certain generating functions. Europ. J. Comb. 11 (1990), 581–587.CrossRefGoogle Scholar
[19] Moon, J. W.. Counting labelled trees. Canadian Mathematica Congress, Montreal (1970).Google Scholar
[20] Pavlov, Yu. L.. The asymptotic distribution of maximum tree size in a random forest. Theory Prob. Appl. 22 (1977), 509–520.CrossRefGoogle Scholar
[21] Pavlov, Yu. L.. A case of limit distribution of the maximal volume of a tree in a random forest. Math. Notes 25 (1979), 387–392.CrossRefGoogle Scholar
[22] Pittel, B.. Linear probing: the probable largest search time grows logarithmically with the number of records. J. Algorithms 8 (1987), 236–249.CrossRefGoogle Scholar
[23] Pittel, B.. On a random graph with a subcritical number of edges. Trans. Amer. Math. Soc. 309 (1988), 51–75.CrossRefGoogle Scholar
[24] Pittel, B.. On tree census and the giant component in sparse random graphs. Random Structures & Algorithms 1 (1990), 311–342.CrossRefGoogle Scholar
[25] Pittel, B., Woyczynski, W. A. and Mann, J. A.. Random tree-type partition as a model for acyclic polymerization: Gaussian behavior of the subcritical phase. Random Graphs '87. Eds. Karonski, M., Jaworski, J. and Ruciński, A.. John Wiley, Chichester 1990, 223–274.Google Scholar
[26] Pittel, B., Woyczynski, W. A. and Mann, J. A.. Random tree-type partition as a model for acyclic polymerization: Holtsmark (3/2-stable) distribution of the supercritical gel. Ann. Probab. 18 (1990), 319–341.CrossRefGoogle Scholar
[27] Pittel, B. and Woyczynski, W. A.. A graph-valued Markov process as rings-allowed polymerization model: subcritical behavior. SIAM J. Appl. Math. 50 (1990), 1200–1220.CrossRefGoogle Scholar
[28] Rényi, A.. Some remarks on the theory of trees. Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 73–85.Google Scholar
[29] Spouge, J. L.. Polymers and random graphs: asymptotic equivalence to branching processes. J. Stat. Phys. 38 (1985), 573–587.CrossRefGoogle Scholar
[30] Stepanov, V. E.. On the probability of connectedness of a random graph Gm(t). Theory Probab. Appl. 15 (1970), 55–67.CrossRefGoogle Scholar
[31] Stepanov, V. E.. Phase transition in random graphs. Theory Probab. Appl. 15 (1970), 187–203.CrossRefGoogle Scholar
[32] Stepanov, V. E.. Structure of random graphs Gm(x/h). Theory Probab. Appl. 17 (1972), 227–242.CrossRefGoogle Scholar
[33] Stepanov, V. E.. On some features of the structure of a random graph near a critical point. Theory Probab. Appl. 32 (1988), 573–594.CrossRefGoogle Scholar
[34] Tkachuk, S. G.. Local limit theorems and large deviation for stable limit distributions. USSR Ser. Fiz.-Mat. Nauk 2 (1973), 30–33.Google Scholar
[35] Whittle, P.. Polymerization process with intrapolymer bonding. I. One type of unit, II. Stratified processes, III. Several types of unit. Adv. Appl. Probab. 12 (1980), 94–153.CrossRefGoogle Scholar
[36] Whittle, P.. A direct evaluation of the equilibrium distribution for a polymerization process. Theory Probab. Appl. 24 (1981), 344–353.Google Scholar
[37] Whittle, P.. Random graphs and polymerization processes. Ann. Discrete Math. 28 (1985), 337–349.Google Scholar
[38] Yao, A. C.. On the average behavior of set merging algorithms, (extended abstract). Proc. 8th Annual ACM Symposium on Theory of Computing (1976), 192–195.CrossRefGoogle Scholar
[39] Yao, A. C.. On the expected performance of path compression algorithms. SIAM J. Computing 14 (1985), 129–133.CrossRefGoogle Scholar