Subgraph counts in random graphs using incomplete Ustatistics methods
(1988) In Discrete Mathematics 72. p.299310 Abstract
 The random graph Kn,p is constructed on n labelled vertices by inserting each of the (n2) possible edges independently with probability p, 0> p < 1. For a fixed graph G, the threshold function for existence of a subgraph of Kn,p isomorphic to G has been determined by Erdös and Rényi [8] and Bollobás [3]. Bollobás [3] and Karo ski [14] have established asymptotic Poisson and normal convergence for the number of subgraphs of Kn,p isomorphic to G for sequences of p(n)→0 which are slightly greater than the threshold function. We use techniques from asymptotic theory in statistics, designed to study sums of dependent random variables known as Ustatistics. We note that a subgraph count has the form of an incomplete Ustatistics, and prove... (More)
 The random graph Kn,p is constructed on n labelled vertices by inserting each of the (n2) possible edges independently with probability p, 0> p < 1. For a fixed graph G, the threshold function for existence of a subgraph of Kn,p isomorphic to G has been determined by Erdös and Rényi [8] and Bollobás [3]. Bollobás [3] and Karo ski [14] have established asymptotic Poisson and normal convergence for the number of subgraphs of Kn,p isomorphic to G for sequences of p(n)→0 which are slightly greater than the threshold function. We use techniques from asymptotic theory in statistics, designed to study sums of dependent random variables known as Ustatistics. We note that a subgraph count has the form of an incomplete Ustatistics, and prove asymptotic normality of subgraph counts for a wide range of values of p, including any constant p and sequences of p(n) tending to 0 or 1 sufficiently slowly. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1782027
 author
 Nowicki, Krzysztof ^{LU} and Wierman, John
 organization
 publishing date
 1988
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Discrete Mathematics
 volume
 72
 pages
 299  310
 publisher
 Elsevier
 external identifiers

 scopus:38249028674
 ISSN
 0012365X
 language
 English
 LU publication?
 yes
 id
 1079694854374621b987559f0579c4f9 (old id 1782027)
 date added to LUP
 20160401 15:20:07
 date last changed
 20201129 04:16:01
@article{1079694854374621b987559f0579c4f9, abstract = {The random graph Kn,p is constructed on n labelled vertices by inserting each of the (n2) possible edges independently with probability p, 0> p < 1. For a fixed graph G, the threshold function for existence of a subgraph of Kn,p isomorphic to G has been determined by Erdös and Rényi [8] and Bollobás [3]. Bollobás [3] and Karo ski [14] have established asymptotic Poisson and normal convergence for the number of subgraphs of Kn,p isomorphic to G for sequences of p(n)→0 which are slightly greater than the threshold function. We use techniques from asymptotic theory in statistics, designed to study sums of dependent random variables known as Ustatistics. We note that a subgraph count has the form of an incomplete Ustatistics, and prove asymptotic normality of subgraph counts for a wide range of values of p, including any constant p and sequences of p(n) tending to 0 or 1 sufficiently slowly.}, author = {Nowicki, Krzysztof and Wierman, John}, issn = {0012365X}, language = {eng}, pages = {299310}, publisher = {Elsevier}, series = {Discrete Mathematics}, title = {Subgraph counts in random graphs using incomplete Ustatistics methods}, volume = {72}, year = {1988}, }