A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
Author:
- 1 June 1990
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 1 (2) , 231-242
Abstract
We consider non‐overlapping subgraphs of fixed order in the random graph Kn, p(n). Fix a strictly strongly balanced graph G. A subgraph of Kn, p(n) isomorphic to G is called a G‐subgraph. Let Xn be the number of G‐subgraphs of Kn, p(n) vertex disjoint to all other G‐subgraphs. We show that if E[Xn]→∞ as n→, then Xn/E[Xn] converges to 1 in probability. Also, if E[Xn]→c as n→∞, then Xn satisfies a Poisson limit theorem. the Poisson limit theorem is shown using a correlation inequality similar to those appeared in Janson, Łuczak, and Ruciñski[8] and Boppana and Spencer [4].Keywords
This publication has 7 references indexed in Scilit:
- A useful elementary correlation inequalityJournal of Combinatorial Theory, Series A, 1989
- Bonferroni-type inequalitiesAdvances in Applied Probability, 1987
- Strongly balanced graphs and random graphsJournal of Graph Theory, 1986
- A review of random graphsJournal of Graph Theory, 1982
- Poisson convergence and random graphsMathematical Proceedings of the Cambridge Philosophical Society, 1982
- Threshold functions for small subgraphsMathematical Proceedings of the Cambridge Philosophical Society, 1981
- Limit theorems for complete subgraphs of random graphsPeriodica Mathematica Hungarica, 1979