Connectivity of inhomogeneous random graphs II

Abstract

Each graphon $W:\hat{I}{\text{c◯}}^2\to [0,1]$ yields an inhomogeneous random graph model $G(n,W)$. We show that $G(n,W)$ is asymptotically almost surely connected if and only if (i) $W$ is a connected graphon and (ii) the measure of elements of $\hat{I}\text{c◯}$ of $W$-degree less than $\hat{I}\pm$ is $o(\hat{I}\pm )$ as $\hat{I}\pm \to 0$. These two conditions encapsulate the absence of several linear-sized components, and of isolated vertices, respectively. We study in bigger detail the limit probability of the property that $G(n,W)$ contains an isolated vertex, and, more generally, the limit distribution of the minimum degree of $G(n,W)$.

22 pages, 3 figures