Poisson approximation of counts of subgraphs in random intersection graphs

2016/09/06 by Rybarczyk, Katarzyna, Stark, Dudley
#05C80 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1609.01699

Abstract

Random intersection graphs are characterized by three parameters: n, m and p, where n is the number of vertices, m is the number of objects, and p is the probability that a given object is associated with a given vertex. Two vertices in a random intersection graph are adjacent if and only if they have an associated object in common. When m=\lfloor n^α\rfloor for constant α, we provide a condition, called \em strictly α-balanced, for the Poisson convergence of the number of induced copies of a fixed subgraph.

Related

• Normal approximation for number of edges in random intersection graphs
• On the intersection of pairs of trees
• Inhomogeneous random graphs, isolated vertices, and Poisson approximation
• Poisson approximation for cycles in the generalised random graph
• Multivariate Poisson approximation of joint subgraph counts in random graphs via size-biased couplings