{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T21:39:55Z","timestamp":1775079595210,"version":"3.50.1"},"reference-count":34,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5884,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1990,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For each of the two models of a sparse random graph on <jats:italic>n<\/jats:italic> vertices, <jats:italic>G(n, #<\/jats:italic> of edges = <jats:italic>cn<\/jats:italic>\/2) and <jats:italic>G<\/jats:italic>(<jats:italic>n, Prob (edge) = c\/n) define t<jats:sub>n<\/jats:sub>(k) as the total number of tree components of size k (1 \u2264 k \u2264 n). the random sequence {[t<jats:sub>n<\/jats:sub>(k) \u2010 nh(k)]n<jats:sup>\u22121\/2<\/jats:sup>} is shown to be Gaussian in the limit n \u2192\u221e, with h(k) = k<jats:sup>k\u22122<\/jats:sup>c<jats:sup>k\u22121<\/jats:sup>e<jats:sup>\u2212kc<\/jats:sup>\/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c&gt; 1, the size of the giant component is asymptotically Gaussian, with mean n\u03b8(c) and variance n(1 \u2212 T)<jats:sup>\u22122<\/jats:sup>(1 \u2212 2T\u03b8)\u03b8(1 \u2212 \u03b8) for the first model and n(1 \u2212 T)<jats:sup>\u22122<\/jats:sup>\u03b8(1 \u2212 \u03b8)<\/jats:italic> for the second model. Here <jats:italic>Te<jats:sup>\u2212T<\/jats:sup><\/jats:italic> = <jats:italic>ce<jats:sup>\u2212c<\/jats:sup><\/jats:italic>, <jats:italic>T<\/jats:italic>&lt;1, and \u03b8 = 1 \u2212 <jats:italic>T\/c<\/jats:italic>. A close technique allows us to prove that, for <jats:italic>c<\/jats:italic> &lt; 1, the independence number of <jats:italic>G(n, p = c\/n)<\/jats:italic> is asymptotically Gaussian with mean <jats:italic>nc<\/jats:italic><jats:sup>\u22121<\/jats:sup>(<jats:italic>\u03b2 + \u03b2<jats:sup>2<\/jats:sup>\/2<\/jats:italic>) and variance <jats:italic>n<\/jats:italic>[<jats:italic>c<\/jats:italic><jats:sup>\u22121<\/jats:sup>(\u03b2 + \u03b2<jats:sup>2<\/jats:sup>\/2) \u2212<jats:italic>c<\/jats:italic><jats:sup>\u22122<\/jats:sup>(<jats:italic>c<\/jats:italic> + 1)\u03b2<jats:sup>2<\/jats:sup>], where <jats:italic>\u03b2e<jats:sup>\u03b2<\/jats:sup><\/jats:italic> = c. It is also proven that almost surely the giant component consists of a giant two\u2010connected core of size about <jats:italic>n<\/jats:italic>(1 \u2212 <jats:italic>T<\/jats:italic>)\u03b2 and a \u201cmantle\u201d of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.<\/jats:p>","DOI":"10.1002\/rsa.3240010306","type":"journal-article","created":{"date-parts":[[2007,5,31]],"date-time":"2007-05-31T08:20:37Z","timestamp":1180599637000},"page":"311-342","source":"Crossref","is-referenced-by-count":71,"title":["On tree census and the giant component in sparse random graphs"],"prefix":"10.1002","volume":"1","author":[{"given":"Boris","family":"Pittel","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579172"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/3212323"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.2307\/1426205"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100059995"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.2307\/1426620"},{"key":"e_1_2_1_7_2","volume-title":"Convergence of Probability Measures","author":"Billingsley P.","year":"1968"},{"key":"e_1_2_1_8_2","first-page":"35","volume-title":"Proc. Cambridge Combinatorial Conf. in Honour of Paul Erd\u00f6s","author":"Bollob\u00e1s B.","year":"1984"},{"key":"e_1_2_1_9_2","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","year":"1985"},{"key":"e_1_2_1_10_2","first-page":"534","article-title":"Poisson approximation for dependent trials","volume":"3","author":"Chen L. H. Y.","journal-title":"Ann. Prob."},{"key":"e_1_2_1_11_2","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u00f6s P.","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90039-6"},{"key":"e_1_2_1_13_2","first-page":"79","volume-title":"Lecture Notes in Mathematics","author":"Karo\u0144ski M."},{"key":"e_1_2_1_14_2","unstructured":"R. M.Karp(1988).The transitive closure of a random digraph(private communication)."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010102"},{"key":"e_1_2_1_16_2","first-page":"7","article-title":"Large trees in random graphs","volume":"28","author":"Ku\u0144era L.","year":"1987","journal-title":"Commun. Math. Univ. Carolinae"},{"key":"e_1_2_1_17_2","unstructured":"T.\u0141uczak The size of the largest hole in a random graph J. Comb. Theory Ser. B. submitted."},{"key":"e_1_2_1_18_2","unstructured":"T.\u0141uczak On the size and connectivity of thek\u2010core of a random graph Discrete Math. submitted."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90215-4"},{"key":"e_1_2_1_20_2","unstructured":"T.\u0141uczak B.PittelandJ. C.Wierman The structure of a random graph near the point of the phase transition in preparation."},{"key":"e_1_2_1_21_2","first-page":"335","article-title":"The expected node\u2010independence number of random trees","volume":"35","author":"Meir A.","year":"1974","journal-title":"Nederl. Akad. Wetensch. Proc. Ser. Indag. Math."},{"key":"e_1_2_1_22_2","volume-title":"Counting Labelled Trees, Canadian Mathematical Congress","author":"Moon J. W."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100060205"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.2307\/2001158"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.2307\/3214592"},{"key":"e_1_2_1_26_2","volume-title":"Probability in Banacl: Spaces 7","author":"Pittel B.","year":"1989"},{"key":"e_1_2_1_27_2","unstructured":"B.Pittel W.Woyczy\u0144skiandJ. A.Mann Random tree\u2010type partitions as a model for acyclic polymerization: Gaussian behaviour of the subcritical sol phase Proc. Third Int. Seminar on Random Graphs and Probabilistic Methods in Combinatorics Pozna\u0144 Poland 1987 to appear."},{"key":"e_1_2_1_28_2","article-title":"Random tree\u2010type partitions as a model of acyclic polymerization: Holtsmark (3\/2\u2010stable) distribution of the supercritical gel","author":"Pittel B.","journal-title":"Ann. Prob."},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400854332"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00718031"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/16\/4\/014"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.2307\/1427224"},{"key":"e_1_2_1_33_2","first-page":"583","article-title":"A bound for the error in the normal approximation to the distribution of a sum of dependent random variables","volume":"2","author":"Stein C.","year":"1970","journal-title":"Proc. Sixth Berkeley Symp. Math. Stat. Prob."},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1115004"},{"key":"e_1_2_1_35_2","unstructured":"W. Fernandezde la Vega Induced trees in sparse random graphs Research Report 214 CNRS 1985."}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240010306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240010306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T09:49:11Z","timestamp":1697968151000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240010306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,9]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,9]]}},"alternative-id":["10.1002\/rsa.3240010306"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240010306","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,9]]}}}