Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
and
organization
publishing date
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&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}},
}