Premium
A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
Author(s) -
Suen W. C. Stephen
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240010210
Subject(s) - mathematics , combinatorics , disjoint sets , poisson distribution , random graph , discrete mathematics , graph , vertex (graph theory) , limit (mathematics) , central limit theorem , mathematical analysis , statistics
We consider non‐overlapping subgraphs of fixed order in the random graph K n , p ( n ). Fix a strictly strongly balanced graph G . A subgraph of K n, p ( n) isomorphic to G is called a G ‐subgraph. Let X n be the number of G ‐subgraphs of K n, p ( n) vertex disjoint to all other G ‐subgraphs. We show that if E[ X n ]→∞ as n →, then X n /E[ X n ] converges to 1 in probability. Also, if E[ X n ]→ c as n →∞, then X n 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].