Advanced

Subgraph counts in random graphs using incomplete U-statistics methods

Nowicki, Krzysztof LU and Wierman, John (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:
author
organization
publishing date
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
2016-04-16 02:50:59
@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&gt; p &lt; 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},
}