A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
复制标题
随机图非重叠平衡子图的相关不等式和泊松极限定理
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Stephen Suen
中科院分区：
文献类型：
--
作者：
Stephen Suen
考虑随机图Kn，p（n）中固定阶的非重叠子图。固定一个严格强平衡图G. Kn，p（n）中同构于G的子图称为G-子图。设Xn是Kn，p（n）的G-子图的个数，p（n）与所有其它G-子图不相交。证明了当n→时E[Xn]→∞，则Xn/E[Xn]依概率收敛于1.当n→∞时，E[Xn]→c，则Xn满足泊松极限定理。泊松极限定理是用一个类似于Janson、J.S.和Rucinski[8]以及Boppana和Spencer [4]中出现相关不等式来证明的。
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 Rucinski[8] and Boppana and Spencer [4].