Large deviations of empirical neighborhood distribution in sparse random graphs

Introduction and main results

Consider the Erdős-Renyi ensemble $\mathcal{G}(n,p)$, where a random graph is obtained from the vertex set $[n]=\{1,\dots,n\}$ by adding each edge independently with probability $p$. In the sparse regime with $p=\lambda/n$, for a fixed $\lambda>0$, it is well known that, for large $n$, a typical graph from $\mathcal{G}(n,p)$ locally looks like a Galton-Watson tree with Poisson offspring distribution with mean $\lambda$. In this work we study large deviations from this typical behavior. The problem is intimately related to the question: conditioned on having a certain neighborhood distribution, what does a typical element of $\mathcal{G}(n,p)$ locally look like ? The same questions can be asked for other commonly studied random graph ensembles such as the uniform random graphs with fixed number of edges growing linearly with the number of vertices, or with given degree sequence. We formulate the problem within the theory of local weak convergence of graph sequences that was recently introduced by Benjamini and Schramm and Aldous and Steele . The associated local weak topology has now become a common tool for studying sparse graphs, see Aldous and Lyons and Bollobàs and Riordan . A surprising large variety of graph functionals are continuous for this topology. In Section 2 below, we will give more details on local weak convergence. In order to present our result, here we first introduce the main terminology.

For a finite graph $G=(V,E)$ and $v\in V$, one writes $G(v)$ for the connected component of $G$ at $v$. The empirical neighborhood distribution $U(G)$ of $G$ is the law of the equivalence class of the rooted graph $(G(o),o)$ where the root $o$ is sampled uniformly at random from $V$, i.e. $U(G)\in\mathcal{P}(\mathcal{G}^{*})$ is defined by

where $(G,o)$ is the canonical rooted graph whose equivalence class $g\in\mathcal{G}^{*}$ has law $\rho$. It is not hard to check that if $G$ is a finite graph then its neighborhood distribution $U(G)$ is unimodular. In particular, all sofic measures are unimodular. The converse is open; see . We denote by $\mathcal{P}_{u}(\mathcal{G}^{*})$ the set of unimodular probability measures. Similarly, we write $\mathcal{P}_{u}(\mathcal{T}^{*})$ for unimodular probability measures supported by trees.

2. Unimodular Galton-Watson trees with given neighborhood

If $G=(V,E)$ is a graph and $\{u,v\}\in E$ then define $G(u,v)$ as the rooted graph $(G^{\prime}(v),v)$, where $G^{\prime}=(V,E\backslash\{u,v\})$, i.e. $G(u,v)$ is the rooted graph obtained from $G$ by removing the edge $\{u,v\}$ and taking the connected component at the root $v$. Next, given a rooted graph $(G,o)$, and $g,g^{\prime}\in\mathcal{G}_{h-1}^{*}$, define

As an example, consider the the rooted graph $\alpha$ from Figure 1. Fix $h=2$, and call $g_{1},g_{2}$ the elements of $\mathcal{G}^{*}_{h-1}$ consisting respectively of a rooted single edge and a rooted triangle. Then one has $E_{h}(g_{1},g_{2})=2$ and $E_{h}(g_{2},g_{1})=0$. Similarly, if the reference graph is $\beta$ from Figure 1, then $E_{h}(g_{1},g_{2})=0$ while $E_{h}(g_{2},g_{1})=1$.

Here it is understood that $(G,o)$ represents the canonical rooted graph whose equivalence class in $\mathcal{G}_{h}^{*}$ has law $P$. By applying the definition of unimodularity (2) to the function

For $t,t^{\prime}\in\mathcal{T}^{*}_{h-1}$ such that $e_{P}(t,t^{\prime})\neq 0$ define, for all $\tau\in\mathcal{T}^{*}_{h}$,

where $\tau\cup t^{\prime}_{+}$ denotes the tree obtained from $\tau$ by adding a new neighbor of the root whose rooted subtree is $t^{\prime}$; see Figure 2 for an example. The subtree $\tau(o,v)$ is defined before Eq. (3) with the graph $G$ replaced by $\tau$.

It can be checked that $\widehat{P}_{t,t^{\prime}}$ is a probability, i.e. $\widehat{P}_{t,t^{\prime}}\in\mathcal{P}(\mathcal{T}^{*}_{h})$; see Section 3. We may now define the random rooted tree $(T,o)$. First, $(T,o)_{h}$ is sampled according to $P$. Next, for each vertex $v$ in the first generation of $(T,o)_{h}$, consider the subtree $t=T(o,v)_{h-1}$ with depth $h-1$ rooted at $v$ obtained by removing the edge $\{o,v\}$ and retaining the connected component up to distance $h-1$ from $v$. We add a layer to $t$ by replacing $t$ with a new tree $\tau$ with depth $h$ that coincides with $t$ in the first $h-1$ generations. The new tree $\tau$ is sampled according to $\widehat{P}_{t,t^{\prime}}$ where $t$ is as above while $t^{\prime}$ denotes the subtree $T(v,o)_{h-1}$ rooted at $o$ obtained from $(T,o)_{h}$ by removing the edge $\{o,v\}$ and retaining the connected component up to distance $h-1$ from $o$. This operation is repeated for each $v$ in the first generation independently. After this step, we have overall added one layer to $(T,o)_{h}$, and thus we have sampled $(T,o)_{h+1}$.

an application of Stirling’s formula shows that

If $\rho\in\mathcal{P}(\mathcal{G}^{*})$, define

where $B(\rho,\varepsilon)$ denotes the open ball with radius $\varepsilon$ around $\rho$ with respect to the Lévy metric on $\mathcal{P}(\mathcal{G}^{*})$. For $\varepsilon>0$, define

Since $\varepsilon\mapsto\overline{\Sigma}(\rho,\varepsilon)$ is non-decreasing, one defines

The extended real numbers $\underline{\Sigma}(\rho,\varepsilon)$ and $\underline{\Sigma}(\rho)$ are defined as above, with $\limsup$ replaced by $\liminf$. If $\rho$ is such that $\underline{\Sigma}(\rho)=\overline{\Sigma}(\rho)$, we set $\Sigma(\rho):=\overline{\Sigma}(\rho)=\underline{\Sigma}(\rho)$. The number $\Sigma(\rho)$ can be interpreted, up to an overall constant, as a microcanonical entropy associated to the state $\rho$. From (7), one has that $\Sigma(\rho)\in[-\infty,s(d)]$, whenever it is well defined.

Fix $d>0$ and choose a sequence $m=m(n)$ such that $m/n\to d/2$. For any $\rho\in\mathcal{P}(\mathcal{G}^{*})$, the entropy $\Sigma(\rho)\in\;\left[-\infty,s(d)\right]$ is well defined, it is upper semi-continuous, and it does not depend on the choice of the sequence $m(n)$. Moreover, $\Sigma(\rho)=-\infty$ if at least one of the following is satisfied:

Let us introduce some additional notation. For any $P\in\mathcal{P}(\mathcal{T}^{*}_{h})$, define the Shannon entropy

defines a function $J_{h}:\mathcal{P}_{h}\mapsto[-\infty,s(d)]$, satisfying

In Remark 5.13 below we provide an alternative expression for $J_{h}(P)$ in terms of relative entropies. Specializing to the case $h=1$, we obtain the following corollary of Theorem 1.3.

As a byproduct of our analysis, we will also obtain an alternative proof of the Bowen-Elek Theorem .

If $\rho\in\mathcal{P}_{u}(\mathcal{T}^{*})$, then $\rho$ is sofic.

4. Large deviations of uniform graphs with given degrees

$\max_{1\leqslant v\leqslant n}d^{(n)}(v)\leqslant\theta$,

$\frac{1}{n}\sum_{v\in[n]}\delta_{d^{(n)}(v)}\rightsquigarrow P$,

where $B^{\circ}$ denotes the interior of $B$ and $\overline{B}$ denotes the closure of $B$.

Let $\mathbf{d}^{(n)}$ be a sequence satisfying conditions $(C1)-(C3)$ above. Let $G_{n}$ be uniformly distributed on $\mathcal{G}(\mathbf{d}^{(n)})$. Then $U(G_{n})$ satisfies the LDP in $\mathcal{P}(\mathcal{G}^{*})$ with speed $n$ and good rate function

It follows from Theorem 1.3 that for any integer $h\geqslant 1$, and $Q\in\mathcal{P}_{h}$ with $Q_{1}=P$, then

We note finally Theorem 1.6 establishes a large deviations principle with speed $n$. Other interesting large deviation events occur at higher speed. For example, for the proportion of vertices in a triangle in $G_{n}$, the speed would be $n\log n$.

5. Large deviations of Erdős-Rényi graphs

Fix $d>0$ and a sequence $m=m(n)$ such that $m/n\to d/2$, as $n\to\infty$. Let $G_{n}$ be uniformly distributed in $\mathcal{G}_{n,m}$. Then $U(G_{n})$ satisfies the LDP in $\mathcal{P}(\mathcal{G}^{*})$ with speed $n$ and good rate function

Fix $\lambda>0$ and take $G_{n}$ with law $\mathcal{G}(n,\lambda/n)$. Then $U(G_{n})$ satisfies the LDP in $\mathcal{P}(\mathcal{G}^{*})$ with speed $n$ and good rate function

6. Plan and methods

The proof of the main results discussed above is organized as follows. In Section 2 we review some basic facts about local weak convergence in the context of multi-graphs. We also establish a compactness criterion which parallels recent results of Benjamini, Lyons and Schramm . In Section 3 we introduce the unimodular Galton Watson trees with given $h$-neighborhood distribution and prove the properties stated in Proposition 1.1 . In Section 5 we prove our main results concerning the entropy $\Sigma(\rho)$, cf. Theorem 1.2 and Theorem 1.3. These are crucially based on the possibility of counting asymptotically the number of graphs in $\mathcal{G}_{n,m}$ which have a certain $h$-neighborhood distribution. To compute such things, we introduce what we call a generalized configuration model. The standard configuration model, introduced in Bollobas , allows one to compute asymptotically the number of graphs with a given degree sequence. Since here we want to uncover the $h$-neighborhood of a vertex and not only its degree, we need to generalize the usual construction. To keep track of the $h$-neighborhood structure, we introduce directed multigraphs with colored edges and analyze the associated configuration model; see Section 4. This will allow us to sample a random graph with a given sequence of $h$-neighborhoods, as long as these neighborhoods are rooted trees. As an application, we prove Corollary 1.5 at the end of Section 4. It seems to us that this new configuration model may turn out to be a natural tool in other applications as well. Finally, Section 6 is devoted to the proof of large deviation principles in the classical random graphs ensembles. We stress that our methods allow in principle a much greater generality, since one could establish large deviation estimates for random graphs that are uniformly sampled from the class of all graphs with a given $h$-neighborhood distribution and not only with given degree sequences; see Remark 6.1.

7. Related work

Large deviations in random graphs is a rapidly growing topic. For dense graphs, e.g. $\mathcal{G}(n,p)$ with fixed $p\in(0,1)$, a thorough treatment has been given recently by Chatterjee and Varadhan , in the framework of the cut topology introduced by Lovász and Szegedy , see also Borgs, Chayes, Lovász, Sós and Vesztergombi . In the sparse regime, only a few partial results are known. O’Connell , Biskup, Chayes and Smith and Puhalskii have proven large deviation asymptotics for the connectivity and for the size of the connected components. Large deviations for degree sequences of Erdős-Rényi graphs has been studied in Doku-Amponsah and Mörters and Boucheron, Gamboa and Léonard [13, Theorem 7.1]. Closer to our approach, large deviations in the local weak topology were obtained for critical multi-type Galton-Watson trees by Dembo, Mörters and Sheffield . Finally, large deviations for other models of statistical physics on Erdős-Rényi graphs have been considered in Rivoire and Engel, Monasson, and Hartmann .

As far as we know, this is the first time that large deviations of the neighborhood distribution are addressed in a systematic way. While our approach does not cover results on connectivity and the size of connected components such as , it does yield a simplification of some of the existing arguments concerning the large deviations for degree sequences. We point out that our Corollary 1.10 gives a corrected version of [18, Corollary 2.2]. Under a stronger sparsity assumption, large deviations of neighborhood distributions for random networks have been used in to study the large deviations of the spectral measure of certain random matrices.

Local weak convergence

In this section, we first recall the basic notions of local weak convergence in the more general context of rooted multi-graphs; see , , and . Then, we give a general tightness lemma.

Recall that a path $\pi$ from $u$ to $v$ of length $k$ is a sequence $\pi=(u_{0},\cdots,u_{k})$ with $u_{0}=u$, $u_{k}=v$ and, for $0\leqslant i\leqslant k-1$, $\{u_{i},u_{i+1}\}\in E$. If such $\pi:u\to v$ exists, the distance $D(u,v)$ in $G$ between $u$ and $v$ is defined as the minimal length of all paths from $u$ to $v$. If there is no path $\pi:u\to v$, then the distance $D(u,v)$ is set to be infinite. A multi-graph is connected if $D(u,v)<\infty$ for any $u\neq v\in V$.

Below, a rooted multi-graph $(G,o)=(V,\omega,o)$ is a locally finite and connected multi-graph $(V,\omega)$ with a distinguished vertex $o\in V$, the root. For $t\geqslant 0$, we denote by $(G,o)_{t}$ the induced rooted multi-graph with vertex set $\{u\in V:\,D(o,u)\leqslant t\}$. Two rooted multi-graphs $(G_{i},o_{i})=(V_{i},\omega_{i},o_{i})$, $i\in\{1,2\}$, are isomorphic if there exists a bijection $\sigma:V_{1}\to V_{2}$ such that $\sigma(o_{1})=o_{2}$ and $\sigma(G_{1})=G_{2}$, where $\sigma$ acts on $G_{1}$ through $\sigma(u,v)=(\sigma(u),\sigma(v))$ and $\sigma(\omega)=\omega\circ\sigma$. We will denote this equivalence relation by $(G_{1},o_{1})\simeq(G_{2},o_{2})$. The associated equivalence classes can be seen as unlabeled rooted multi-graphs. We call $\widehat{\mathcal{G}}^{*}$ the set of all such equivalence classes.

We define the semi-distance $d$ between two rooted multi-graphs $(G_{1},o_{1})$ and $(G_{2},o_{2})$ as

where $T$ is the supremum of those $t>0$ such that $(G_{1},o_{1})_{t}$ and $(G_{2},o_{2})_{t}$ are isomorphic. On the space $\widehat{\mathcal{G}}^{*}$, $d$ is a distance. The associated topology will be referred to as the local topology. The space $(\widehat{\mathcal{G}}^{*},d)$ is Polish (i.e. separable and complete) .

Explicit compact subsets of $\widehat{\mathcal{G}}^{*}$ can be constructed as follows. If $g\in\widehat{\mathcal{G}}^{*}$, we define

is a compact subset of $\,\widehat{\mathcal{G}}^{*}$ for the local topology.

For each $t\geqslant t_{0}$, there is a finite number of elements in $\widehat{\mathcal{G}}^{*}$, say $f_{t,1},\cdots,f_{t,n_{t}}$, such that $|g|\leqslant\varphi(t)$ and for any vertex the distance to the root is at most $t$. Therefore, the collection $A_{t,1},\cdots,A_{t,n_{t}}$ where $A_{t,k}=\{g\in\widehat{\mathcal{G}}^{*}:g_{t}=f_{t,k}\}$ is a finite covering of $K$ of radius $1/(1+t)$. ∎

The notions of local weak convergence introduced in §1.1 are immediately extended to the present setting of multi-graphs. The definitions of $U(G)$ in (1) and unimodularity (2) easily carry over to $\mathcal{P}(\widehat{\mathcal{G}}^{*})$. The next simple lemma is proved in .

The set $\mathcal{P}_{u}(\widehat{\mathcal{G}}^{*})$ is closed in the local weak topology.

2. Compactness lemma for the local weak topology

Let $G_{n}$ be a sequence of finite multi-graphs. We now give a condition which guarantees that the sequence $U(G_{n})$ is tight for the local weak topology. If $G=(V,\omega)$ is a multi-graph, we define the degree of a subset $S\subset V$ as

The next lemma is a sufficient condition for tightness in $\mathcal{P}_{u}(\widehat{\mathcal{G}}^{*})$. A similar result appears in Benjamini, Lyons and Schramm [3, Theorem 3.1]. We give an independent proof.

Considering a sequence $U(G_{n}),n\geqslant 1$, condition (15) amounts to a uniform integrability of the degree sequences of the multi-graphs $(G_{n}),n\geqslant 1$. It may seem quite paradoxical that a sole condition on the degrees implies the tightness of the whole graph sequence. However, the unimodularity of $U(G)$ yields enough uniformity for this result to hold.

Since $\widehat{\mathcal{G}}^{*}$ is a Polish space, from Prohorov’s theorem, a set $\Pi\subset\mathcal{P}(\widehat{\mathcal{G}}^{*})$ is relatively compact if and only if for any $\varepsilon>0$, there exists a compact $K\subset\widehat{\mathcal{G}}^{*}$ such that for all $\mu\in\Pi$, $\mu(K^{c})\leqslant\varepsilon$.

Set $c=\delta(1)$. Without loss of generality, we may assume $c>1$. We consider the increasing function $[0,c]\mapsto$

Now, for each $\varepsilon>0$, and integer $t\geqslant 1$, we set

where the composition holds $t$ times. We now define $\Pi$ as being the closure of the set of measures $\mu$ in $\mathcal{P}_{u}(\widehat{\mathcal{G}}^{*})$ such that for any $\varepsilon>0$, $\mu(K_{\varepsilon}^{c})\leqslant\varepsilon$ where

By Lemma 2.1, $K_{\varepsilon}$ is a compact set of $\widehat{\mathcal{G}}^{*}$. Hence, Prohorov’s theorem asserts that $\Pi$ is a compact set of $\mathcal{P}_{u}(\widehat{\mathcal{G}}^{*})$.

We now check that $\rho=U(G)\in\Pi$. This will conclude the proof of our lemma. It is sufficient to prove that $\rho(K_{\varepsilon})\geqslant 1-\varepsilon$ for all $\varepsilon>0$. Let $t\geqslant 0$ be an integer, for $S\subset V$, $B(S,t)$ denote the set of vertices at distance at most $t$ from a vertex in $S$. In particular, if $v\in V$ and $g$ is the equivalence class of $(G(v),v)$ we have

Hence, using Markov inequality, we deduce that the set

has cardinality at most $h_{\varepsilon}(t)n$. From what precedes, the set

has cardinality at most $2^{-t}\varepsilon n$. So finally, from the union bound, the set

has cardinality at least $(1-\varepsilon)n$. We have thus checked that $\rho(K_{\varepsilon})\geqslant 1-\varepsilon$. ∎

Unimodular Galton-Watson trees with given neighborhood

First observe that if $\tau\in\mathcal{T}^{*}_{h}$, $t^{\prime}\in\mathcal{T}^{*}_{h-1}$ and $S=\tau\cup t^{\prime}_{+}$, then (recall the definition of $\tau\cup t^{\prime}_{+}$ and Figure 2)

Therefore, for any $t,t^{\prime}\in\mathcal{T}^{*}_{h-1}$,

where, in the summand, $S=\tau\cup t^{\prime}_{+}$. Now, (5) and (16) imply

Finally, the assumption $e_{P}(t,t^{\prime})=e_{P}(t^{\prime},t)$ yields

2. Consistency lemma

We turn to the second part of Proposition 1.1. The following lemma computes the law of the $(h+1)$-neighborhood of a Galton-Watson tree with a given $h$-neighborhood.

$(t^{i}\in\mathcal{T}^{*}_{h},1\leqslant i\leqslant d)$ are the subtrees of $\tau$ attached to the offspring of the root, and for $1\leqslant i\leqslant d$, $s^{i}=(t^{i})_{h-1}$ ;

$\{s^{a}\}_{a\in\mathcal{A}}$ is set of distinct elements of $(s^{i},1\leqslant i\leqslant d)$, and, for each $a\in\mathcal{A}$, $\{t^{a,b}\}_{b\in\mathcal{B}_{a}}$ is the set the distinct elements of $(t^{i},1\leqslant i\leqslant d)$, such that $(t^{a,b})_{h-1}=s^{a}$ ;

$n_{a}$ is the cardinality of $s^{i}$’s equal to $s^{a}$ and $k_{a,b}$ is the cardinality of $t^{i}$’s equal to $t^{a,b}$ ;

$s^{-a}=(t^{-a})_{h-1}$ and $t^{-a}\in\mathcal{T}^{*}_{h}$ is the tree obtained from $\tau_{h}$ by removing one offsping with subtree equal to $s^{a}$.

Using $\rho_{h}=P$, for a fixed $\tau\in\mathcal{T}^{*}_{h+1}$, the above definitions allow us to write

Observe that $T(o,v)_{h}=t^{a,b}$ implies that $T(o,v)_{h-1}=s^{a}$. Moreover, given $(T,o)_{h}=t$, $T(o,v)_{h-1}=s^{a}$ implies that $T(v,o)_{h-1}=s^{-a}$, i.e. the type of vertex $v$ is $(s^{a},s^{-a})$. The lemma is then a consequence of the conditional independence of the subtrees attached to the offspring of the root given $(T,o)_{h}$. ∎

By recursion, it suffices to prove the statement for $k=h+1$. For $s\in\mathcal{T}^{*}_{h-1}$ such that $e_{P}(s,s^{\prime})>0$ for some $s^{\prime}\in\mathcal{T}^{*}_{h-1}$, we may define the probability measure

However, with n=\big{|}\big{\{}v\stackrel{{\scriptstyle t}}{{\sim}}o:t(o,v)=s^{\prime}\big{\}}\big{|}, we deduce from the unimodularity of $\rho$ and (16) that

where $s^{\prime}=t^{\prime}_{h-1}$. Indeed, since $\rho^{\prime}$ and $\rho$ have the same $h+1$ neighborhood, this would prove that they have in fact the same $h+2$ neighborhood and, by conditional independence, we would deduce that $\rho=\rho^{\prime}$.

where, as above, $t=\tau_{h}$ and $s^{\prime}=t^{\prime}_{h-1}$. Since $(\tau\cup t^{\prime}_{+})_{h}=t\cup s^{\prime}_{+}$, and $\rho^{\prime}_{h+1}=\rho_{h+1}$, we have

As in Lemma 3.2, let $t^{i}\in\mathcal{T}^{*}_{h},1\leqslant i\leqslant d$ be the subtrees of $\tau$ attached to the offspring of the root and call $s^{i}$ their restriction to $\mathcal{T}^{*}_{h-1}$. By construction, $k$ elements of the $t^{i}$’s are equal to $t^{\prime}$ and $n$ elements of the $s^{i}$’s are equal to $s^{\prime}$. Let $(s^{a})_{a}$ be the set of distinct elements of the set $\{s^{\prime}\}\cup\{s^{i},1\leqslant i\leqslant d\}$, and, for each $a$, let $(t^{a,b})_{b}$ denote the distinct elements of $\{t^{\prime}\}\cup\{t^{i},1\leqslant i\leqslant d\}$, such that $t^{a,b}$ restricted to $\mathcal{T}^{*}_{h-1}$ is $s^{a}$. We denote by $n_{a}$ the cardinality of $s^{i}$’s equal to $s^{a}$ and $k_{a,b}$ the cardinality of $t^{i}$’s equal to $t^{a,b}$. We set $n^{\prime}_{a}=n_{a}+\mathbf{1}(s_{a}=s^{\prime})$ and $k^{\prime}_{a,b}=k_{a,b}+\mathbf{1}(t_{a,b}=t^{\prime})$. Then, Lemma 3.2 yields

where, $s^{-a}=[(t\cup s^{\prime}_{+})^{-a}]_{h-1}$ and $(t\cup s^{\prime}_{+})^{-a}\in\mathcal{T}^{*}_{h}$ is the tree obtained from $t\cup s^{\prime}_{+}$ by removing one of the offspring with subtree equal to $s^{a}$. Thus, we find

Since $\rho_{h+1}=\rho^{\prime}_{h+1}$, one has

By sampling the $h$-neighborhood $(T,o)_{h}$ first, and using the number $n$ as above, one has

Next, we show that the right hand side in (19) equals the above expression. We have

where we have used unimodularity and (18). Now, by sampling first the $h$-neighborhood $(T,o)_{h}$, one finds that

where, as before, $k=k(t^{\prime})$ stands for the number of $v\stackrel{{\scriptstyle\tau}}{{\sim}}o$ such that $\tau(o,v)=t^{\prime}$. Using Lemma 3.2 in the form (20), and the fact that $\sum_{t^{\prime}:t^{\prime}_{h-1}=s^{\prime}}\widehat{P}_{s^{\prime},s}(t^{\prime})=1$, we find

The identity (19) follows from (24) and (23). ∎

Configuration model for directed graphs with colored edges

This section introduces a generalized configuration model, to be used later on to count the number of graphs with a given tree-like neighborhood distribution.

We are now going to define a family of directed multi-graphs with colored edges. Let $L$ be a fixed integer. Each pair $(i,j)$ with $1\leqslant i,j\leqslant L$ is interpreted as a color. Define the sets of colors

Also, define $\mathcal{C}_{\leqslant}=\mathcal{C}_{<}\cup\mathcal{C}_{=}$, $\mathcal{C}_{>}=\mathcal{C}\setminus\mathcal{C}_{\leqslant}$ and $\mathcal{C}_{\neq}=\mathcal{C}\setminus\mathcal{C}_{=}$. If $c=(i,j)\in\mathcal{C}$, then set $\bar{c}=(j,i)$ for the conjugate color.

If $G\in\widehat{\mathcal{G}}(\mathcal{C})$, one can define the colorblind multi-graph $\bar{G}=(V,\bar{\omega})$, by setting

The multi-graph $\bar{G}=(V,\bar{\omega})$ can be identified with an undirected multi-graph, in that by construction $\bar{\omega}(u,v)=\bar{\omega}(v,u)$ for all $u,v\in V$. We say that $G$ is a simple graph if $\bar{G}$ has no loops and no multiple edges. Clearly, if $L=1$ then there is only one color, so that any multi-graph $G\in\widehat{\mathcal{G}}(\mathcal{C})$ coincides with its own $\bar{G}$.

If $G\in\widehat{\mathcal{G}}(\mathcal{C})$, $c\in\mathcal{C}$ and $u\in V$, set

and write $D(u)=\{D_{c}(u),c\in\mathcal{C}\}$. Note that $D(u)$ is an element of $\mathcal{M}_{L}$, defined as the set of $L\times L$ matrices with nonnegative integer valued entries. The vector $\mathbf{D}=\{D(u),u\in V\}$ of such matrices will be called the degree sequence of $G$.

2. Directed colored multi-graphs with given degree sequence

$\widehat{\mathcal{G}}(\mathbf{D})$ is the set of multi-graphs $G\in\widehat{\mathcal{G}}(\mathcal{C})$ with $V=[n]$ such that the degree sequence of $G$ defined by (26) coincides with $\mathbf{D}$.

Fix a multi-graph $G\in\widehat{\mathcal{G}}(\mathbf{D})$. For a fixed $c\in\mathcal{C}_{=}$, let $G_{c}$ denote the subgraph of $G$ obtained by removing all edges but the ones with color $c$. If $c\in\mathcal{C}_{<}$ instead, then define $G_{c}$ as the subgraph of $G$ obtained by removing all edges but the ones with color $c$ or $\bar{c}$. Thus, every $G\in\widehat{\mathcal{G}}(\mathbf{D})$ is the result of the superposition of the multi-graphs $G_{c}$, $c\in\mathcal{C}_{\leqslant}$. We may then analyze each color separately.

When $c\in\mathcal{C}_{=}$, every pair $u,v$ satisfies $\omega_{c}(u,v)=\omega_{c}(v,u)$, so $G_{c}$ is actually a multi-graph with undirected edges, and we may use the usual construction [8, Section 2.4]. We provide the details for completeness. The degrees of $G_{c}$ are fixed by the sequence $D_{c}(1),\dots,D_{c}(n)$. Let $W_{c}=\cup_{i=1}^{n}W_{c}(i)$, be a fixed set of $S_{c}=\sum_{i=1}^{n}D_{c}(i)$ points, with the subsets $W_{c}(i)$ satisfying $|W_{c}(i)|=D_{c}(i)$. Recall that $S_{c}$ is even by assumption. Let $\Sigma_{c}$ be the set of all perfect matchings of the complete graph over the points of $W_{c}$, i.e. the set of all partitions of $W_{c}$ into disjoint edges. Then,

Elements of $\Sigma_{c}$ are called configurations. For any configuration $\sigma_{c}\in\Sigma_{c}$, call $\Gamma(\sigma_{c})$ the multi-graph on $[n]$ with undirected edges obtained by including an edge $\{i,j\}$ iff $\sigma_{c}$ has a pair with one element in $W_{c}(i)$ and the other in $W_{c}(j)$. Notice that $\Gamma(\sigma_{c})$ has the same degree sequence $D_{c}(1),\dots,D_{c}(n)$ of $G_{c}$. Moreover, any multi-graph with that degree sequence equals $\Gamma(\sigma_{c})$ for some $\sigma_{c}\in\Sigma_{c}$.

Fix $c\in\mathcal{C}_{=}$. Let $H$ be a multi-graph on $[n]$ with undirected edges and with degree sequence $D_{c}(1),\dots,D_{c}(n)$. The number of $\sigma_{c}\in\Sigma_{c}$ such that $\Gamma(\sigma_{c})=H$ is given by

where $\omega_{c}(i,j)$ is the number of edges between nodes $\{i,j\}$ in $H$, while $\omega_{c}(i,i)/2$ is the number of loops at node $i$ in $H$.

We need to count the number of matchings $\sigma_{c}\in\Sigma_{c}$ such that for every $i<j$ one has $\omega_{c}(i,j)$ edges between $W_{c}(i)$ and $W_{c}(j)$, and such that for all $i$ one has $\frac{1}{2}\omega_{c}(i,i)$ edges within $W_{c}(i)$. Fix $i<j$. Once we choose the $\omega_{c}(i,j)$ elements of $W_{c}(i)$ and the $\omega_{c}(i,j)$ elements of $W_{c}(j)$ to be matched together to produce the $\omega_{c}(i,j)$ edges, then there are $\omega_{c}(i,j)!$ distinct matchings that produce the same graph. Similarly, once we fix the $\omega_{c}(i,i)$ elements of $W_{c}(i)$ to be matched together to produce the $\frac{1}{2}\omega_{c}(i,i)$ loops at $i$, then there are $(\omega_{c}(i,i)-1)!!$ distinct matchings that produce the same graph. On the other hand, for every node $i$ there are

distinct ways of choosing the elements of $W_{c}(i)$ to be matched with $W_{c}(1),\dots,W_{c}(n)$ respectively. Putting all together we arrive at the following expression for the total number of configurations producing the graph $H$:

When $c\in\mathcal{C}_{<}$, every pair $u,v$ satisfies $\omega_{c}(u,v)=\omega_{\bar{c}}(v,u)$, so for the multi-graph $G_{c}$, $D_{c}(i)$ represents the number of outgoing edges at node $i$, which equals the number of incoming edges at that node. Here we use a bipartite version of the previous construction. Let $W_{c}=\cup_{i=1}^{n}W_{c}(i)$, be a fixed set of $S_{c}=\sum_{i=1}^{n}D_{c}(i)$ points, with the subsets $W_{c}(i)$ satisfying $|W_{c}(i)|=D_{c}(i)$. Similarly, set $\bar{W}_{c}=\cup_{i=1}^{n}\bar{W}_{c}(i)$, with $|\bar{W}_{c}(i)|=D_{\bar{c}}(i)$. Consider the set $\Sigma_{c}$ of all perfect matchings of the complete bipartite graph over the sets $(W_{c},\bar{W}_{c})$, i.e. the set of perfect matchings containing only edges connecting an elements of $W_{c}$ with an element of $\bar{W}_{c}$. Since $S_{c}=S_{\bar{c}}$, one has $|W_{c}|=|\bar{W}_{c}|$, and $\Sigma_{c}$ can be identified with the set of permutations of $S_{c}$ objects, or the set of bijective maps $W_{c}\mapsto\bar{W}_{c}$, and $|\Sigma_{c}|=S_{c}!$. A configuration is an element $\sigma_{c}\in\Sigma_{c}$. For any configuration $\sigma_{c}$, let $\Gamma(\sigma_{c})$ denote the directed multi-graph on $[n]$ obtained by including the directed edge $(i,j)$ with color $c$ and the edge $(j,i)$ with color $\bar{c}$ iff $\sigma_{c}$ has a pair with one element in $W_{c}(i)$ and the other in $\bar{W}_{c}(j)$. Notice that $\Gamma(\sigma_{c})$ has the same degree sequence $D_{c}(1),\dots,D_{c}(n)$ of $G_{c}$, and any multi-graph with directed edges with colors with the same degree sequence equals $\Gamma(\sigma_{c})$ for some $\sigma_{c}\in\Sigma_{c}$.

Fix $c\in\mathcal{C}_{<}$. Let $H$ be a multi-graph on $[n]$ with directed edges with colors $(c,\bar{c})$ only and with degree sequence $D_{c}(1),\dots,D_{c}(n)$. The number of $\sigma_{c}\in\Sigma_{c}$ such that $\Gamma(\sigma_{c})=H$ is given by

where $\omega_{c}(i,j)=\omega_{\bar{c}}(j,i)$ is the number of edges from $i$ to $j$ with color $c$ in $H$.

We have to count the number of bijective maps $W_{c}\mapsto\bar{W}_{c}$ such that for every $i,j\in[n]$ (including the case $i=j$), $\omega_{c}(i,j)$ elements of $W_{c}(i)$ are mapped to $\bar{W}_{c}(j)$. We begin by choosing, for every fixed node $i$, the subsets of $W_{c}(i)$ that are mapped into $\bar{W}_{c}(k)$, $k=1,\dots,n$, and the subsets of $\bar{W}_{c}(i)$ that are mapped into $W_{c}(k)$, $k=1,\dots,n$. This can be done in

distinct ways. Once these subsets are chosen there remain, for every $i,j$, $\omega_{c}(i,j)!$ distinct bijections producing the same graph. Therefore, the total number of bijections from $W_{c}$ to $\bar{W}_{c}$ which preserve the numbers $\omega_{c}(i,j)=\omega_{\bar{c}}(j,i)$ is given by

The latter expression can be rewritten as (29). ∎

2.3. Generalized configuration model

where $S_{c}=\sum_{i=1}^{n}D_{c}(i)$, and $b(H)$ is defined by

In particular, for any $h\geqslant 2$, if $\mathcal{G}(\mathbf{D},h)$ is not empty, the law of $G$ conditioned on $\mathcal{G}(\mathbf{D},h)$ is the uniform distribution on $\mathcal{G}(\mathbf{D},h)$.

The cardinality of $\Sigma$ is given by $\prod_{c\in\mathcal{C}_{<}}S_{c}!\prod_{c\in\mathcal{C}_{=}}(S_{c}-1)!!$. Thus, it suffices to check that $\Gamma^{-1}(H)$ has cardinality $b(H)^{-1}\prod_{c\in\mathcal{C}}\prod_{i}D_{c}(u)!$. This follows from Lemma 4.2 and Lemma 4.3 by observing that $|\Gamma^{-1}(H)|=\prod_{c\in\mathcal{C}_{\leqslant}}n_{c}(H_{c})$, where $H_{c}$ denotes the multi-graph $H$ after all edges with color $c^{\prime}\notin\{c,\bar{c}\}$ are removed. This proves (30). If $H\in\mathcal{G}(\mathbf{D},h)$, $h\geqslant 2$, then $\omega_{c}(i,i)=0$ and $\omega_{c}(i,j)\in\{0,1\}$ for all $i,j\in[n]$ and $c\in\mathcal{C}$, so that $b(H)=1$. This proves the last assertion. ∎

for all $u\in[n]$, $D^{(n)}(u)\in\mathcal{M}_{L}^{(\theta)}$ ;

as $n\to\infty$, $\frac{1}{n}\sum_{u=1}^{n}\delta_{D^{(n)}(u)}\rightsquigarrow P.$

The main result of this section is the following

The actual value of $\alpha_{h}$ could be in principle computed in terms of $P$ (see proof of Theorem 4.5). We will however not need that.

In the setting of Theorem 4.5, writing $S_{c}^{(n)}=\sum_{u\in[n]}D_{c}^{(n)}(u)$, for all $h\geqslant 2$:

As in Lemma 4.4, for each $H\in\mathcal{G}(\mathbf{D}^{(n)},h)$, $|\Gamma^{-1}(H)|=\prod_{c\in\mathcal{C}}\prod_{u}D^{(n)}_{c}(u)!$. Hence the sum in the right hand side above equals $|\mathcal{G}(\mathbf{D}^{(n)},h)|\prod_{c\in\mathcal{C}}\prod_{u}D^{(n)}_{c}(u)!$. The conclusion follows from Theorem 4.5 and $|\Sigma|=\prod_{c\in\mathcal{C}_{<}}S^{(n)}_{c}!\prod_{c\in\mathcal{C}_{=}}(S^{(n)}_{c}-1)!!$. ∎

where we use the notation $B_{c}^{H,G}(u,v)$ for the binomial coefficient $\binom{\omega_{c}^{G}(u,v)}{\omega_{c}^{H}(u,v)}$, with the convention that if $u=v$ and $c\in\mathcal{C}_{=}$, then $B_{c}^{H,G}(u,u)$ equals $\binom{(\omega_{c}^{G}(u,u)/2)}{(\omega_{c}^{H}(u,u)/2)}$.

Next, for $G\in\widehat{\mathcal{G}}_{n}$ and $H\in\widehat{\mathcal{G}}_{k}$, $1\leqslant k\leqslant n$, define $X(H,G)$ as the number of distinct subgraphs of $G$ that are isomorphic to $H$. If $a(H)$ denotes the cardinality of the automorphism group of $H$, i.e. the number of permutations of the vertex labels which leave $H$ invariant, then

where the sum is over all injective maps $\tau$ from $[k]$ to $[n]$, and $\tau(H)$ represents the multi-graph obtained by embedding $H$ in $[n]$ through $\tau$.

For $H\in\widehat{\mathcal{G}}_{k}$, the $c$-degree at vertex $u$ is denoted

where $D\in\mathcal{M}^{(\theta)}_{L}$ has distribution $P$ and $s^{H}_{c}:=\sum_{i=1}^{k}d_{c}^{H}(i)$.

Consider first the case $c\in\mathcal{C}_{<}$. Set

where $H_{c}$ is the graph $H$ with all edges removed except for edges of color $c$ or $\bar{c}$, and the condition $G\supset H_{c}$ indicates that $\omega_{c}^{G}(u,v)\geqslant\omega_{c}^{H}(u,v)$ for all $u,v\in[n]$. Then, as in Lemma 4.4

On the other hand, applying (29) to the multi-graph $G\!\smallsetminus\!H$ defined by $(\omega_{c}^{G}(u,v)-\omega_{c}^{H}(u,v))$, one has

Next, consider the case $c\in\mathcal{C}_{=}$. Here

where $H_{c}$ is the graph $H$ with all edges removed except for edges of color $c$. Then,

Applying (28) to the multi-graph $G\!\smallsetminus\!H$ and simplifying, one arrives at

Finally, taking products over $c\in\mathcal{C}_{<}$ of (36) together with products over $c\in\mathcal{C}_{=}$ of (37), we arrive at (35).