A Note on the Conductance of the Binomial Random Intersection Graph

摘要

We establish the rapid mixing property of a binomial random intersection graph G (n,m,p) introduced in [11,17]. For this purpose we show that the conductance is bounded away from zero by a positive constant. We consider the range of parameters n, m, p where the edge density is just above the connectivity threshold (our graph is connected with high probability as n,m → +∞). We assume in addition that np = Θ(1).