Summary
LetG be a graph and letX n count copies ofG in a random graphK(n,p). The random variable\(\left( {X_n - E\left( {X_n } \right)} \right)/\sqrt {Var\left( {X_n } \right)} \) is asymptotically normally distributed if and only ifnp m→∞ andn 2 (1-p)→∞, wherem=max {e(H)/|H|:H∪G}. In addition to, and in connection with this main result we investigate the formula for Var (X n ) and the Poisson convergence ofX n .
Article PDF
Similar content being viewed by others
References
Barbour, A.: Poisson convergence and random graphs. Math. Proc. Camb. Philos. Soc.92, 349–359 (1982)
Bollobás, B.: Threshold functions for small subgraphs. Math. Proc. Camb. Philos. Soc.90, 187–206 (1981)
Chow, Y.S., Teicher, H.: Probability theory. Springer Verlag, Berlin Heidelberg New York: 1978
Györi, E., Rothschild, B., Ruciński, A.: Every graph is contained in a sparsest possible balanced graph. Math. Proc. Camb. Philos. Soc.98, 397–401 (1985)
Karoński, M.: Balanced subgraphs of large random graphs. Poznań: AMU Press 1984
Karoński, M., Ruciński, A.: On the number of strictly balanced subgraphs of a random graph. In: Borowiecki, M., Kennedy, J.W., Syslo, M.M. (eds.). Proceedings of conference held in Lagów, Poland, 1981. Lect. Notes Math., vol. 1018, pp. 79–83. Berlin Heidelberg New York: Springer 1983
Maehara, H.: On random simplices in product distributions. J. Appl. Probab.17, 553–558 (1980)
Nowicki, K., Wierman, J.: Subgraph counts in random graphs using incomplete U-statistics method. Technical report. Lund 1986
Ruciński, A., Vince, A.: Strongly balanced graphys and random graphs. J. Graph Theory10, 251–264 (1986)
Ruciński, A., Vince, A.: Balanced graphs and the problem of subgraphs of random graphs, Congr. Numerantium49, 181–190 (1985)
Ruciński, A.: Small subgraphs of a random graph (a survey), Proceedings of conference “Random graphs '87” held in Poznań, 1987, submitted
Author information
Authors and Affiliations
Additional information
Part of the research was done during the author's stay in Division of Mathematics and Science, St. John's University, Staten Island, New York
Rights and permissions
About this article
Cite this article
Ruciński, A. When are small subgraphs of a random graph normally distributed?. Probab. Th. Rel. Fields 78, 1–10 (1988). https://doi.org/10.1007/BF00718031
Issue Date:
DOI: https://doi.org/10.1007/BF00718031