Subgraph counts in random graphs using incomplete U-statistics methods
(1988) In Discrete Mathematics 72. p.299-310- 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 U-statistics. We note that a subgraph count has the form of an incomplete U-statistics, 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 U-statistics. We note that a subgraph count has the form of an incomplete U-statistics, 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:
http://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
- ISSN
- 0012-365X
- language
- English
- LU publication?
- yes
- id
- 10796948-5437-4621-b987-559f0579c4f9 (old id 1782027)
- date added to LUP
- 2011-02-03 17:27:34
- date last changed
- 2018-05-29 11:38:48
@article{10796948-5437-4621-b987-559f0579c4f9, 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 U-statistics. We note that a subgraph count has the form of an incomplete U-statistics, 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 = {0012-365X}, language = {eng}, pages = {299--310}, publisher = {Elsevier}, series = {Discrete Mathematics}, title = {Subgraph counts in random graphs using incomplete U-statistics methods}, volume = {72}, year = {1988}, }