{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T21:39:57Z","timestamp":1775079597052,"version":"3.50.1"},"reference-count":39,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":6039,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1992,3]]},"abstract":"<jats:p>A forest \u2131(<jats:italic>n, M<\/jats:italic>) chosen uniformly from the family of all labelled unrooted forests with n vertices and <jats:italic>M<\/jats:italic> edges is studied. We show that, like the \u00c9rd\u0151s-R\u00e9nyi random graph <jats:italic>G<\/jats:italic>(<jats:italic>n, M<\/jats:italic>), the random forest exhibits three modes of asymptotic behaviour: subcritical, nearcritical and supercritical, with the phase transition at the point <jats:italic>M<\/jats:italic> = <jats:italic>n<\/jats:italic>\/2. For each of the phases, we determine the limit distribution of the size of the <jats:italic>k<\/jats:italic>-th largest component of \u2131(<jats:italic>n, M<\/jats:italic>). The similarity to the random graph is far from being complete. For instance, in the supercritical phase, the giant tree in \u2131(<jats:italic>n, M<\/jats:italic>) grows roughly two times slower than the largest component of <jats:italic>G<\/jats:italic>(<jats:italic>n, M<\/jats:italic>) and the second largest tree in \u2131(<jats:italic>n, M<\/jats:italic>) is of the order <jats:italic>n<\/jats:italic><jats:sup>\u2154<\/jats:sup> for every <jats:italic>M<\/jats:italic> = <jats:italic>n<\/jats:italic>\/2 +<jats:italic>s<\/jats:italic>, provided that <jats:italic>s<\/jats:italic><jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic><jats:sup>\u22122<\/jats:sup> \u2192 \u221e and <jats:italic>s<\/jats:italic> = <jats:italic>o(n)<\/jats:italic>, while its counterpart in <jats:italic>G<\/jats:italic>(<jats:italic>n, M<\/jats:italic>) is of the order <jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup><jats:italic>s<\/jats:italic><jats:sup>\u22122<\/jats:sup> log(<jats:italic>s<\/jats:italic><jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic><jats:sup>\u22122<\/jats:sup>) \u226a <jats:italic>n<\/jats:italic><jats:sup>\u2154<\/jats:sup>.<\/jats:p>","DOI":"10.1017\/s0963548300000067","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:19:46Z","timestamp":1221218386000},"page":"35-52","source":"Crossref","is-referenced-by-count":27,"title":["Components of Random Forests"],"prefix":"10.1017","volume":"1","author":[{"given":"Tomasz","family":"\u0141uczak","sequence":"first","affiliation":[]},{"given":"Boris","family":"Pittel","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300000067_ref017","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1978-085-0"},{"key":"S0963548300000067_ref035","doi-asserted-by":"publisher","DOI":"10.2307\/1426496"},{"key":"S0963548300000067_ref036","first-page":"344","article-title":"A direct evaluation of the equilibrium distribution for a polymerization process","volume":"24","author":"Whittle","year":"1981","journal-title":"Theory Probab. Appl."},{"key":"S0963548300000067_ref034","first-page":"30","article-title":"Local limit theorems and large deviation for stable limit distributions","volume":"2","author":"Tkachuk","year":"1973","journal-title":"USSR Ser. Fiz.-Mat. Nauk"},{"key":"S0963548300000067_ref028","first-page":"73","article-title":"Some remarks on the theory of trees","volume":"4","author":"R\u00e9nyi","year":"1959","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"S0963548300000067_ref023","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1988-0957061-X"},{"key":"S0963548300000067_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/BF01224845"},{"key":"S0963548300000067_ref025","first-page":"223","volume-title":"Random Graphs '87","author":"Pittel","year":"1990"},{"key":"S0963548300000067_ref032","doi-asserted-by":"publisher","DOI":"10.1137\/1117028"},{"key":"S0963548300000067_ref030","doi-asserted-by":"publisher","DOI":"10.1137\/1115004"},{"key":"S0963548300000067_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90009-9"},{"key":"S0963548300000067_ref027","doi-asserted-by":"publisher","DOI":"10.1137\/0150073"},{"key":"S0963548300000067_ref019","volume-title":"Canadian Mathematica Congress","author":"Moon","year":"1970"},{"key":"S0963548300000067_ref001","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010402"},{"key":"S0963548300000067_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322038"},{"key":"S0963548300000067_ref003","doi-asserted-by":"publisher","DOI":"10.2307\/1999405"},{"key":"S0963548300000067_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/BF01158847"},{"key":"S0963548300000067_ref006","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"\u00c9rd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. Kozl."},{"key":"S0963548300000067_ref009","volume-title":"The Art of Computer Programming. 3. Sorting and Searching","author":"Knuth","year":"1973"},{"key":"S0963548300000067_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90004-6"},{"key":"S0963548300000067_ref008","volume-title":"Independent and Stationary Sequences of Random Variables","author":"Ibragimov","year":"1971"},{"key":"S0963548300000067_ref031","doi-asserted-by":"publisher","DOI":"10.1137\/1115027"},{"key":"S0963548300000067_ref014","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010305"},{"key":"S0963548300000067_ref010","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1989-0949878-9"},{"key":"S0963548300000067_ref015","article-title":"The structure of a random graph near the point of the phase transition","author":"Luczak","journal-title":"Trans. Amer. Math. Soc."},{"key":"S0963548300000067_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80012-6"},{"key":"S0963548300000067_ref037","first-page":"337","article-title":"Random graphs and polymerization processes","volume":"28","author":"Whittle","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"S0963548300000067_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(13)80043-1"},{"key":"S0963548300000067_ref020","doi-asserted-by":"publisher","DOI":"10.1137\/1122061"},{"key":"S0963548300000067_ref039","doi-asserted-by":"publisher","DOI":"10.1137\/0214010"},{"key":"S0963548300000067_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90040-X"},{"key":"S0963548300000067_ref012","doi-asserted-by":"publisher","DOI":"10.1137\/1131058"},{"key":"S0963548300000067_ref024","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010306"},{"key":"S0963548300000067_ref026","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990951"},{"key":"S0963548300000067_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BF01010478"},{"key":"S0963548300000067_ref033","doi-asserted-by":"publisher","DOI":"10.1137\/1132091"},{"key":"S0963548300000067_ref004","volume-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"S0963548300000067_ref038","doi-asserted-by":"crossref","unstructured":"[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\u2013195.","DOI":"10.1145\/800113.803648"},{"key":"S0963548300000067_ref013","volume-title":"Random Allocations","author":"Kolchin","year":"1978"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300000067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T22:27:37Z","timestamp":1558045657000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300000067\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,3]]}},"alternative-id":["S0963548300000067"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300000067","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,3]]}}}