Poisson Approximation of the Number of Cliques in Random Intersection Graphs
Katarzyna Rybarczyk, Dudley Stark · Journal of Applied Probability · 2010
A random intersection graphG(n,m,p) is defined on a setVofnvertices. There is an auxiliary setWconsisting ofmobjects, and each vertexv∈Vis assigned a random subset of objectsWv⊆Wsuch thatw∈Wvwith probabilityp, independently for allv∈Vand allw∈W. Given two verticesv1,v2∈V, we setv1∼v2if and only ifWv1∩Wv2≠ ∅. We use Stein's method to obtain an upper bound on the total variation distance between the distribution of the number ofh-cliques inG(n,m,p) and a related Poisson distribution for any fixed integerh.