On connectivity and robustness of random graphs with inhomogeneity

Abstract

The study of threshold functions has a long history in random graph theory. It is known that the thresholds for minimum degree k, k-connectivity, as well as k-robustness coincide for a binomial random graph. In this paper we consider an inhomogeneous random graph model, which is obtained by including each possible edge independently with an individual probability. Based on an intuitive concept of neighborhood density, we show two sufficient conditions guaranteeing k-connectivity and k-robustness, respectively, which are asymptotically equivalent. Our framework sheds some light on extending uniform threshold values in homogeneous random graphs to threshold landscapes in inhomogeneous random graphs.

1. Introduction

Classical binomial random graph theory founded in the late 1950s by Gilbert [9] and Erdős and Rényi [5, 6] considers the random graph model $G(n,p_n)$ of all graphs over the vertex set $V=\{1,2,\ldots,n\}$ , in which each edge $e_{ij}\in E$ appears independently with probability $p_n$ . Here $E=\{e_{ij}=e_{ji}\,:\, 1\le i\not=j\le n\}$ consists of all edges in the complete graph $K_n$ over V. The probability of a random graph in $G(n,p_n)$ holding a graph property is typically understood in the large graph limit as $n\rightarrow\infty$ . One of the most important results on random graphs, shown by Erdős and Rényi [6], is the following sharp threshold for k-connectivity. Recall that a graph G is said to be k-connected if it remains connected when any set of at most $k-1$ vertices is deleted.

Theorem 1. ([6].) Let $p_n=\frac1n(\!\ln n+(k-1)\ln \ln n+\omega_n)$ for an integer $k\ge1$ . Then

\begin{align*}& \lim_{n\rightarrow\infty}\mathbb{P}(G(n,p_n)\ \textit{is k-connected})\\ &\quad = \lim_{n\rightarrow\infty}\mathbb{P}(G(n,p_n)\ \textit{has minimum degree no less than k})\\&\quad =\begin{cases} 0 &\textit{if $\omega_n\rightarrow-\infty$,}\\1 &\textit{if $ \omega_n\rightarrow\infty$.}\end{cases}\end{align*}

The above type of zero–one law is known to be universal for all monotone properties in random graphs [7]. The theorem indicates that although having minimum degree at least k is weaker than k-connectedness, both properties share the same asymptotic threshold function (in this case $\frac1n(\!\ln n+(k-1)\ln \ln n)$ ).

Connectivity is a fundamental property of graph theory and is essential to many distributed computation problems over large-scale complex networks. For example, synchronization of oscillators or mobile agents is not possible without a connected underlying communication network. To cope with undesirable disturbances such as node faults and malicious attacks in realistic networked systems, a novel graph concept known as k-robustness was recently introduced by LeBlanc et al. [12] together with a class of distributed resilient consensus protocols called weighted-mean subsequence reduced (W-MSR) algorithms. In these algorithms, a node (or vertex) calculates its value in each iteration based on the current neighbors’ states and cuts the links with some neighbors that have extreme values. The notion of k-robustness (see Section 2 for the definition) of the communication network has been proposed as a sufficient condition to guarantee the global consensus of the network against malicious neighbors. This notion has been found to be central in a number of related network control protocols; see e.g. [13], [15], and [16]. In this context, a sufficiently connected but inadequately robust network is not able to deliver the consensus result. As will be seen below, k-robustness is a stronger property than k-connectivity. Interestingly, Zhang et al. [18] showed that Theorem 1 holds verbatim for k-robustness.

Theorem 2. ([18].) Let $p_n=\frac1n(\!\ln n+(k-1)\ln \ln n+\omega_n)$ for an integer $k\ge1$ . Then

\begin{align*}&\lim_{n\rightarrow\infty}\mathbb{P}(G(n,p_n)\ \textit{is k-robust})=\begin{cases} 0&\textit{if $\omega_n\rightarrow-\infty$,}\\ 1&\textit{if $ \omega_n\rightarrow\infty$.}\end{cases}\end{align*}

In other words, a random graph in $G(n,p_n)$ becomes k-robust as soon as it becomes k-connected (and as soon as its last vertex of degree $k-1$ vanishes).

The aforementioned threshold $\frac1n(\!\ln n+(k-1)\ln \ln n)$ is obviously precise and plain (note that Theorem 1 is a weaker statement than the result in [6]). However, would there be a possibility of zooming in and examining details of the threshold landscape (across all edges)? A natural way is to introduce unequal edge probabilities. To that end, in this paper we consider an inhomogeneous random graph with a list of edge probabilities $\textbf{p}_n=\{p_n(e_{ij})\}_{1\le i<j\le n}$ by including each edge $e_{ij}=e_{ji}$ of $K_n$ independently with probability $p_n(e_{ij})$ . We denote this inhomogeneous random graph model by $G(n,\textbf{p}_n)$ .

As an effort to diversify and extend previous results regarding binomial random graphs, it is not surprising that the $G(n,\textbf{p}_n)$ model has been studied by a few researchers across a relatively long time period under different names, e.g. generalized binomial random graphs [1, 11], anisotropic random graphs [4, 8], and edge-independent random graphs [3, 14]. We mention that Chapter 9 of the monograph [8] presents an updated survey of connectivity-related results for this and other inhomogeneous random graphs. In the seminal work [2], Bollobás et al. systematically analyzed a very general class of inhomogeneous random graphs and networks that were studied in recent decades.

In this paper we attempt to generalize the threshold result presented in Theorem 1 for both k-connectivity and k-robustness by considering the $G(n,\textbf{p}_n)$ model, and shed some light on the shape of the threshold landscape. We show two sufficient conditions for k-connectivity and k-robustness, which are asymptotically equivalent as $n\rightarrow\infty$ . It is hoped that the approach developed in the present work could facilitate relevant research in this direction on other topics in random graphs. The main results of this paper and their implications are discussed in Section 2 and proofs are given in Section 3.

2. Statements of main results and discussions

By convention, we will use standard Landau asymptotic notations such as ${\mathrm{O}}({\cdot})$ , ${\mathrm{o}}({\cdot})$ , $\Theta({\cdot})$ , $\sim$ , etc. throughout the paper; see e.g. [10]. For a simple, undirected graph $G=(V_G,E_G)$ with vertex set $V_G=\{1,2,\ldots, n\}$ and edge set $E_G$ , let $N_G(i)=\{j\in V_G\,:\, e_{ij}\in E_G\}$ be the set of neighbors (i.e. the open neighborhood) of vertex $i\in V_G$ . The degree of vertex i is denoted by $d_G(i)=|N_G(i)|$ . Let $\overline{N}_G(i)=\{i\}\cup N_G(i)$ be the closed neighborhood of i. We also define the neighborhood of a set $S\subseteq V_G$ as $N_G(S)=\{j\in V_G\,:\, e_{ij}\in E_G$ for some $ i \in S\}$ . As mentioned in the Introduction, the following notion of graph robustness was put forward in [12] to analyze the convergence of W-MSR algorithms in resilient control in the presence of adversaries.

Definition 1. ([12].) (a) For an integer $k\ge1$ and a graph $G=(V_G,E_G)$ , a subset $S\subseteq V_G$ is called k-reachable if there is some vertex $i\in S$ satisfying $|N_G(i)\backslash S|\ge k$ . (b) A graph G is called k-robust if, for any two non-empty, disjoint sets in $V_G$ , at least one of them is k-reachable.

From Definition 1 it is not difficult to see that k-robustness is a stronger property compared to k-connectedness in general. In fact, if a graph G is k-connected, for any two non-empty disjoint sets in $V_G$ , at least one of them has k neighbors (collectively) outside of the set itself. This does not guarantee k-reachability of either of these sets for $k\ge2$ . Generally, we have the following relationship between the three properties $\{ k{\text{-robustness}}\} \subseteq \{ k{\text{-connectedness}}\} \subseteq \{ {\text{minimum degree }}k\}$ , and for the binomial random graph $G(n,p_n)$ they share the same threshold function $p_n=\frac1n(\!\ln n+(k-1)\ln \ln n)$ .

To accommodate the inhomogeneous random graph setting, we consider the neighborhood density for a vertex $i\in V$ with respect to a set $S\subseteq V$ . For $i\in V\backslash S$ , define $\rho_n(i,S)=|S|^{-1}\sum_{j\in S}p_n(e_{ij})$ . This quantifies the expected fraction of neighbors of i inside S. Let $p_n=\frac{1}{n}(\!\ln n+(k-1)\ln \ln n+\omega_n)$ , where $k\ge1$ is an integer and $\omega_n\rightarrow\infty$ as $n\rightarrow\infty$ . For a constant $\beta \ge1$ , define

\begin{align*}\rho_n^{\beta }(i,S)=\dfrac{1}{|S|}\sum_{j\in S}\min\{p_n(e_{ij}),\beta p_n\}. \end{align*}

A sufficient condition ensuring k-connectivity and minimum degree k is formalized in the following.

Theorem 3. Suppose that there is some constant $\beta \ge1$ and an integer $k\ge1$ satisfies

(1) \begin{equation}\min_{1\le i\le n}\min_{\substack{S\,:\, i\not\in S\\ |S|\ge \lfloor n/2\rfloor}}\rho_n^{\beta }(i,S)\ge p_n\end{equation}

for all large n. Then

\begin{align*}&\lim_{n\rightarrow\infty}\mathbb{P}(G(n,\boldsymbol{{p}}_n)\ \textit{is k-connected})\\&\quad =\lim_{n\rightarrow\infty}\mathbb{P}(G(n, \boldsymbol{{p}}_n)\textit{has minimum degree no less than k})\\&\quad =1.\end{align*}

Theorem 3 is a generalization of the ‘one’ part of the zero–one law in Theorem 1, which can be seen by taking $p_n(e_{ij})\equiv p_n$ for all distinct $i, j\in V$ in Theorem 3. Roughly speaking, Theorem 3 says that if the edge probabilities are large enough, then the random graph $G(n,\textbf{p}_n)$ is sufficiently connected with high probability. The quantity $\rho_n^{\beta }(i,S)$ can be viewed as a capped neighborhood density with each potential edge contributing no more than $\beta p_n$ . If (1) holds for a constant $\beta $ then it holds for any larger $\beta $ . Moreover, if $\max_{i,j\in V}p_n(e_{ij})\le\beta p_n$ , then $\rho_n^{\beta }(i,S)=\rho_n(i,S)$ and (1) reduces to

(2) \begin{equation}\min_{1\le i\le n}\min_{\substack{S\,:\, i\not\in S\\ |S|\ge \lfloor n/2\rfloor}}\rho_n(i,S)\ge p_n\end{equation}

concerning the neighborhood density. Since k-connectivity and minimum degree no less than k are monotonic properties, without loss of generality we will only present the proofs in Section 3 under this maximum probability condition.

To appreciate the result presented above, we consider an example of non-trivial edge probabilities satisfying (1).

Example 1. To build an inhomogeneous random graph $G(n,\textbf{p}_n)$ , we consider the following assignment probabilities. For $1\le i<j\le \lfloor n^{\alpha}\rfloor$ for some $\alpha\in(0,1)$ , let $p_n(e_{ij})=0$ . For all other $1\le i<j\le n$ , let $p_n(e_{ij})=\frac{1}{n}(\!\ln n+(k-1)\ln \ln n+\omega_n)$ with $k\ge1$ and $\omega_n\rightarrow\infty$ . Let $\beta =1$ .

Notice that for any $S\subseteq V$ with $|S|\ge\lfloor n/2\rfloor$ and $i\in V\backslash S$ ,

\begin{align*}\rho_n^{\beta }(i,S)&\ge \dfrac{1}{|S|}\biggl(n^{\alpha}\cdot0+(|S|-n^{\alpha})\cdot\dfrac{\ln n+(k-1)\ln \ln n+\omega_n}{n}\biggr)\\&\ge \dfrac{\ln n+(k-1)\ln \ln n+\omega^{\prime}_n}{n},\end{align*}

where $\omega^{\prime}_n\rightarrow\infty$ as $n\rightarrow\infty$ . It is easy to see that (1) is satisfied and hence by Theorem 3 $G(n,\textbf{p}_n)$ is k-connected a.a.s. (i.e. asymptotically almost surely [10]). Loosely speaking, this example indicates that with a sublinear order portion of the graph being arbitrarily sparse and the rest of the graph k-connected, the entire graph can still be k-connected a.a.s.

The next example looks into a classical result regarding connectivity of $G(n,\textbf{p}_n)$ by Alon, which is sharp up to a multiplicative factor c.

Example 2. It is known [1] that for every constant $b>0$ there exists a constant $c>0$ so that if, for any $\emptyset\not=S\subset V$ ,

(3) \begin{align}\sum_{j\in S,\ i\in V\backslash S}p_n(e_{ij})\ge c\ln n,\end{align}

then

\begin{equation*}\mathbb{P}(G(n,\textbf{p}_n)\ \text{is connected})\ge1-n^{-b}.\end{equation*}

By dividing both sides of condition (3) by $|S|$ , we can rewrite it as

(4) \begin{align}\sum_{i\in V\backslash S}\rho_n(i,S)\ge\dfrac{c\ln n}{|S|}.\end{align}

Write

\begin{equation*}\rho_n(i)=(n-1)^{-1}\sum_{j\in V\backslash \{i\}}p_n(e_{ij})\end{equation*}

for the neighborhood density of a vertex $i\in V$ in the entire graph. Firstly, taking $S=V\backslash \{i\}$ , condition (2) becomes $\min_{i\in V}\rho_n(i)\ge\frac1n(\!\ln n+\omega_n)$ when $k=1$ , while (4) reduces to $\min_{i\in V}\rho_n(i)\ge\frac{c}{n}\ln n$ . As c is unknown, it is not difficult to see that these two conditions are incomparable in general. Secondly, the form of condition (4) takes a sum over all $i\not\in S$ , which mitigates the risk of uneven contribution of edge probabilities. Our condition (1) considers a single vertex i with minimum neighborhood density. Therefore we have to consider a cap on the contribution to neighborhood density. Finally, for a given random graph $G(n,\textbf{p}_n)$ , condition (3) is not always easy to check compared to (1) due to the undetermined constant c.

Next, we present our result for robustness.

Theorem 4. Suppose that there is some constant $\beta \ge1$ and an integer $k\ge1$ satisfies condition (1) for all large n. Then

\begin{align*}\lim_{n\rightarrow\infty}\mathbb{P}(G(n, \boldsymbol{{p}}_n)\ \textit{is k-robust})=1.\end{align*}

Several remarks are in order. Firstly, Theorem 4 can be viewed as a generalization of the ‘one’ part of the zero–one law Theorem 2 for robustness of binomial random graphs, which can be recovered by taking $p_n(e_{ij})\equiv p_n$ for all distinct $i, j\in V$ in Theorem 4.

Secondly, the same condition is adopted here as in Theorem 3 and analogous comments underneath it are applicable here. That said, k-robustness may be essentially stronger than k-connectedness in the current setting as we are not able to match a ‘zero’ part statement. As an example (which appeared in [18]) of a heterogeneously connected graph, we consider the union graph G of a complete bipartite graph $K_{n/2,n/2}$ and a perfect matching between the two partite sets. G has connectivity $n/2$ but is just 1-robust, suggesting that a gap might exist in the thresholds for connectivity and robustness in the $G(n,\textbf{p}_n)$ model.

Finally, it would be useful to perform some computational experiments to vouch for the above conjecture. Unfortunately, as shown in [17] and [18], determining robustness is significantly harder than checking connectivity, namely, NP-hard versus P in time complexity. The most current robustness-checking algorithm can only effectively handle graphs of order about $n=30$ .

Example 1 (revisited). For the model $G(n,\textbf{p}_n)$ set up in Example 1, we can argue in the same way and show that $G(n,\textbf{p}_n)$ is not only k-connected but k-robust a.a.s. by Theorem 4.

3. Proofs of Theorem 3 and Theorem 4

In this section we present the proofs of our main results. As mentioned above, we will assume $\max_{i,j\in V}p_n(e_{ij})\le\beta p_n$ for some constant $\beta \ge1$ and that condition (2) holds.

Proof of Theorem 3.Here we will actually rely on the following inequality instead of (2):

(5) \begin{equation}\min_{1\le i\le n}\min_{\substack{S\,:\, i\not\in S\\ |S|\ge \lfloor{(n-k+1)}/{2}\rfloor}}\rho_n(i,S)\ge p_n.\end{equation}

The minimum in condition (5) has the same asymptotic behavior as that in condition (2). In fact, although $\lfloor(n-k+1)/2\rfloor<\lfloor n/2\rfloor$ for any $k\ge1$ , the difference between the two terms is ${\mathrm{O}}(1)$ . Hence it can only make a difference of order ${\mathrm{O}}(n^{-1})$ to the right-hand side of (2) or (5).

For an integer $d\ge0$ , let $X_d$ be the random variable counting the number of vertices in $G(n,\textbf{p}_n)$ having degree d. Write $N_n(i)\,:\!=\, N_{G(n,\textbf{p}_n)}(i)$ and $\overline{N}_n(i)\,:\!=\, \overline{N}_{G(n,\textbf{p}_n)}(i)$ , respectively, for the open and closed neighborhood of vertex i in $G_{n,\textbf{p}_n}$ . Accordingly, we use $N^*_n(i)$ and $\overline{N}^*_n(i)$ to represent a potential instance of an open and closed neighborhood of i, respectively. By the construction of our inhomogeneous random graph model, we have

\begin{align*}\mathbb{E}X_d=\sum_{i=1}^n\sum_{N^*_n(i)\,:\, |N^*_n(i)|=d}\prod_{j\in N^*_n(i)}p_n(e_{ij})\prod_{j\in V\backslash \overline{N}^*_n(i)}(1-p_n(e_{ij})).\end{align*}

Capitalizing on the neighborhood density condition (5) and the estimate for binomial coefficient $\binom{n}{ d}=(1+{\mathrm{o}}(1))n^d/d!$ for fixed d as $n\rightarrow\infty$ , we obtain

(6) \begin{align}\mathbb{E}X_d &\le\sum_{i=1}^n\sum_{N^*_n(i)\,:\, |N^*_n(i)|=d}\beta ^dp_n^d {\mathrm{e}}^{-|V\backslash \overline{N}^*_n(i)|\cdot\rho_n(i,V\backslash \overline{N}^*_n(i))}\notag \\&\le n\binom{n-1}{ d}\beta ^dp_n^d {\mathrm{e}}^{-(n-1-d)p_n}\notag \\&\le (1+{\mathrm{o}}(1))n\cdot\dfrac{n^d}{d!}\beta ^d\dfrac{(\!\ln n)^d}{n^d}\cdot\dfrac{{\mathrm{e}}^{-\omega_n}}{n(\!\ln n)^{k-1}}\notag \\& =(1+{\mathrm{o}}(1))\dfrac{\beta ^d}{d!}\dfrac{(\!\ln n)^d {\mathrm{e}}^{-\omega_n}}{(\!\ln n)^{k-1}}.\end{align}

It follows from (6) that

(7) \begin{align}\sum_{d=0}^{k-2}\mathbb{E}X_d&\le (1+{\mathrm{o}}(1))\dfrac{{\mathrm{e}}^{-\omega_n}}{(\!\ln n)^{k-1}}\sum_{d=0}^{k-2}\beta ^d\dfrac{(\!\ln n)^d}{d!}\le (1+{\mathrm{o}}(1))\dfrac{{\mathrm{e}}^{-\omega_n}}{\ln n}(k-1)\beta ^{k-2}\end{align}

and

(8) \begin{align}\mathbb{E}X_{k-1}\le(1+{\mathrm{o}}(1))\dfrac{\beta ^{k-1}}{(k-1)!}\,{\mathrm{e}}^{-\omega_n}.\end{align}

Since k and $\beta $ are fixed constants and $\omega_n\rightarrow\infty$ as $n\rightarrow\infty$ , by (7) and (8) we obtain

\begin{equation*}\sum_{d=0}^{k-2}\mathbb{E}X_d={\mathrm{o}}(1)\quad\text{and}\quad\mathbb{E}X_{k-1}={\mathrm{o}}(1).\end{equation*}

Let $d^{\min}_n$ represent the minimum degree of $G(n,\textbf{p}_n)$ . Then $\mathbb{P}(d^{\min}_n\ge k)\rightarrow1$ as $n\rightarrow\infty$ by Markov’s inequality.

Notice that

\begin{align*}&\mathbb{P}(G(n,\textbf{p}_n)\ \text{is } k \text{-connected}) \ge\mathbb{P}(G(n,\textbf{p}_n)\ \text{is } k{\text{-connected}}\mid d^{\min}_n\ge k)\cdot\mathbb{P}(d^{\min}_n\ge k).\end{align*}

To show Theorem 3, it suffices to prove

(9) \begin{align}\lim_{n\rightarrow\infty}\mathbb{P}(G(n,\textbf{p}_n)\ \text{is }k{\text{-connected}}\mid d^{\min}_n\ge k)=1.\end{align}

Given two subsets $S_1,S_2\subseteq V$ satisfying $0\le|S_1|\le k-1$ and $k-|S_1|+1\le|S_2|\le\lceil\frac12(n-|S_1|)\rceil$ , consider an event

\begin{equation*}\mathcal{E}(S_1,S_2)=\{\text{$S_2$ is a connected component of $G(n,\textbf{p}_n)\backslash S_1$}\}.\end{equation*}

Notice that if $G(n,\textbf{p}_n)\backslash S_1$ is not connected, it must contain a component having order at most $\frac12(n-|S_1|)$ . In the following, we will bound the probability $P_{12}$ that there exist two vertex sets $S_1$ and $S_2$ such that the event $\mathcal{E}(S_1,S_2)$ occurs. For this purpose, without loss of generality, we assume $S_1$ is minimal for the given $S_2$ . This implies that each vertex in $S_1$ is adjacent to at least one vertex in $S_2$ (otherwise $S_1$ can be made smaller by removing a vertex without neighbors in $S_2$ ). Moreover, $N_{G(n,\textbf{p}_n)}(S_2)=S_1$ since $S_2$ is a component. Let $|S_1|=s_1$ and $|S_2|=s_2$ . Therefore we have

(10) \begin{align}P_{12}&\le \sum_{s_1=0}^{k-1}\sum_{s_2=k-s_1+1}^{(n-s_1)/2}\sum_{\substack{S_1\,:\,|S_1|=s_1\\ S_1\subseteq V}}\sum_{\substack{S_2\,:\, |S_2|=s_2\\ S_2\subseteq V}}\sum_{\substack{T\subseteq S_2\\ T \text{ is a spanning tree of $S_2$}}}\Biggl(\prod_{e_{ij}\in T}p_n(e_{ij})\Biggr)\notag \\&\quad \times \Biggl(\sum_{E^*_n(S_1,S_2)\,:\, |E^*_n(S_1,S_2)|=s_1}\prod_{\substack{i\,:\, i\in S_1\\ j\in S_2}}p_n(e_{ij})\Biggr)\cdot\prod_{e_{ij}\in E^*_n(V\backslash (S_1\cup S_2),S_2)}(1-p_n(e_{ij}))\notag \\&\le \sum_{s_1=0}^{k-1}\sum_{s_2=k-s_1+1}^{(n-s_1)/2}\sum_{\substack{S_1\,:\,|S_1|=s_1\\ S_1\subseteq V}}\sum_{\substack{S_2\,:\, |S_2|=s_2\\ S_2\subseteq V}}\sum_{\substack{T\subseteq S_2\\ T \text{ is a spanning tree of $ S_2$}}}(\beta p_n)^{s_2-1}\notag \\&\quad \times \Biggl(\sum_{E^*_n(S_1,S_2)\,:\, |E^*_n(S_1,S_2)|=s_1}(\beta p_n)^{s_1}\Biggr)\cdot {\mathrm{e}}^{-\sum_{e_{ij}\in E^*_n(V\backslash (S_1\cup S_2),S_2)}p_n(e_{ij})},\end{align}

where $E_n(S_1,S_2)=\{e_{ij}\in G(n,\textbf{p}_n)\,:\, i\in S_1, j\in S_2\}$ is the random edge set between two sets $S_1$ and $S_2$ , and $E^*_n(S_1,S_2)$ represents a potential instance accordingly. Using the neighborhood density assumption (1) and the relation $x-\lceil x/2\rceil=\lfloor x/2\rfloor$ for any non-negative integer x, we have

\begin{equation*}{\mathrm{e}}^{-\sum_{e_{ij}\in E_n(V\backslash (S_1\cup S_2),S_2)}p_n(e_{ij})}={\mathrm{e}}^{-\sum_{j\in S_2}\sum_{i\in V\backslash (S_1\cup S_2)}p_n(e_{ij})}\le {\mathrm{e}}^{-s_2(n-s_1-s_2)p_n}.\end{equation*}

Since $S_1$ is minimal for the given $S_2$ , $S_2$ must be connected. There are at most $s_2^{s_2-2}$ different labeled spanning trees over $S_2$ by Cayley’s formula. Hence the right-hand side of (10) is upper-bounded by

(11) \begin{equation}\sum_{s_1=0}^{k-1}\sum_{s_2=k-s_1+1}^{(n-s_1)/2}\binom{n}{s_1}\binom{n}{ s_2}s_2^{s_2-2}\binom{s_1s_2}{ s_1}(\beta p_n)^{s_1+s_2-1}\cdot{\mathrm{e}}^{-s_2(n-s_1-s_2)p_n}\,=\!:\, A_1+A_2,\end{equation}

where $A_1$ represents the value for $s_1=0$ and $A_2$ the sum for $1\le s_1\le k-1$ .

We first estimate $A_1$ . Recall $k\ge1$ and $\binom{n}{s_2}\le(n{\mathrm{e}}/s_2)^{s_2}$ . We have

\begin{align*}A_1&=\sum_{s_2=k+1}^{n/2}\binom{n}{ s_2}s_2^{s_2-2}(\beta p_n)^{s_2-1} {\mathrm{e}}^{-s_2(n-s_2)p_n}\\&\le(\beta p_n)^{-1}\sum_{s_2=k+1}^{\ln n}\bigl(n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n-s_2)p_n}\bigr)^{s_2} +(\beta p_n)^{-1}\sum_{s_2=1+\ln n}^{n/2}\bigl(n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n-s_2)p_n}\bigr)^{s_2}\\& \,:\!=\, A_{11}+A_{12}.\end{align*}

The term $n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n-s_2)p_n}$ in the above sums is less than 1. Using the definition of $p_n$ and $k\ge1$ , we obtain

\begin{align*}A_{11}&\le \dfrac{n}{\beta \ln n}\cdot(\!\ln n)\cdot\bigl(n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n-\ln n)p_n}\bigr)^{k+1}\\&=\dfrac{n}{\beta }\bigl((1+{\mathrm{o}}(1))\,{\mathrm{e}}\beta (\!\ln n) \,{\mathrm{e}}^{-(1+{\mathrm{o}}(1))\ln n}\bigr)^{k+1}\\&={\mathrm{o}}(1)\end{align*}

and

\begin{align*}A_{12}&\le \dfrac{n}{\beta \ln n}\sum_{s_2=1+\ln n}^{n/2}\bigl(n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n/2)p_n}\bigr)^{s_2}\\&\le \dfrac{n}{\beta \ln n}\sum_{s_2=1+\ln n}^{\infty}\bigl((1+{\mathrm{o}}(1))\,{\mathrm{e}}\beta (\!\ln n+(k-1)\ln \ln n+\omega_n) \cdot {\mathrm{e}}^{-{(\!\ln n+(k-1)\ln \ln n+\omega_n)}/{2}}\bigr)^{s_2}\\&=(1+{\mathrm{o}}(1))\dfrac{n}{\beta \ln n}\biggl((1+{\mathrm{o}}(1))\,{\mathrm{e}}\beta \cdot\dfrac{\ln n+(k-1)\ln \ln n+\omega_n}{{\mathrm{e}}^{{(\!\ln n+(k-1)\ln \ln n+\omega_n)}/{2}}}\biggr)^{1+\ln n}\\&={\mathrm{o}}(1).\end{align*}

Therefore $A_1=A_{11}+A_{12}={\mathrm{o}}(1)$ as $n\rightarrow\infty$ . Similarly, $A_2$ for $k\ge2$ can be estimated as follows:

\begin{align*}A_2&= \sum_{s_1=1}^{k-1}\sum_{s_2=k-s_1+1}^{(n-s_1)/2}\binom{n}{s_1}\binom{n}{ s_2}s_2^{s_2-2}\binom{s_1s_2}{ s_1}(\beta p_n)^{s_1+s_2-1}\cdot {\mathrm{e}}^{-s_2(n-s_1-s_2)p_n}\\&\le (\beta p_n)^{-1}\sum_{s_1=1}^{k-1}\sum_{s_2=k-s_1+1}^{(n-s_1)/2}\bigl(n{\mathrm{e}}^2s_2\beta p_n {\mathrm{e}}^{s_2p_n}\bigr)^{s_1}\cdot\bigl(n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n-s_2)p_n}\bigr)^{s_2}\\&= (\beta p_n)^{-1}\sum_{s_1=1}^{k-1}\sum_{s_2=k-s_1+1}^{\ln n}\bigl(n{\mathrm{e}}^2s_2\beta p_n {\mathrm{e}}^{s_2p_n}\bigr)^{s_1}\cdot\bigl(n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n-s_2)p_n}\bigr)^{s_2}\\&\quad +(\beta p_n)^{-1}\sum_{s_1=1}^{k-1}\sum_{s_2=1+\ln n}^{(n-s_1)/2}\bigl(n{\mathrm{e}}^2s_2\beta p_n {\mathrm{e}}^{s_2p_n}\bigr)^{s_1}\cdot\bigl(n{\mathrm{e}}\beta p_n {\mathrm{e}}^{-(n-s_2)p_n}\bigr)^{s_2}\\& \,:\!=\, A_{21}+A_{22},\end{align*}

where the estimate $\binom{n}{ s}\le(n{\mathrm{e}}/s)^s$ is used in the first inequality. Using the definition of $p_n$ we write

\begin{equation*}p_n=\frac{1}{n}(\!\ln n+(1+{\mathrm{o}}(1))(k-1)\ln \ln n)=(1+{\mathrm{o}}(1))\frac{\ln n}{n}.\end{equation*}

Therefore we derive

\begin{align*}A_{21}&= {\mathrm{O}}(1)\cdot\dfrac{n}{\ln n}\sum_{s_1=1}^{k-1}\sum_{s_2=k-s_1+1}^{\ln n}\bigl((1+{\mathrm{o}}(1))\beta {\mathrm{e}}^2s_2(\!\ln n)\cdot n^{{s_2}/{n}}(\!\ln n)^{{((1+{\mathrm{o}}(1))s_2(k-1))}/{n}}\bigr)^{s_1}\\&\quad \times\bigl((1+{\mathrm{o}}(1))\beta {\mathrm{e}}(\!\ln n)\cdot n^{{s_2}/{n}-1}(\!\ln n)^{(1+{\mathrm{o}}(1))(k-1)({s_2}/{n}-1)}\bigr)^{s_2}\\&= {\mathrm{O}}(1)\cdot\dfrac{n}{\ln n}\sum_{s_1=1}^{k-1}({\mathrm{O}}(\!\ln n))^{2s_1}\cdot\sum_{s_2=2}^{\ln n}\biggl({\mathrm{O}}\biggl(\dfrac{\ln n}{n}\biggr)\biggr)^{s_2}\\&\le nk(\!\ln n)^{2k}\cdot\biggl(\dfrac{\ln n}{n}\biggr)^2\\&={\mathrm{o}}(1),\end{align*}

where in the second equality above we note the limit $\lim_{n\rightarrow\infty}(n\ln n)^{{c\ln n}/{n}}=1$ for any positive constant c and $s_2\le\ln n$ . Likewise

\begin{align*}A_{22}&= {\mathrm{O}}(1)\cdot\dfrac{n}{\ln n}\sum_{s_1=1}^{k-1}\sum_{s_2=1+\ln n}^{(n-s_1)/2}\bigl((1+{\mathrm{o}}(1))\beta {\mathrm{e}}^2s_2(\!\ln n)\cdot n^{{s_2}/{n}}(\!\ln n)^{{((1+{\mathrm{o}}(1))s_2(k-1))}/{n}}\bigr)^{s_1} \\&\quad \times \bigl((1+{\mathrm{o}}(1))\beta {\mathrm{e}}(\!\ln n)\cdot n^{{s_2}/{n}-1}(\!\ln n)^{(1+{\mathrm{o}}(1))(k-1)({s_2}/{n}-1)}\bigr)^{s_2} \\&= {\mathrm{O}}(1)\cdot\dfrac{n}{\ln n}\sum_{s_1=1}^{k-1}\bigl({\mathrm{O}}\bigl(n^{{3}/{2}+{\mathrm{o}}(1)}\bigr)\bigr)^{s_1}\cdot\sum_{s_2=1+\ln n}^{(n-s_1)/2}\bigl({\mathrm{O}}\bigl(n^{-{1}/{2}+{\mathrm{o}}(1)}\bigr)\bigr)^{s_2} \\&\le \dfrac{nk}{\ln n}\bigl(n^{{3}/{2}+{\mathrm{o}}(1)}\bigr)^k\cdot\bigl(n^{-{1}/{2}+{\mathrm{o}}(1)}\bigr)^{1+\ln n}\\&={\mathrm{o}}(1),\end{align*}

where in the second equality above we note the relationship $(\!\ln n)^{c}=n^{{\mathrm{o}}(1)}$ for any positive constant c and $s_2\le n/2$ . Therefore $A_2=A_{21}+A_{22}={\mathrm{o}}(1)$ as $n\rightarrow\infty$ . It follows from (11) that $P_{12}\le A_1+A_2={\mathrm{o}}(1)$ .

Recall that $G(n,\textbf{p}_n)\backslash S_1$ contains a component having order no more than $\frac12(n-|S_1|)$ if it is not connected. Moreover, when $d^{\min}_n\ge k$ , any vertex in $S_1$ has no less than $k-|S_1|+1$ neighbors outside $S_1$ . Recalling the definition of the event $\mathcal{E}(S_1,S_2)$ , we know that the probability $P_{12}={\mathrm{o}}(1)$ implies that if $d^{\min}_n\ge k$ then a.a.s. $G(n,\textbf{p}_n)$ is k-connected. Hence (9) holds true. The proof of Theorem 3 is completed.

Proof of Theorem 4.Arguing similarly as in the beginning of Theorem 3, here we will rely on the following inequality instead of (2):

(12) \begin{equation}\min_{1\le i\le n}\min_{\substack{S\,:\, i\not\in S\\ |S|\ge \lceil n/2\rceil-k+1}}\rho_n(i,S)\ge p_n.\end{equation}

In view of Definition 1, it suffices to show that

\begin{equation*}\mathbb{P}({\text{any non-empty set $S\subseteq V$ with $|S|\le\lfloor n/2\rfloor$ is} \,k\text{-reachable in $G(n,\textbf{p}_n)$})\rightarrow1\ \text{as $n\rightarrow\infty$.}}\end{equation*}

Let $P_0$ be the probability that some set of size no more than $\lfloor n/2\rfloor$ is not k-reachable. Furthermore, let $P_l$ represent the probability that some set of size $l\ge1$ is not k-reachable in $G(n,\textbf{p}_n)$ . Fix a set $S\in V$ with $|S|=l$ . For any vertex $i\in S$ ,

\begin{align*}&\mathbb{P}(i \text{ has less than } k \text{ neighbors in $V\backslash S$})\\&\quad =\sum_{r=0}^{k-1}\sum_{N_n(i)\backslash S\,:\, |N_n(i)\backslash S|=r}\prod_{j\in N_n(i)\backslash S}p_n(e_{ij})\prod_{j\in V\backslash (S\cup N_n(i))}(1-p_n(e_{ij}))\\&\quad \le\sum_{r=0}^{k-1}\sum_{N_n(i)\backslash S\,:\, |N_n(i)\backslash S|=r}(\beta p_n)^r {\mathrm{e}}^{-|V\backslash (S\cup N_n(i))|\cdot\rho_n(i,V\backslash (S\cup N_n(i)))}\\&\quad \le\sum_{r=0}^{k-1}\binom{n-l}{ r}(\beta p_n)^r {\mathrm{e}}^{-(n-l-r)p_n},\end{align*}

where we used the neighborhood density condition (12). Since $\binom{n-l}{ r}\le n^r$ , the above probability is bounded from above by $k(n\beta p_n {\mathrm{e}}^{p_n})^{k-1}\cdot {\mathrm{e}}^{-(n-l)p_n}$ . By independence, the probability that S is not k-reachable is at most $\bigl(k(n\beta p_n {\mathrm{e}}^{p_n})^{k-1}\cdot{\mathrm{e}}^{-(n-l)p_n}\bigr)^l$ . Therefore

(13) \begin{align}P_l&\le \binom{n}{ l}\bigl(k(n\beta p_n {\mathrm{e}}^{p_n})^{k-1}\cdot{\mathrm{e}}^{-(n-l)p_n}\bigr)^l \le \biggl(\dfrac{{\mathrm{e}} kn}{l}(n\beta p_n {\mathrm{e}}^{p_n})^{k-1}\cdot{\mathrm{e}}^{-(n-l)p_n}\biggr)^l.\end{align}

Using the assumption of $p_n$ , the right-hand side of (13) equals

(14) \begin{align}&\biggl(\dfrac{{\mathrm{e}} k}{l}(\beta (\!\ln n+(k-1)\ln \ln n+\omega_n)\,{\mathrm{e}}^{p_n})^{k-1}\dfrac{1}{(\!\ln n)^{k-1}}\,{\mathrm{e}}^{lp_n-\omega_n}\biggr)^l \le(C\varphi(l)\,{\mathrm{e}}^{-\omega_n})^l,\end{align}

where $C>0$ is a constant and the function $\varphi(l)\,:\!=\, {\mathrm{e}}^{lp_n}/l$ . A quick study of $\varphi$ , when seen as a function of a real variable in the interval $[1, n/2]$ , shows that it is convex and hits its minimum at $p_n^{-1}$ . Thus its maximum is either $\varphi(1)={\mathrm{e}}^{p_n}$ or $\varphi(n/2)={\mathrm{O}}({1}/{\sqrt{n}})$ . It follows from (13) and (14) that $P_l\le(C{\mathrm{e}}^{1-\omega_n})^l$ .

Finally, an application of the union bound yields

\begin{align*} P_0\le\sum_{l=1}^{n/2} (C {\mathrm{e}}^{1-\omega_n})^l\le\sum_{l=1}^{\infty} (C {\mathrm{e}}^{1-\omega_n})^l=\dfrac{C {\mathrm{e}}^{1-\omega_n}}{1-C{\mathrm{e}}^{1-\omega_n}}={\mathrm{o}}(1)\end{align*}

as $n\rightarrow\infty$ , i.e. $\omega_n\rightarrow\infty$ . This completes the proof of Theorem 4.