Du är här

Subgraph counts in random graphs using incomplete U-statistics methods

Författare:
Publiceringsår: 1988
Språk: Engelska
Sidor: 299-310
Publikation/Tidskrift/Serie: Discrete Mathematics
Volym: 72
Dokumenttyp: Artikel
Förlag: Elsevier Science B.V.

Sammanfattning

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.

Disputation

Nyckelord

  • Mathematics and Statistics

Övriga

Published
Yes
  • ISSN: 0012-365X

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

 

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen