Connectivity threshold for superpositions of Bernoulli random graphs

Abstract

Let $G_1,\dots ,G_m$ be independent Bernoulli random subgraphs of the complete graph ${\mathcal{K}}_n$ having variable sizes $x_1,\dots ,x_m\in [n]$ and densities $q_1,\dots ,q_m\in [0,1]$. Letting $n,m\to +\infty$, we study the connectivity threshold for the union ${\cup }_{i=1}^m{G}_i$ defined on the vertex set of ${\mathcal{K}}_n$. Assuming that the empirical distribution $P_{n,m}$ of the pairs $(x_1,q_1),\dots ,(x_m,q_m)$ converges to a probability distribution $P$ we show that the threshold is defined by the mixed moments ${\kappa }_n=\iint x(1-(1-q{)}^{|x-1|})P_{n,m}(dx,dq)$. For $\ln n-\frac{m}{n}{\kappa }_n\to -\infty$ we have $P\{{\cup }_{i=1}^m{G}_i$ is connected$\}\to 1$ and for $\ln n-\frac{m}{n}{\kappa }_n\to +\infty$ we have $P\{{\cup }_{i=1}^m{G}_i$ is connected$\}\to 0$. Interestingly, this dichotomy only holds if the mixed moment $\iint x(1-(1-q{)}^{|x-1|})\ln (1+x)P(dx,dq)<\infty$.

In the revised version several misprints have been corrected. Corrections are in red. Appendix with auxiliary results has been added