The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Subgraph counts in random graphs using incomplete U-statistics methods

På svenska

Author

Summary, in English

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.

Publishing year

1988

Language

English

Pages

299-310

Publication/Series

Discrete Mathematics

Volume

72

Document type

Journal article

Publisher

Elsevier

Topic

  • Probability Theory and Statistics

Status

Published

ISBN/ISSN/Other

  • ISSN: 0012-365X