zbMATH — the first resource for mathematics

A functional limit theorem for random graphs with applications to subgraph count statistics. (English) Zbl 0708.05052
Summary: We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. The proof is based on a martingale convergence theorem. The evolving random graph allows us to study both the random graph model \(K_{n,p}\), by fixing attention to a fixed time, and the model \(K_{n,N}\), by studying it at the random time it contains exactly n edges. In particular, we obtain the asymptotic distribution as \(n\to \infty\) of the number of subgraphs isomorphic to a given graph G, both for \(K_{n,p}\) (p fixed) and \(K_{n,N}\left(N/(\begin{matrix} n\\ 2\end{matrix} \right)\to p)\). The results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for \(K_{n,N}\); the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. In some exceptional cases, the limit distribution is not normal.

05C80 Random graphs (graph-theoretic aspects)
60F17 Functional limit theorems; invariance principles
Full Text: DOI
[1] Convergence of Probability Measures, Wiley, New York, 1968. · Zbl 0172.21201
[2] and , The asymptotic distribution of generalized U-statistics with applications to random graphs Tech. Report, Univ. Lund (1988).
[3] Ruciński, Prob. Th. Rel. Fields 78 pp 1– (1988)
[4] and , A central limit theorem for decomposable random variables with applications to random graphs, J. Comb. Theory B. (1988).
[5] and , Limit Theorems for Stochastic Processes, Springer, Berlin, 1987. · Zbl 0635.60021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.