Degree sequences of random digraphs and bipartite graphs

Introduction

We will study the joint distributions of the vertex degrees for three different models of random bipartite graphs. In each case, we construct simpler probability spaces which match these distributions to high precision. The new probability spaces are based on independent binomial distributions and allow asymptotic calculations of any random variable which is a function of the degrees and has maximum at most polynomially greater than its expectation. In Section 2.1 we will show an example of such a calculation. Note that our results are much stronger than contiguity or decreasing total variation distance. These results are similar to those obtained by McKay and Wormald for the case of ordinary (not necessarily bipartite) graphs.

We prefer to use graph terminology, but will also describe the problem in the matrix and other settings. Consider a probability space of $m\times n$ matrices over $\{0,1\}$. Three probability spaces will be considered. In the first case, which we call ${\mathcal{G}}_{p}$, some number $p\in(0,1)$ is specified and each entry of the matrix is independently equal to 1 with probability $p$ and equal to 0 otherwise. In the second case, which we call ${\mathcal{G}}_{k}$, some integer $k$ is specified, and all $m\times n$ binary matrices with exactly $k$ ones have the same probability, and no other matrices are allowed. In the third case, which we call ${\mathcal{G}}_{\textit{{t}}}$, a list of $n$ integers $t_{1},\ldots,t_{n}$ is specified, and all $m\times n$ binary matrices with column sums $t_{1},\ldots,t_{n}$, respectively, are equally likely and no others are allowed.

We can interpret the matrix as a bipartite graph in the standard fashion. Associate distinct vertices $U=\{u_{1},\ldots,u_{m}\}$ with the rows, and $V=\{v_{1},\ldots,v_{n}\}$ with the columns, and place an edge between $u_{i}$ and $v_{j}$ exactly when the matrix entry in position $(i,j)$ equals 1. The row and column sums of the matrix correspond to the degrees of the vertices.

These probability models have also appeared in other settings. Given $m$ bins, at each stage $j=1,\ldots,n$ throw $t_{j}$ balls into distinct bins with all $\binom{m}{t_{j}}$ possible placings equally likely. Then the distribution of the number of balls in each bin ${\textit{{S}}}=(S_{1},\ldots,S_{m})$ can be studied. This model is referred to as allocation by complexes and is precisely our ${\mathcal{G}}_{\textit{{t}}}$ model. If we allow the number of balls thrown to be a random variable $T_{j}$, binomially distributed with parameters $(m,p)$, we attain the ${\mathcal{G}}_{p}$ model.

Similarly, in the coupon collection problem a customer repeatedly buys a random number, $T$, of distinct coupons from a set of $m$ possible different coupons. This covers both our ${\mathcal{G}}_{p}$ case when $T$ is binomially distributed with parameters $(m,p)$ and our ${\mathcal{G}}_{\textit{{t}}}$ case where $T_{j}=t_{j}$ with probability 1. (Here, our vector s describes the number of each coupon collected and t the number of coupons collected at each stage.)

Finally, consider a hypergraph on $m$ vertices. At each stage $j=1,\ldots,n$, choose at random a hyperedge of size $t_{j}$, allowing multi-edges. Then if we set $S_{i}$ to be the number of hyperedges which contain the $i$th vertex, we obtain the ${\mathcal{G}}_{\textit{{t}}}$ model.

If $m=n$, we can also associate the matrix with a directed graph. There are $n$ vertices $\{w_{1},\ldots,w_{n}\}$. A matrix entry equal to 1 in position $(i,j)$ corresponds to a directed edge from $w_{i}$ to $w_{j}$. The case $i=j$ is permitted, so these directed graphs can have loops. The row and column sums of the matrix correspond to the out-degrees and in-degrees, respectively, of the directed graph. We will also treat the case of loop-free digraphs, which correspond to square matrices with zero diagonal. Our methods would also work if some other limited set of matrix entries are required to be zero, but we have not applied them in that case.

We now continue using the bipartite graph formulation. For each of the three probability spaces of random bipartite graphs, we seek to examine the $(m{+}n)$-dimensional joint distribution of the vertex degrees. If $G$ is a bipartite graph on $U\cup V$ (respecting the partition into $U$ and $V$), then ${\textit{{s}}}={\textit{{s}}}(G)=(s_{1},\ldots,s_{m})$ is the list of degrees of $u_{1},\ldots,u_{m}$, and ${\textit{{t}}}={\textit{{t}}}(G)=(t_{1},\ldots,t_{n})$ is the list of degrees of $v_{1},\ldots,v_{n}$. We call the pair $({\textit{{s}}},{\textit{{t}}})$ the degree sequence of $G$.

Define $I_{n}=\{0,1,\ldots,n\}$ and $I_{m,n}=I_{n}^{m}\times I_{m}^{n}$. Also let $G({\textit{{s}}},{\textit{{t}}})$ be the number of (labelled) bipartite graphs on $U\cup V$ with degree sequence $({\textit{{s}}},{\textit{{t}}})$. In the case of $m=n$, we also define $\mathaccent 382{G}({\textit{{s}}},{\textit{{t}}})$ to be the number of loop-free digraphs with in-degrees s and out-degrees t.

For precision we need to distinguish between random variables (written in uppercase) and the values they may take (written in lowercase). For each probability space of random graphs, as determined by the context, ${\textit{{S}}}=(S_{1},\ldots,S_{m})$ will denote the random variable given by the degrees in $U$ and ${\textit{{T}}}=(T_{1},\ldots,T_{n})$ will denote the random variable given by the the degrees in $V$. We will take S to have range $I_{n}^{m}$ and T to have range $I_{m}^{n}$. Also define random variables

As usual, $q$ is an abbreviation for $1-p$.

The ${\mathcal{G}}_{\textit{{t}}}$ model has received wide ranging attention, in particular the distribution of the number of isolated vertices. This is also a natural question in the alternative (non-graph) wordings of the model. It corresponds to the number of empty bins in the allocation model , the number of uncollected coupons in the collector’s problem , the number of isolated vertices in the hypergraph model and the number of zero rows in the binary matrix model . More generally, the number of vertices with a particular degree (or range of degrees) in ${\mathcal{G}}_{\textit{{t}}}$ has been studied in allocation , graph and matrix models . A different extension on this theme is to study the distribution of the number of draws required to go from $i$ to $j$ non-empty bins . In a similar direction, Khakimullin and Enatskaya studied the distribution of the number of draws to exceed a particular lineup in the bins in the ${\mathcal{G}}_{\textit{{t}}}$ model and in the i.i.d. case which includes the ${\mathcal{G}}_{p}$ model as well . The monograph by Kolchin gives many results on ${\mathcal{G}}_{\textit{{t}}}$ phrased as the balls and bins model .

We are interested in asymptotic results as we take $m,n$ roughly equal as they tend to infinity, but another natural option is to fix $m$, the number of vertices in one part, and let $n$, the number of vertices in the other part, tend to infinity. There seems to be a consistent divide in the literature that when considered as a graph the asymptotics of ${\mathcal{G}}_{\textit{{t}}}$ are studied with $m,n$ both tending towards infinity while the balls and bins and coupon collection articles (including those cited above) fix $m$ and take $n$ tending toward infinity. The latter corresponds to fixing the number of bins and taking the number of balls to infinity or having a fixed number of coupons and letting the number of sampling rounds tend to infinity.

In the other two probability models on bipartite graphs, ${\mathcal{G}}_{p}$ and ${\mathcal{G}}_{k}$, two types of results are known: those on the minimum and maximum degrees and those on the number of vertices with a given degree . For results in the digraph counterpart $\mathaccent 382{\mathcal{G}}_{p}$ see (and below). The model ${\mathcal{G}}_{p}$ also appears in papers on ball and bin models. Sometimes the numbers of balls thrown at each stage are allowed to be i.i.d. random variables . If we then set these random variables to be binomially distributed with parameters $m,p$ we recover the ${\mathcal{G}}_{p}$ model. Godbole et. al. study the number of sets of $r$ mutually threatening rooks. This corresponds to the number of vertices with $h\geq r$ weighted by $\binom{h}{r}$ in our ${\mathcal{G}}_{p}$ and ${\mathcal{G}}_{k}$ models.

Palka and Sperling showed that if we fix $p$ such that $np=w(n)\log n=o(n)$, then any fixed number of the smallest and largest degrees are unique in $\mathaccent 382{\mathcal{G}}_{p}$ and in the uniform ${\mathcal{G}}_{\textit{{t}}}$ model . A similar result for the $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$ model is shown by Palka in , where ${\textit{{t}}}=(d,d,\ldots,d)$ and $d=w(n)\log n=o(n)$. There is also some work on the degrees in random digraphs by Jaworski and Karoński who showed, in the case that ${\textit{{t}}}=(d,d,\ldots,d)$ and $d=o(n)$, that the minimum vertex degree in ${\mathcal{G}}_{\textit{{t}}}$ is almost surely the same as that in $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$.

2 Asymptotic notation

As we are dealing with asymptotics of functions of many variables, we must be careful to define our asymptotic notation.

3 Graph models

We now define a sequence of finite probability spaces that we call “models”, with sample space either $I(m,n)=I^{m}_{n}\times I^{n}_{m}$ or $I^{m}_{n}$. The probability measure for each model will be defined using random variables $({\textit{{S}}},{\textit{{T}}})$ or S, respectively, whose distribution equals the respective probability measure. In general our notation will not distinguish between each probability space and its probability measure.

We first consider six models whose probability measures are derived from the degrees of a random bipartite graph or digraph $G$.

($p$-models ${\mathcal{G}}_{p},\mathaccent 382{\mathcal{G}}_{p}$, for $0<p<1$) Generate $G$ by choosing each of the $mn$ possible edges $u_{i}v_{j}$ with probability $p$, such choices being independent. The probability distribution ${\mathcal{G}}_{p}={\mathcal{G}}_{p}(m,n)$ on $I_{m,n}$ is that of the degree sequence $({\textit{{S}}},{\textit{{T}}})$ of $G$. If $m=n$ and the edges $\{u_{i}v_{i}\}$ are forbidden, we obtain the probability distribution $\mathaccent 382{\mathcal{G}}_{p}$ instead, corresponding to the degree sequences of a loop-free digraph where each possible directed edge is chosen independently with probability $p$. Note that $G({\textit{{s}}},{\textit{{t}}})=0$ for many pairs $({\textit{{s}}},{\textit{{t}}})$. We have

where $q=1-p$ and $k=\sum_{i=1}^{m}s_{i}$.

($k$-models ${\mathcal{G}}_{k},\mathaccent 382{\mathcal{G}}_{k}$, for integer $k\geq 0$) Generate $G$ by choosing each of the bipartite graphs on $U\cup V$ having $k$ edges, with equal probability. The probability distribution ${\mathcal{G}}_{k}={\mathcal{G}}_{k}(m,n)$ on $I_{m,n}$ is that of the degree sequence $({\textit{{S}}},{\textit{{T}}})$ of $G$. If $m=n$ and the edges $\{u_{i}v_{i}\}$ are forbidden, we obtain the distribution $\mathaccent 382{\mathcal{G}}_{k}=\mathaccent 382{\mathcal{G}}_{k}(n)$ of the degree-sequences for the uniform probability space of all loop-free digraphs with $k$ edges. We have

(t-models ${\mathcal{G}}_{\textit{{t}}},\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$, for ${\textit{{t}}}\in I_{m}^{n}$) Generate $G$ by choosing each of the bipartite graphs on $U\cup V$ having ${\textit{{t}}}(G)={\textit{{t}}}$, with equal probability. For consistency we can define the random variable T to have the value t, but since this is constant we will define our probability spaces using S only. The probability distribution ${\mathcal{G}}_{\textit{{t}}}={\mathcal{G}}_{\textit{{t}}}(m)$ on $I_{n}^{m}$ is that of the degree sequence S of $G$ in $U$. If $m=n$ and the edges $\{u_{i}v_{i}\}$ are forbidden, we obtain the distribution $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}=\mathaccent 382{\mathcal{G}}_{\textit{{t}}}(n)$ of the in-degrees for the uniform probability distribution of all loop-free digraphs with fixed out-degrees t. For a given ${\textit{{t}}}\in I_{m}^{n}$, we have

The probability spaces ${\mathcal{G}}_{p}$, ${\mathcal{G}}_{k}$ and ${\mathcal{G}}_{\textit{{t}}}$ are clearly related, by mixing and conditioning. In particular, for any event $E\subseteq I_{m,n}$ or $E^{\prime}\subset I_{n}^{m}$, the following hold. Note that the first relationships on lines (2) and (3) are independent of $p$ and assume $0<p<1$.

with similar relations between $\mathaccent 382{\mathcal{G}}_{p}$, $\mathaccent 382{\mathcal{G}}_{k}$ and $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$.

Note that the separate distributions of S and T in ${\mathcal{G}}_{p}$ and ${\mathcal{G}}_{k}$ are elementary. In ${\mathcal{G}}_{p}$, the components of S have independent binomial distributions, while in the ${\mathcal{G}}_{k}$ model S has a multivariate hypergeometric distribution. The difficulty is in quantifying the dependence between S and T when all $m+n$ components are considered together.

4 Binomial models

Our aim is to compare the degree sequence distributions defined above to some distributions derived from independent binomials. Our motivating observation is the known marginal distributions of S and T in the models ${\mathcal{G}}_{p}$ and ${\mathcal{G}}_{k}$.

(Independent models ${\mathcal{I}}_{p},\mathaccent 382{\mathcal{I}}_{p}$, for $0<p<1$) Generate $m$ components distributed $\operatorname{Bin}(n,p)$ and $n$ components distributed $\operatorname{Bin}(m,p)$, all $m+n$ components being independent. The joint distribution on $I_{m,n}$ is ${\mathcal{I}}_{p}={\mathcal{I}}_{p}(m,n)$. If instead we have $m=n$ and the $2n$ components are all distributed $\operatorname{Bin}(n{-}1,p)$, the joint distribution on $I_{n,n}$ is $\mathaccent 382{\mathcal{I}}_{p}=\mathaccent 382{\mathcal{I}}_{p}(n)$. We have

(Binomial $p$-models ${\mathcal{B}}_{p},\mathaccent 382{\mathcal{B}}_{p}$, for $0<p<1$) The distribution ${\mathcal{B}}_{p}={\mathcal{B}}_{p}(m,n)$ on $I_{m,n}$ is the conditional distribution of ${\mathcal{I}}_{p}$ subject to $\sum_{i=1}^{m}S_{i}=\sum_{j=1}^{n}T_{j}$. For $m=n$, the distribution $\mathaccent 382{\mathcal{B}}_{p}=\mathaccent 382{\mathcal{B}}_{p}(n)$ on $I_{n,n}$ is obtained from $\mathaccent 382{\mathcal{I}}_{p}$ by the same conditioning. We have

and similarly for $\mathaccent 382{\mathcal{B}}_{p}$.

(Binomial $k$-models ${\mathcal{B}}_{k},\mathaccent 382{\mathcal{B}}_{k}$, for integer $k\geq 0$) The distribution ${\mathcal{B}}_{k}={\mathcal{B}}_{k}(m,n)$ on $I_{m,n}$ is the conditional distribution of ${\mathcal{I}}_{p}$ subject to $\sum_{i=1}^{m}S_{i}=\sum_{j=1}^{n}T_{j}=k$. For $m=n$, $\mathaccent 382{\mathcal{B}}_{k}=\mathaccent 382{\mathcal{B}}_{k}({m,n})$ is derived from $\mathaccent 382{\mathcal{I}}_{p}$ in the same way. In both cases, the distribution doesn’t depend on $p$. We have

In each case S and T have independent multivariate hypergeometric distributions.

(Binomial t-models ${\mathcal{B}}_{\textit{{t}}},\mathaccent 382{\mathcal{B}}_{\textit{{t}}}$, for ${\textit{{t}}}\in I_{m}^{n}$) The distribution ${\mathcal{B}}_{\textit{{t}}}={\mathcal{B}}_{\textit{{t}}}(m,n)$ on $I_{n}^{m}$ is the distribution of S when $({\textit{{S}}},{\textit{{T}}})$ has distribution ${\mathcal{B}}_{k}$ for $k=\sum_{j=1}^{n}t_{j}$. For $m=n$, $\mathaccent 382{\mathcal{B}}_{\textit{{t}}}=\mathaccent 382{\mathcal{B}}_{\textit{{t}}}(n)$ is derived from $\mathaccent 382{\mathcal{B}}_{k}$ in the same way. For a given ${\textit{{t}}}\in I_{m}^{n}$, we have

In each case, S has a multivariate hypergeometric distribution.

(Integrated $p$-models ${\mathcal{V}}_{p},\mathaccent 382{\mathcal{V}}_{p}$, for $0<p<1$) The distribution ${\mathcal{V}}_{p}={\mathcal{V}}_{p}(m,n)$ on $I_{m,n}$ is a mixture of ${\mathcal{B}}_{p^{\prime}}$ distributions, while for $m=n$ the distribution $\mathaccent 382{\mathcal{V}}_{p}=\mathaccent 382{\mathcal{V}}_{p}(n)$ on $I_{n,n}$ is a mixture of $\mathaccent 382{\mathcal{B}}_{p^{\prime}}$ distributions. Let

Our main theorems will show that, under certain conditions, ${\mathcal{G}}_{p}$ is very close to ${\mathcal{V}}_{p}$, ${\mathcal{G}}_{k}$ to ${\mathcal{B}}_{k}$, and ${\mathcal{G}}_{\textit{{t}}}$ to ${\mathcal{B}}_{\textit{{t}}}$. Similar relationships hold for the digraph models.

5 The main theorems

Note that (4) implies x(1-x)=\Omega\bigl{(}(\log n)^{-1}\bigr{)}.

For $\varepsilon>0$, a vector $(x_{1},x_{2},\ldots,x_{N})$ will be called $\varepsilon$-regular if

uniformly for $i=1,\ldots,N$. We say that $({\textit{{s}}},{\textit{{t}}})$ is $\varepsilon$-regular if $\sum_{i=1}^{m}s_{i}=\sum_{j=1}^{n}t_{j}$ and ${\textit{{s}}},{\textit{{t}}}$ are both $\varepsilon$-regular.

Finally, define $\lambda_{m}({\textit{{t}}})=(mn)^{-1}\sum_{j=1}^{n}t_{j}$. If $\sum_{i=1}^{m}s_{i}=\sum_{j=1}^{n}t_{j}$, the common value of $\lambda_{n}({\textit{{s}}})$ and $\lambda_{m}({\textit{{t}}})$ will be denoted by $\lambda$. Note that $\lambda$ is the value in $$that gives the density of a bipartite graph with degrees$({\textit{{s}}},{\textit{{t}}})$, relative to$K_{m,n}$. In the case of loop-free digraphs,$\lambda\in[0,1-1/n]$.

We now state the theorems that are the main contribution of this paper. Their proofs will be given in Section 4, after some preliminary lemmas are proved in Section 3.

Let constants $a,b>0$ satisfy $a+b<\tfrac{1}{2}$. Then there is a constant $\varepsilon=\varepsilon(a,b)>0$ such that the following holds. Let ${\mathcal{D}}$ and ${\mathcal{D}}^{\prime}$ be probability spaces on $I_{m,n}$ in one of the following cases.

$(m,n,p)$ is $(a,\varepsilon)$-acceptable and $({\mathcal{D}},{\mathcal{D}}^{\prime})=({\mathcal{G}}_{p},{\mathcal{V}}_{p})$,

$m=n$, $(n,n,p)$ is $(a,\varepsilon)$-acceptable and $({\mathcal{D}},{\mathcal{D}}^{\prime})=(\mathaccent 382{\mathcal{G}}_{p},\mathaccent 382{\mathcal{V}}_{p})$,

$(m,n,k/mn)$ is $(a,\varepsilon)$-acceptable and $({\mathcal{D}},{\mathcal{D}}^{\prime})=({\mathcal{G}}_{k},{\mathcal{B}}_{k})$,

$m=n$, $(n,n,k/n^{2})$ is $(a,\varepsilon)$-acceptable and $({\mathcal{D}},{\mathcal{D}}^{\prime})=(\mathaccent 382{\mathcal{G}}_{k},\mathaccent 382{\mathcal{B}}_{k})$,

Let $E\subseteq I_{m,n}$ be an event. Then, under the conditions of Theorem 1,

In particular, ${\mathcal{G}}_{p}$ and ${\mathcal{B}}_{p}$ are contiguous; i.e., $\operatorname{Prob}_{{\mathcal{G}}_{p}}(E)\to 0$ if and only if $\operatorname{Prob}_{{\mathcal{B}}_{p}}(E)\to 0$, and similarly for $\mathaccent 382{\mathcal{G}}_{p}$ and $\mathaccent 382{\mathcal{B}}_{p}$.

Let constants $a,b>0$ satisfy $a+b<\tfrac{1}{2}$. Then there is a constant $\varepsilon=\varepsilon(a,b)>0$ such that the following holds whenever $(m,n,\lambda_{m}({\textit{{t}}}))$ is $(a,\varepsilon)$-acceptable and t is $\varepsilon$-regular. Let ${\mathcal{D}}$ and ${\mathcal{D}}^{\prime}$ be probability spaces on $I_{n}^{m}$ in one of the following cases.

$({\mathcal{D}},{\mathcal{D}}^{\prime})=({\mathcal{G}}_{\textit{{t}}},{\mathcal{B}}_{\textit{{t}}})$,

$m=n$ and $({\mathcal{D}},{\mathcal{D}}^{\prime})=(\mathaccent 382{\mathcal{G}}_{\textit{{t}}},\mathaccent 382{\mathcal{B}}_{\textit{{t}}})$.

A weak corollary of these theorems is that each of the distribution pairs $({\mathcal{G}}_{p},{\mathcal{V}}_{p})$, $(\mathaccent 382{\mathcal{G}}_{p},\mathaccent 382{\mathcal{V}}_{p})$, $({\mathcal{G}}_{k},{\mathcal{B}}_{k})$, $(\mathaccent 382{\mathcal{G}}_{k},\mathaccent 382{\mathcal{B}}_{k})$, $({\mathcal{G}}_{\textit{{t}}},{\mathcal{B}}_{\textit{{t}}})$ and $(\mathaccent 382{\mathcal{G}}_{\textit{{t}}},\mathaccent 382{\mathcal{B}}_{\textit{{t}}})$ have total variation distance $O(n^{-b})$ under the stated conditions.

The proofs of the theorems will be presented in Sections 3 and 4. Meanwhile, we will give an example that illustrates how the theorems can be applied.

Some useful lemmas and an example

We first record a few elementary properties.

If $\sum_{i=1}^{m}s_{i}=\sum_{j=1}^{n}t_{j}=k$ and $pqmn\to\infty$, then

uniformly over ${\textit{{s}}},{\textit{{t}}}$.

In ${\mathcal{I}}_{p}$, both $\sum_{i=1}^{m}S_{i}$ and $\sum_{j=1}^{n}T_{j}$ have the distribution $\operatorname{Bin}(mn,p)$. Therefore

For the last step we use that the central part of the sum is approximately normal and sum it with the Euler-Maclaurin formula, while the two tails of the sum are negligible in comparison. The first claim now follows from the formulas for $\operatorname{Prob}_{{\mathcal{B}}_{p}}({\textit{{S}}}={\textit{{s}}}\wedge{\textit{{T}}}={\textit{{t}}})$ and $\operatorname{Prob}_{{\mathcal{I}}_{p}}({\textit{{S}}}={\textit{{s}}}\wedge{\textit{{T}}}={\textit{{t}}})$. The second claim is proved in the same manner. ∎

$K_{p}(p^{\prime})$ is a normal density with mean $p$ and variance $pq/(2mn)$, so we just need to apply standard normal tail bounds to the definition of $V(p)$. ∎

The next lemma demonstrates how statistics of variables in ${\mathcal{B}}_{p}$ can be converted into statistics in ${\mathcal{V}}_{p}$. Note that $X$ can be the indicator variable of an event, so the lemma applies to probabilities as well.

Let $X$ be a random variable on $I_{m,n}$. Then

We now provide an example of how Theorem 1(b) can be applied to random digraphs. Since this is only an illustration, we will not attempt to treat all values of the parameters or to obtain the best possible error terms.

Let $G$ be a random loop-free digraph on $n$ vertices and edge probability $p=\tfrac{1}{2}$. For convenience we will assume that $n$ is even, though treatment of the odd case would be much the same. As usual, $S_{1},\ldots,S_{n}$ are the out-degrees of the vertices, and $T_{1},\ldots,T_{n}$ are the in-degrees. Let $X,Y$ be random variables which count the vertices with out-degree at most $\tfrac{n}{2}-1$, and the vertices with in-degree at most $\tfrac{n}{2}-1$, respectively. It is easy to see that each of $X$ and $Y$ has a distribution exactly $\operatorname{Bin}(n,\tfrac{1}{2})$, but that $X$ and $Y$ are not independent. Our aim will be to find their asymptotic joint distribution.

We will first calculate some properties of binomial distributions truncated at the centre. Application of model $\mathaccent 382{\mathcal{V}}_{1/2}$ requires us to consider probabilities close to $\tfrac{1}{2}$.

The following hold when $\varepsilon>0$ is sufficiently small. Let $n$ be even and let $p=\tfrac{1}{2}+\delta$ where $\delta=O(n^{-1+\varepsilon})$. For $0\leq k\leq\frac{n}{2}-1$ define

and $P(\delta)=\sum_{k=0}^{n/2-1}b(p,k)$. Then

Now define two random variables, $Z^{-}_{\delta}$ by truncating $\operatorname{Bin}(n-1,p)$ to $[0,\tfrac{1}{2}n-1]$, and $Z^{+}_{\delta}$ by truncating $\operatorname{Bin}(n-1,p)$ to $[\tfrac{1}{2}n,n-1]$. Then

Define $s_{j}=b(p,\frac{1}{2}n-1-j)$. From we have for $j=O(n^{1/2+\varepsilon})$ that

Suppose $n$ is even and $x,y$ are integers with $x,y=O(n^{-1/2+\varepsilon})$ for sufficiently small $\varepsilon>0$. Then

Theorem 1(b) tells us to calculate the probability in $\mathaccent 382{\mathcal{V}}_{1/2}$, for which we need the probability in $\mathaccent 382{\mathcal{B}}_{p}$ when $p\approx\tfrac{1}{2}$. For integers $x,y$, define events

Recall that $\mathaccent 382{\mathcal{B}}_{p}$ is $\mathaccent 382{\mathcal{I}}_{p}$ conditioned on event $E_{\Sigma}$ so, applying Bayes’ rule twice,

We have already computed $\operatorname{Prob}_{\mathaccent 382{\mathcal{I}}_{p}}(E_{\Sigma})$ in (5); for $p=\tfrac{1}{2}+o(1)$ it is

Now consider $\operatorname{Prob}_{\mathaccent 382{\mathcal{I}}_{p}}(E_{\Sigma}\mid E(x,y))$. Under this conditioning, symmetry implies that $\sum_{i}S_{i}$ has the same distribution as the sum of $\tfrac{1}{2}n+x$ copies of $Z^{-}_{\delta}$ and $\tfrac{1}{2}n-x$ copies of $Z^{+}_{\delta}$, all of these being independent. A similar fact holds for $\sum_{j}T_{j}$, which is in addition independent of $\sum_{i}S_{i}$ since we are operating in $\mathaccent 382{\mathcal{I}}_{p}$. Also recall that the binomial distribution and therefore its truncations and their convolutions are log-concave, so we know from that $\varDelta=\sum_{i}S_{i}-\sum_{j}T_{j}$, in $\mathaccent 382{\mathcal{I}}_{p}$ conditioned on $E(x,y)$, satisfies a local central-limit theorem. Using Lemma 7, we calculate

Finally, consider $\operatorname{Prob}_{\mathaccent 382{\mathcal{I}}_{p}}(E(x,y))$. Since the $2n$ events $S_{i}\leq\tfrac{1}{2}n-1,T_{j}\leq\tfrac{1}{2}n-1$ are independent in $\mathaccent 382{\mathcal{I}}_{p}$, $X$ and $Y$ are independent Binomial variables $\operatorname{Bin}(n,P(\delta))$. Using (6) and the normal approximation for the binomial distribution, we have

Applying this to (9) together with (10) and (11), we find that

Now we apply Lemma 6 to pass the result to $\mathaccent 382{\mathcal{V}}_{1/2}$. Multiplying by $K_{1/2}(\tfrac{1}{2}+\delta)$ and integrating, we obtain the formula in the theorem, which holds for $\mathaccent 382{\mathcal{G}}_{1/2}$ on account of Theorem 1(b). ∎

A corollary of the theorem is that $X-Y$ and $X+Y$ have asymptotically independent normal distributions, apart from necessarily having the same parity.

Under the conditions of the theorem, let $\alpha,\beta$ be integers of the same parity such that $\alpha,\beta=O(n^{1/2+\varepsilon})$. Then

More complex information could also be obtained, such as the distributions of all the order statistics of the degrees, but the calculations would be considerably more intricate. See for similar calculations for ordinary graphs.

Properties of likely degree sequences

Another consequence of Theorem 10 is the following.

We start by reminding the reader of a classical algorithm called “reservoir sampling”, attributed by Knuth to Alan G. Waterman [24, p. 144]. Let $Y^{(i)}_{a_{i}+1},\ldots,Y^{(i)}_{\lvert A_{i}\rvert}$ be independent random variables, where $Y^{(i)}_{j}$ has the discrete uniform distribution on $\{1,2,\ldots,j\}$. Now suppose $A_{i}=\{w_{1},\ldots,w_{\lvert A_{i}\rvert}\}$. Execute the following algorithm:

Define $X_{i}=X_{i}(Y^{(i)}_{a_{i}+1},\ldots,Y^{(i)}_{\lvert A_{i}\rvert})$ to be the value of $\{x_{1},\ldots,x_{a_{i}}\}$ when the algorithm finishes. The raison d’être of the algorithm, which is easy to check, is that $X_{i}$ has distribution $\binom{A_{i}}{a_{i}}$; i.e., it is uniform. It is also easy to check that the maximum change to $X_{i}$ resulting from a change in a single $Y^{(i)}_{j}$ is that one element is replaced by another.

Therefore, we can apply Theorem 10 if we consider $f({\textit{{X}}})$ as a function of all the independent variables $\{Y^{(i)}_{j}\}$. If $a_{i}<\lvert A_{i}\rvert/2$, we can represent $X_{i}$ by its complement; this justifies the term $\min\{a_{i},\lvert A_{i}\rvert-a_{i}\}$ in the theorem statement. ∎

We next apply these concentration inequalities to show that certain events are very likely in our probability spaces.

The following are true for sufficiently small $\varepsilon>0$.

Suppose that $(m,n,p)$ and $(m,n,k/mn)$ are $(a,\varepsilon)$-acceptable. Then

for ${\mathcal{D}}$ being any of ${\mathcal{G}}_{p}$, ${\mathcal{G}}_{k}$, ${\mathcal{I}}_{p}$, ${\mathcal{B}}_{p}$, ${\mathcal{B}}_{k}$, or ${\mathcal{V}}_{p}$. The same is true for $m=n$ when ${\mathcal{D}}$ is any of $\mathaccent 382{\mathcal{G}}_{p}$, $\mathaccent 382{\mathcal{G}}_{k}$, $\mathaccent 382{\mathcal{I}}_{p}$, $\mathaccent 382{\mathcal{B}}_{p}$, $\mathaccent 382{\mathcal{B}}_{k}$, or $\mathaccent 382{\mathcal{V}}_{p}$.

If ${\textit{{t}}}\in I_{m}^{n}$ is $\varepsilon$-regular, and $(m,n,\lambda_{m}({\textit{{t}}}))$ is $(a,\varepsilon)$-acceptable, then

for ${\mathcal{D}}$ being ${\mathcal{G}}_{\textit{{t}}}$ or ${\mathcal{B}}_{\textit{{t}}}$. The same is true for $m=n$ when ${\mathcal{D}}$ is either of $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$ or $\mathaccent 382{\mathcal{B}}_{\textit{{t}}}$.

By symmetry, we need only show that S is almost always $\varepsilon$-regular.

In the case that ${\mathcal{D}}$ is ${\mathcal{G}}_{p}$ or ${\mathcal{I}}_{p}$, each $S_{i}$ has the binomial distribution $\operatorname{Bin}(n,p)$, and $K$ has the distribution $\operatorname{Bin}(mn,p)$. Therefore, by Corollary 11,

The cases that ${\mathcal{D}}$ is ${\mathcal{G}}_{k}$, ${\mathcal{B}}_{p}$, or ${\mathcal{B}}_{k}$ follow, since these are the same as slices of ${\mathcal{G}}_{p}$ or ${\mathcal{I}}_{p}$ of size $n^{-O(1)}$, using $p=k/mn$. Also, the distribution of S in ${\mathcal{B}}_{\textit{{t}}}$ is the same as in ${\mathcal{B}}_{k}$ for $k=\sum_{j=1}^{n}t_{j}$, so that case follows too.

For ${\mathcal{D}}={\mathcal{G}}_{\textit{{t}}}$, note that each $S_{i}$ is the sum of independent variables $X_{1},\ldots,X_{n}$, where $X_{j}$ is a Bernoulli random variable with mean $t_{j}/m$. The theorem thus follows using the same argument as we used for ${\mathcal{G}}_{p}$.

Finally consider ${\mathcal{D}}={\mathcal{V}}_{p}$. Taking $X$ to be the indicator of the event that S is not $\varepsilon$-regular, Lemmas 5–6 give

For the digraph models, the proofs are essentially the same. ∎

The following concentration results will form a key part of the proof of Theorem 1.

The following are true for sufficiently small $\varepsilon>0$.

Suppose that $(m,n,p)$ and $(m,n,k/mn)$ are $(a,\varepsilon)$-acceptable. Then

when ${\mathcal{D}}$ is ${\mathcal{G}}_{p}$ or ${\mathcal{G}}_{k}$. When $m=n$, the same bounds hold when ${\mathcal{D}}$ is $\mathaccent 382{\mathcal{G}}_{p}$ or $\mathaccent 382{\mathcal{G}}_{k}$.

If ${\textit{{t}}}\in I_{m}^{n}$ is $\varepsilon$-regular, and $(m,n,\lambda_{m}({\textit{{t}}}))$ is $(a,\varepsilon)$-acceptable, then (13) holds when ${\mathcal{D}}$ is ${\mathcal{G}}_{\textit{{t}}}$, and when $m=n$ and ${\mathcal{D}}$ is $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$.

If $m=n$, $(n,n,p)$ and $(n,n,k/n^{2})$ are $(a,\varepsilon)$-acceptable, then

when ${\mathcal{D}}$ is $\mathaccent 382{\mathcal{G}}_{p}$ or $\mathaccent 382{\mathcal{G}}_{k}$.

If $m=n$, $(n,n,\lambda_{n}({\textit{{t}}}))$ is $(a,\varepsilon)$-acceptable and ${\textit{{t}}}\in I_{n}^{n}$ is $\varepsilon$-regular, then (15) holds when ${\textit{{T}}}={\textit{{t}}}$ and ${\mathcal{D}}$ is $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$.

Write $R=\sum_{i=1}^{m}(S_{i}-n\varLambda)^{2}$. For $i=1,\ldots,m$ and $j=1,\ldots,n$, let $X_{ij}$ be the indicator for an edge from $u_{i}$ to $v_{j}$. Define $\varDelta_{ii^{\prime}jj^{\prime}}=(X_{ij}-X_{i^{\prime}j})(X_{ij^{\prime}}-X_{i^{\prime}j^{\prime}})$. Then we have

Now define $R^{*}=\sum_{i=1}^{m}\min\{(S_{i}-n\varLambda)^{2},m^{1+2\varepsilon}\}$. If S is $\varepsilon$-regular and $S_{j}$ is changed by 1 for some $j$, which changes $\varLambda$ by $1/mn$, then $\min\{(S_{i}-n\varLambda)^{2},m^{1+2\varepsilon}\}$ changes by $O(m^{1/2+\varepsilon})$ for $i=j$ and by $O(m^{-1/2+\varepsilon})$ for $i\neq j$. Consequently, $R^{*}$ changes by $O(m^{1/2+\varepsilon})$. Applying Theorem 10, we find that

for ${\mathcal{D}}={\mathcal{G}}_{p}$. It also holds for ${\mathcal{D}}={\mathcal{G}}_{\textit{{t}}}$, using Theorem 12 in the same way.

We also have that $\varLambda$ is fixed at the value $\lambda_{m}({\textit{{t}}})=(mn)^{-1}\sum_{j=1}^{n}t_{j}$ in ${\mathcal{G}}_{\textit{{t}}}$ and that

by (12). From these bounds, inequality (13) follows for ${\mathcal{G}}_{p}$ and ${\mathcal{G}}_{\textit{{t}}}$, and (14) follows for ${\mathcal{G}}_{p}$ by symmetry. By choosing $p=k/mn$ and noting that ${\mathcal{G}}_{k}$ is a slice of size $n^{-O(1)}$ of ${\mathcal{G}}_{p}$, the theorem is proved for ${\mathcal{G}}_{k}$ too.

We now prove part (d); take ${\mathcal{D}}=\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$, with t being $\varepsilon$-regular and $(n,n,\lambda_{n}({\textit{{t}}}))$ being $(a,\varepsilon)$-acceptable. We have

In the notation of Theorem 12 set $A_{j}=[n]\setminus\{j\}$ and $a_{j}=t_{j}$ for each $j\in[n]$. Then in the probability space X, $X_{j}$ is the set of indices of vertices incident with $v_{j}$ in $\mathaccent 382{\mathcal{G}}_{\textit{{t}}}$. Note $S_{i}=|\{j:u_{i}\in X_{j}\}|$ and two sets being minimally different in the $j$-th component corresponds to two graphs in which one of the $t_{j}$ edges incident with vertex $v_{j}$ is incident with different vertices in $U$. This means, as t is $\varepsilon$-regular, $c_{j}=O(n^{1/2+\varepsilon})$ for each $j$ and we can apply Theorem 12 to conclude that (d) holds.

Proofs of the main theorems

In this section we will give the proofs of the theorems and corollary stated in Section 1.5. The bases for our analysis are the following enumerative results of Canfield, Greenhill and McKay . Also see Barvinok and Hartigan for an overlapping result.

Let $a,b>0$ be constants such that $a+b<\frac{1}{2}$. Then there is a constant $\varepsilon_{0}=\varepsilon_{0}(a,b)>0$ such that the following is true for any fixed $\varepsilon$ with $0<\varepsilon\leq\varepsilon_{0}$. If $({\textit{{s}}},{\textit{{t}}})$ is $\varepsilon$-regular, then

for $\sum_{i}s_{i}=\sum_{j}t_{j}=k$, where the last step follows by Stirling’s formula and, as always, we are assuming that $\varepsilon$ is sufficiently small.

We wish to show that (18) closely matches the probability in ${\mathcal{V}}_{p}$. Define $P(p,{\textit{{s}}},{\textit{{t}}})=\operatorname{Prob}_{{\mathcal{B}}_{p}}({\textit{{S}}}={\textit{{s}}}\wedge{\textit{{T}}}={\textit{{t}}})$. By the definition of ${\mathcal{V}}_{p}$, we have

We will divide the integral into three parts. Define $J_{p}=[p-n^{-1+3\varepsilon},p+n^{-1+3\varepsilon}]$. By Lemma 4 and (17), for $p^{\prime}\in J_{p}$ and $({\textit{{s}}},{\textit{{t}}})\notin B$, we have

which matches (18) when the value of $P(p,{\textit{{s}}},{\textit{{t}}})$ given by Lemma 4 is substituted. This completes the proof of the first claim of Theorem 1(a). The next two claims follow on summing the first claim over all $({\textit{{s}}},{\textit{{t}}})$. For the variance, we can apply the formula for the expectation to argue

For the third line we have used the obvious fact that the minimum in the first line occurs somewhere in the interval $[\min X,\max X]$.

which matches $\operatorname{Prob}_{{\mathcal{B}}_{k}}({\textit{{S}}}={\textit{{s}}}\wedge{\textit{{T}}}={\textit{{t}}})$ up to the error term. Similarly for Theorem 1(d).

Theorem 3 follows from a similar argument, on noting that the $\varepsilon$-regularity of t implies

Finally, we prove Corollary 2 for ${\mathcal{D}}={\mathcal{G}}_{p}$, which is representative of the four cases. In view of Theorem 1, it will suffice to prove that

if $\operatorname{Prob}_{{\mathcal{B}}_{p}}(E)\to 0$. Define

Now note that, by (20), for $\lvert p^{\prime}-p\rvert\leq y\sqrt{pq/2mn}$ and $\lvert k-pmn\rvert\leq y\sqrt{pqmn}$ we have

Since $\int K_{p}(p^{\prime})\,dp<1$, we have proved that

which gives (21) when the value of $y$ is substituted. To prove the statement for the case ${\mathcal{D}}={\mathcal{B}}_{p}$, redefine $y$ and $\hat{E}$ by replacing each instance of ${\mathcal{B}}_{p}$ with ${\mathcal{V}}_{p}$. and then proceed in the same fashion (although in this case because of the direction of the inequality it is enough to note that the tails of the integral in (22) are positive; we do not need to show an upper bound as in the above proof for ${\mathcal{D}}={\mathcal{G}}_{p}$).

Concluding remarks

A theorem similar to Theorem 15 holds also in the sparse domain. This was shown by Greenhill, McKay and Wang in the case that (\max_{i}s_{i})(\max_{j}t_{j})=o\bigl{(}(\sum_{i}s_{i})^{2/3}\bigr{)} . That theorem can be used to develop a parallel theory of degree sequences in that domain, though some of the methods used in this paper must be replaced. However the lack of a precise enumeration in the gap between the sparse domain and the dense domain of Theorem 15 currently thwarts a theory which spans both the sparse and dense domains.

References