The strong component structure of the barely subcritical directed configuration model

Let $\mathbf{d}_{n}=(\mathbf{d}_{n}^{-},\mathbf{d}_{n}^{+})=((d_{1}^{-},d_{1}^{+}),\ldots,(d_{n}^{-},d_{n}^{+}))$ be a directed degree sequence on $n$ vertices and let $m_{n}=\sum d_{i}^{-}=\sum d_{i}^{+}$. The directed configuration model on $\mathbf{d}_{n}$, introduced by Cooper and Frieze [3], is the random directed multigraph on $[n]$ obtained by associating with vertex $i$ $d_{i}^{-}$ in-stubs and $d_{i}^{+}$ in-stubs, and then choosing a perfect matching of in- and out- stubs uniformly at random. We will denote this model by $G(\mathbf{d}_{n})$. This is a directed generalisation of the configuration model of Bollobás [1] which since its introduction has become one of the most widely used random graph models.

A strongly connected component in a digraph is a maximal sub-digraph such that there exists a directed path between each ordered pair of vertices. In this paper we will consider the size of the largest strongly connected component in the barely subcritical regime. Note that these components are much smaller than the connected components which are found in the undirected case. This is due to the fact that the minimal strongly connected components are directed cycles as opposed to the trees in the directed case and so we require one additional edge on the same vertex set. We shall call any strongly connected digraph which is not a cycle complex. Note that any such digraph has strictly more edges than vertices.

Let $n_{k,\ell}$ be the number of copies of $(k,\ell)$ in $\mathbf{d}_{n}$ and let $\Delta_{n}=\max(d_{i}^{-},d_{i}^{+})$ be the maximum degree of $\mathbf{d}_{n}$. Also, define the following parameters of the degree distribution. These parameters govern the behaviour of the size of the largest strongly connected component.

It was shown by Cooper and Frieze [3] that $Q_{n}=0$ is the threshold for the existence of a giant strongly connected component under some mild conditions on the degree sequence similar to those observed in 1.2.

For the remainder of the paper, we shall omit the subscript $n$ for reasons of clarity - for example we write $\mathbf{d}=\mathbf{d}_{n}$ etc. Let $\mathcal{C}_{k}(\mathbf{d})$ be the size of the $k$th largest strongly connected component of the directed configuration model with degree sequence $\mathbf{d}$. We shall write $\mathcal{C}_{k}$ for this quantity when the degree sequence is clear.

Our main result is the following,

The condition $nQ^{3}(R^{-}R^{+})^{-1}\to-\infty$ is likely best possible as the analogous condition in the undirected case discriminates the barely subcritical case from the critical window. Moreover, substituting $Q,R^{-}$ and $R^{+}$ obtained from a typical degree sequence of $D(n,p)$ also enters the critical window when we have $nQ^{3}(R^{-}R^{+})^{-1}\to c$ for some constant $c$.

In prior work, Łuczak and Seierstad [17] considered the model $D(n,p)$ which is a random digraph model formed by including each possible arc with probability $p$ independently. They showed an analogous result to Theorem 1.3 for $p=(1-\varepsilon)/n$ with $\varepsilon=o(1)$ and $\varepsilon^{3}n\to\infty$ in this model.

The study of the giant component in random graph models was initiated by the seminal paper of Erdős and Rényi [7] regarding the giant component in $G(n,p)$. Since then the appearance of a giant component in various models has remained an active topic of study in the area.

When working with directed graphs, there are a number of types of connected component which are of interest. In this paper we concern ourselves with the strongly connected components. The study of strongly connected components in random digraphs began in the model $D(n,p)$ where we include each possible edge with probability $p$ independently. Karp [14] and Łuczak [16] independently showed that when $p=c/n$, then $D(n,p)$ has all strongly connected components of size $O(1)$ if $c<1$. If instead $c>1$ they showed that there exists a unique strongly connected component of linear order with all other components of size $O(1)$. The case $p=(1+\varepsilon)/n$ with $\varepsilon=o(1)$ and $|\varepsilon|^{3}n\to\infty$ was studied by Łuczak and Seierstad [17]. They showed that if $\varepsilon^{3}n\to\infty$, there is a unique strongly connected component of size $4\varepsilon^{2}n$ and other components all of size $O(1/\varepsilon)$. When $\varepsilon^{3}n\to-\infty$ they showed an analogue of Theorem 1.3:

The so-called critical window, when $p=(1+\lambda n^{-1/3})/n$ has also been the subject of some study. In [5] the author showed bounds on the size of the largest strongly connected component in this regime which are akin to bounds obtained by Nachmias and Peres for the undirected case [18]. Moreover, Goldschmidt and Stephenson [10] gave a scaling limit result for the largest strongly connected components in the critical window.

The directed configuration model has also been studied previously. It was first studied by Cooper and Frieze who showed that provided the maximum degree $\Delta<n^{1/12}/\log(n)$ then if $Q_{n}<0$, there is no all strongly connected components are small and if $Q_{n}>0$ there is a giant strongly connected component of linear size. The assumptions on the degree sequence have subsequently been relaxed, Graf [11] showed $\Delta<n^{1/4}$ is enough to draw the same conclusion and Cai and Perarnau [2] improved this further to only require bounded second moments. A scaling limit result has been recently obtained at the exact point of criticality, $Q_{n}=0$ by Donderwinkel and Xie [6] in a very closely related model where vertices’ degrees are sampled from a limiting degree sequence.

The remainder of this paper is arranged as follows, in section 2 we prove some auxiliary results on subgraph counting within the directed configuration model. Then, in section 3 we enumerate certain types of strongly connected directed graphs of maximum degree $4$. In section 4 we prove Theorem 1.3 which we break down into a few steps: first that there are no long cycles, next that there are no complex components, and finally we compute the probability the $k$th largest component has size at least $\alpha/|Q|$ via Poisson approximation. We conclude the paper in section 5 with some open questions and future work.

To show that there are no long cycles, it suffices to show that the out-component of an arbitrary vertex is bounded above by $f(n)$. Certainly, the longest cycle in a directed graph is at most the size of the largest out-component and so the lemma follows.

Thus, consider the following version of the branching process of Hatami and Molloy [12] for the out-component in a digraph. For a vertex $v$ we explore its out-component in the random digraph $G(\mathbf{d})$ as follows. We will have a partial subdigraph $C_{t}$ at time $t$ consisting of the vertices explored thus far. $C_{t}$ will consist of all in- and out-stubs of some vertices of $G(\mathbf{d})$ together with a matching of some of the stubs. If there are unmatched out-stubs in $C_{t}$ we will pick one at random and match it to some in-stub which yields an edge of $C_{t}$. We define $Y_{t}$ as the number of unmatched out-stubs in $C_{t}$. Thus, $Y_{t}=0$ indicates that we have explored an out-component in its entirety. Formally we define the exploration process as follows.

• •

  Choose a vertex $v$ and initialise $C_{0}=\{v\}$ and $Y_{0}=d^{+}(v)$.

• •

  While $Y_{t}>0$, choose an arbitrary unmatched out-stub of any vertex $v\in C_{t}$. Pick a uniformly random unmatched in-stub and let $u$ be the vertex to which this in-stub belongs. Match these two stubs forming an edge of $G$.

  • –

    If $u\not\in C_{t}$ we add it so $C_{t+1}=C_{t}\cup\{u\}$ and $Y_{t+1}=Y_{t}+d^{+}(u)-1$.

  • –

    Otherwise, $C_{t+1}=C_{t}$, $Y_{t+1}=Y_{t}-1$.

Note that $Y_{t}$ does not depend on how we have exposed $C_{t}$ so $C_{t}$ and $Y_{t}$ are Markov processes. We define the following quantities.

• •

  $D_{t}:=Y_{t}+\sum_{u\not\in C_{t}}d^{+}(u)$, the number of unmatched out-stubs at time $t$. Note this is also the number of unmatched in-stubs at time $t$.

• •

  $v_{t}:=\emptyset$ if $C_{t-1}$ and $C_{t}$ have the same vertex set. Otherwise it is the unique vertex in $C_{t}\setminus C_{t-1}$.

• •

  $Q_{t}:=\frac{\sum_{u\not\in C_{t}}d^{-}(u)d^{+}(u)}{D_{t}}-1$.

Note that initially $Q_{t}=Q$. Also, for unvisited vertices $u\not\in C_{t}$, the probability that we explore $u$ next is $\mathbb{P}(v_{t+1}=u)=\frac{d^{-}(u)}{D_{t}}$. Hence, provided that $Y_{t}>0$, the expected change in $Y_{t}$ is

$$\mathbb{E}(Y_{t+1}-Y_{t}|C_{t})=\sum_{u\not\in C_{t}}\mathbb{P}(v_{t+1}=u)(d^{+}(u)-1)=\frac{\sum_{u\not\in C_{t}}d^{-}(u)d^{+}(u)}{D_{t}}-1=Q_{t}.$$

(10)

As long as $Q_{t}$ remains close to $Q$ we expect that $Y_{t}$ is a random walk with drift approximately $Q$. So in particular, for our setting of $Q<0$, we expect that the random walk will quickly return to 0. Thus, we shall start by showing that the drift parameter $Q_{t}$ is indeed close to $Q$ with high probability. For this we shall use the following formulation of the Azuma-Hoeffding inequality (see [13, Theorem 2.25]).

For $t\geq 1$ define $W_{t}:=Q_{t}-Q_{t-1}-\mathbb{E}(Q_{t}-Q_{t-1}|C_{t-1})$. Also, we define $X_{0}=Q$ and for $t\geq 1$ let

$$X_{t}:=X_{0}+\sum_{i=1}^{t}W_{i}=Q_{t}-\sum_{i=1}^{t}\mathbb{E}(Q_{i}-Q_{i-1}|C_{i-1}).$$

(11)

It is a simple check that the $X_{t}$ forms a martingale. Furthermore, $|Q_{t}-Q|\leq|Q_{t}-X_{t}|+|X_{t}-Q|$ so to bound the probability that $|Q_{t}-Q|$ is large, we show that $|Q_{t}-X_{t}|$ is small and bound the probability that $|X_{t}-Q|$ is large.

For the second of these, consider the auxiliary random variables

$$\widetilde{Q}_{t}:=\frac{\sum_{u\not\in C_{t}}d^{-}(u)d^{+}(u)}{D_{t-1}}-1.$$

That is we change $Q_{t}$ to have the same denominator as $Q_{t-1}$. As we assume that $t\leq m/2$, $D_{t}\geq m/2$ so combining this with the fact that $|D_{t}-D_{t-1}|\leq 1$ we deduce that

$$|Q_{t}-\widetilde{Q}_{t}|=\frac{|D_{t}-D_{t-1}|\sum_{u\not\in C_{t}}d^{-}(u)d^{+}(u)}{D_{t}D_{t-1}}\leq\frac{4}{m}.$$

(12)

Also, as there is at most one vertex whose contributions are removed in moving from $Q_{t-1}$ to $Q_{t}$, then

$$|Q_{t-1}-\widetilde{Q}_{t}|\leq\frac{4\Delta^{2}}{m}.$$

(13)

Combining equations (12) and (13) gives an upper bound on $|Q_{t}-Q_{t-1}|$ which we may then use to bound the martingale differences almost surely,

$$|X_{t}-X_{t-1}|\leq\frac{8\Delta^{2}+8}{m}\leq\frac{16\Delta^{2}}{m}.$$

(14)

Next, we will bound the terms $\mathbb{E}(Q_{t}-Q_{t-1}|C_{t-1})$. It will be convenient to do this in two stages utilising the auxiliary random variables $\widetilde{Q}_{t}$. So, first note that

	$\displaystyle 0\leq\mathbb{E}(Q_{t-1}-\widetilde{Q}_{t}|C_{t-1})$	$\displaystyle=\sum_{u\not\in C_{t-1}}\mathbb{P}(v_{t}=u)\frac{d^{-}(u)d^{+}(u)}{D_{t-1}}\leq\sum_{u\in V(G)}\frac{(d^{-}(u))^{2}d^{+}(u)}{D_{t-1}^{2}}$
		$\displaystyle\leq\sum_{u\in V(G)}\frac{4(d^{-}(u))^{2}d^{+}(u)}{m^{2}}\leq\frac{4R^{-}+4}{m}.$		(15)

We can combine (15) with (12) and apply 1.2 to deduce that

$$|\mathbb{E}(Q_{t}-Q_{t-1}|C_{t-1})|\leq\frac{4R^{-}+8}{m}\leq\frac{12R^{-}}{\zeta m}.$$

(16)

This leaves us in a situation in which we can compare $X_{t}$ and $Q_{t}$,

$$|X_{t}-Q_{t}|\leq\sum_{i=1}^{t}|\mathbb{E}(Q_{i}-Q_{i-1}|C_{i-1})|\leq\frac{12R^{-}t}{\zeta m}.$$

(17)

So provided that $t\leq\frac{m\zeta|Q|}{48R^{-}}$ we have $|X_{t}-Q_{t}|\leq|Q|/4$ and in particular, for any such $t$,

		$\displaystyle\mathbb{P}\left(Q_{t}-Q\geq\frac{|Q|}{2}\right)=\mathbb{P}\left(Q_{t}-X_{t}+X_{t}-Q\geq\frac{|Q|}{2}\right)$
	$\displaystyle\leq\;$	$\displaystyle\mathbb{P}\left(X_{t}-Q\geq\frac{|Q|}{4}\right)\leq\mathbb{P}\left(|X_{t}-Q|\geq\frac{|Q|}{4}\right)$

Whereupon we can apply the Azuma-Hoeffding inequality as $X_{0}=Q$. We can use the bound from (14) for the $c_{k}$. Substituting into Theorem 4.2 yields,

$$\mathbb{P}\left(|X_{t}-Q|\geq\frac{|Q|}{4}\right)\leq\exp\left(-\frac{|Q|^{2}m^{2}}{8192t\Delta^{4}}\right)\leq\exp\left(-C|Q|mn^{-2/3}\log(n)\right),$$

(18)

where the second inequality in (18) comes from $t\leq\frac{m\zeta|Q|}{48R^{-}}$, $\Delta\leq n^{1/6}\log^{-1/4}(n)$ and $R^{-}\geq\zeta$. We could improve the dependence on $\Delta$ by using Freedman’s inequality [9] in place of the Azuma-Hoeffding inequality here however there are other points where we require $\Delta\leq n^{1/6}$ and so this would only remove the $\log^{-1/4}(n)$ term in 1.2. Note $mn^{-2/3}\geq m^{1/3}/2$ hence $|Q|mn^{-2/3}\to\infty$ and so for any large enough $n$,

$$\mathbb{P}\left(Q_{t}-Q\geq\frac{|Q|}{2}\right)=\mathbb{P}\left(Q_{t}\geq-\frac{|Q|}{2}\right)\leq n^{-2}.$$

(19)

Now that we have shown that $Q_{t}$ is concentrated around $Q$, we can proceed to show that $G(\mathbf{d})$ has no large components with high probability via a stopping time argument. We will use the following version of Doob’s optional stopping theorem [20, Theorem 10.10]