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:
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
- 0012-365X
- language
- English
- LU publication?
- yes
- id
- 10796948-5437-4621-b987-559f0579c4f9 (old id 1782027)
- date added to LUP
- 2016-04-01 15:20:07
- date last changed
- 2021-01-10 05:07:50
@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}}, }