On the strength of connectedness of unions of random graphs

Let $G_1,\dots ,G_m$ be independent identically distributed random subgraphs of the complete graph ${\mathcal{K}}_n$. We analyse the threshold behaviour of the strength of connectedness of the union ${\cup }_{i=1}^m{G}_i$ defined on the vertex set of ${\mathcal{K}}_n$. Let $a=\min \{t\ge 1:\mathbf{P}\{\delta (G_1)=t>0\}\}$ be the minimal non zero vertex degree attained with positive probability. Given $k\ge 0$ let $\lambda (k)=\ln n+k\ln \frac{m}{n}-\frac{m}{n}\mathbf{E}X$, where $X$ stands for the number of non isolated vertices of $G_1$. Letting $n,m\to +\mathrm{\infty }$ we show that $\mathbf{P}\{{\cup }_{i=1}^m{G}_i$ is $a(k+1)$-connected$\}\to 1$ for $\lambda (k)\to -\mathrm{\infty }$, and $\mathbf{P}\{{\cup }_{i=1}^m{G}_i$ is $ak+1$-connected$\}\to 0$ for $\lambda (k)\to +\mathrm{\infty }$. In particular, the connectivity strength of the union graph ${\cup }_{i=1}^m{G}_i$ increases in steps of size $a$. Our results are obtained in a more general setting where the contributing random subgraphs do not need to be identically distributed.