Factorisation of the complete bipartite graph into spanning semiregular factors

Mahdieh Hasheminezhad
Department of Computer Science
Yazd University
Yazd, Iran
[email protected] Brendan D. McKay
School of Computing
Australian National University
Canberra, ACT 2601, Australia
[email protected]

Abstract

We enumerate factorisations of the complete bipartite graph into spanning semiregular graphs in several cases, including when the degrees of all the factors except one or two are small. The resulting asymptotic behaviour is seen to generalise the number of semiregular graphs in an elegant way. This leads us to conjecture a general formula when the number of factors is vanishing compared to the number of vertices. As a corollary, we find the average number of ways to partition the edges of a random semiregular bipartite graph into spanning semiregular subgraphs in several cases. Our proof of one case uses a switching argument to find the probability that a set of sufficiently sparse semiregular bipartite graphs are edge-disjoint when randomly labelled.

1 Introduction

A classical problem in enumerative graph theory is the asymptotic number of 0-1 matrices with uniform row and column sums; equivalently, semiregular bipartite graphs.

We will consider all bipartite graphs to have bipartition $(V_{1},V_{2})$ where $\mathopen{|}V_{1}\mathclose{|}=m$ and $\mathopen{|}V_{2}\mathclose{|}=n$ . An $(m,n,\lambda)$ -semiregular bipartite graph has every degree in $V_{1}$ equal to $\lambda n$ and every degree in $V_{2}$ equal to $\lambda m$ . Of course, for such a graph to exist we must have $0\leq\lambda\leq 1$ and $\lambda m,\lambda n$ must be integers. We will tacitly assume that these elementary conditions hold throughout the paper for every mentioned semiregular graph. The parameter $\lambda$ will be called the density. Define $R_{\lambda}(m,n)$ to be the number of $(m,n,\lambda)$ -semiregular bipartite graphs. The asymptotic determination of $R_{\lambda}(m,n)$ as $n\to\infty$ with $m=m(n)$ and $\lambda=\lambda(n)$ is not yet complete, but the known values fit a simple formula.

Theorem 1.1.

Let $n\to\infty$ with $m\leq n$ . Then

R_{\lambda}(m,n)\sim\frac{\displaystyle\binom{n}{\lambda n}^{\!m}\binom{m}{\lambda m}^{\!n}}{\displaystyle\binom{mn}{\lambda mn}}\,(1-1/m)^{(m-1)/2}

in the following cases.

1.

$\lambda=o\bigl{(}(mn)^{-1/4}\bigr{)}$ .
2.

For sufficiently small $\varepsilon>0$ , $(1-2\lambda)^{2}\bigl{(}1+\lower 0.6458pt\hbox{\large$\textstyle\frac{5m}{6n}$}+\lower 0.6458pt\hbox{\large$\textstyle\frac{5n}{6m}$}\bigr{)}\leq(4-\varepsilon)\lambda(1-\lambda)\log n$ and $n=o\bigl{(}\lambda(1-\lambda)m^{1+\varepsilon}\bigr{)}$ .
3.

For some $\varepsilon>0$ , $2\leq m=O\bigl{(}(\lambda(1-\lambda)n)^{1/2-\varepsilon}\bigr{)}$ .
4.

$\lambda\leq c$ for a sufficiently small constant $c$ , $n=O(\lambda^{1/2-\varepsilon}m^{3/2-\varepsilon})$ for some $\varepsilon>0$ , and $\lambda m\geq\log^{K}n$ for every $K$ .

Proof.

Note that $(1-1/m)^{(m-1)/2}\to e^{-1/2}$ if $m\to\infty$ . Case 1 covers the sparse case and was proved by McKay and Wang [11]. Case 2 applies when $m$ and $n$ are not very much different and the graph is very dense, while Case 3 covers all densities when $n$ is much larger than $m$ . Case 2 was proved by Greenhill and McKay [4], and Case 3 by Canfield and McKay [1]. Case 4, proved by Liebenau and Wormald [8], covers a wide range of densities and moderately large $n/m$ . ∎

Theorem 1.1 does not cover all $(m,n,\lambda)$ . For example $\lambda=\frac{1}{2},m=n^{2/3}$ is missing, and so is $\lambda=\frac{1}{m},m=n^{1/2}$ . However, based on numerical evidence a strong form of the theorem was conjectured in [1] to hold for all $(m,n,\lambda)$ .

We can consider $R_{\lambda}(m,n)$ as counting the partitions of the edges of $K_{m,n}$ into two spanning semiregular subgraphs, one of density $\lambda$ and one of density $1-\lambda$ . This suggests a generalization: how many ways are there to partition the edges of $K_{m,n}$ into more than two spanning semiregular subgraphs, of specified densities?

For positive numbers $\lambda_{0},\ldots,\lambda_{k}$ with sum 1, define $R(m,n;\lambda_{0},\ldots,\lambda_{k})$ to be the number of ways to partition the edges of $K_{m,n}$ into spanning semiregular subgraphs of density $\lambda_{0},\ldots,\lambda_{k}$ . We conjecture that for $k=o(m)$ , the asymptotic answer is a simple generalisation of Theorem 1.1.

Conjecture 1.2.

Let $\lambda_{0},\ldots,\lambda_{k}$ be positive numbers such that $\sum_{i=0}^{k}\lambda_{i}=1$ . Then, if $n\to\infty$ with $2\leq m\leq n$ , and $1\leq k=o(m)$ , $R(m,n;\lambda_{0},\ldots,\lambda_{k})\sim R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})$ , where (using multinomial coefficients)

R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})=\frac{\displaystyle\binom{n}{\lambda_{0}n,\ldots,\lambda_{k}n}^{\!m}\binom{m}{\lambda_{0}m,\ldots,\lambda_{k}m}^{\!n}}{\displaystyle\binom{mn}{\lambda_{0}mn,\ldots,\lambda_{k}mn}}\,(1-1/m)^{k(m-1)/2}.

We will prove the conjecture in six cases.

Theorem 1.3.

Conjecture 1.2 holds in the following cases.

(a)

$k=1$ and one of the conditions of Theorem 1.1 holds.
(b)

$k\geq 2$ , $m\leq n$ and $m^{-1}n^{3}\bigl{(}\sum_{i=1}^{k}\lambda_{i}\bigr{)}^{3}=o(1)$ .
(c)

$k\geq 2$ , $m\leq n$ and $m^{1/2}n\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}=o(1)$ .
(d)

$m=n$ , $k=o(n^{6/7})$ and $\lambda_{1}=\cdots=\lambda_{k}=\frac{1}{n}$ (the case of Latin rectangles).
(e)

$(m,n,\lambda_{1})$ satisfies condition 2 of Theorem 1.1, and $\lambda_{2}+\cdots+\lambda_{k}=O(n^{-1+\varepsilon})$ for sufficiently small $\varepsilon>0$ .
(f)

$m=O(1)$ and $1\leq k\leq m-1$ . In this case we do not need the condition $k=o(m)$ .

Part (a) is just a restatement of Theorem 1.1. Part (b) will be proved using [9]. Part (c) will follow from a switching argument applied to the probability of two randomly labelled semiregular graphs being edge-disjoint. Part (d) is a consequence of [3]. Part (e) will follow from a combination of [4] and Part (b). Part (f) will be proved using the Central Limit Theorem.

Conjecture 1.4.

Let $\lambda_{1},\ldots,\lambda_{k},\lambda$ be positive numbers such that $\sum_{i=1}^{k}\lambda_{i}=\lambda$ . Then, if $n\to\infty$ with $2\leq m\leq n$ , and $1\leq k=o(m)$ , the average number of ways to partition the edges of a uniform random $(m,n,\lambda)$ -semiregular bipartite graph into spanning semiregular subgraphs of density $\lambda_{1},\ldots,\lambda_{k}$ is asymptotically

	$\displaystyle\frac{R^{\prime}(m,n;1-\lambda,\lambda_{1}\ldots,\lambda_{k})}{R^{\prime}(m,n;1-\lambda,\lambda)}$
	$\displaystyle{\kern 40.00006pt}=\frac{\displaystyle\binom{\lambda n}{\lambda_{1}n,\ldots,\lambda_{k}n}^{\!m}\binom{\lambda m}{\lambda_{1}m,\ldots,\lambda_{k}m}^{\!n}}{\displaystyle\binom{\lambda mn}{\lambda_{1}mn,\ldots,\lambda_{k}mn}}\,(1-1/m)^{(k-1)(m-1)/2}.$

Note that Conjecture 1.4 holds if the formula in Theorem 1.1 holds for $(m,n,\lambda)$ and Conjecture 1.2 holds for $(m,n,1-\lambda,\lambda_{1},\ldots,\lambda_{k})$ . Thus, many cases of Conjecture 1.4 follow from Theorem 1.1 and Theorem 1.3.

For integer $x\geq 0$ , $(N)_{x}$ denotes the falling factorial $N(N-1)\cdots(N-x+1)$ . It will be convenient to have an approximation for $R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})$ when $\sum_{i=1}^{k}\lambda_{i}$ is small.

Lemma 1.5.

Let $\lambda_{0},\ldots,\lambda_{k}$ be positive numbers such that $\sum_{i=0}^{k}\lambda_{i}=1$ . Define $\lambda=\sum_{i=1}^{k}\lambda_{i}$ and assume $m\leq n$ and $\lambda=O(m^{-1/4}n^{-1/4})$ . Then

	$\displaystyle R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})$	$\displaystyle=\prod_{i=1}^{k}\frac{(\lambda_{i}mn)!}{(\lambda_{i}m)!^{n}\,(\lambda_{i}n)!^{m}}\exp\bigl{(}\varDelta_{1}(m,n,\lambda)+O(\lambda^{4}mn)\bigr{)}$		(1.1)
		$\displaystyle=\prod_{i=1}^{k}\frac{(\lambda_{i}mn)!}{(\lambda_{i}m)!^{n}\,(\lambda_{i}n)!^{m}}\exp\bigl{(}\varDelta_{2}(m,n,\lambda)+O(\lambda^{3}mn)\bigr{)},$		(1.2)

where

	$\displaystyle\varDelta_{1}(m,n,\lambda)$	$\displaystyle=-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}k+\lower 0.6458pt\hbox{\large$\textstyle\frac{k}{4m}$}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\lambda+\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{4}$}\lambda(2+\lambda)(m+n)-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{6}$}\lambda^{2}(3+\lambda)mn-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{12}$}\lambda\bigl{(}\lower 0.6458pt\hbox{\large$\textstyle\frac{m}{n}$}+\lower 0.6458pt\hbox{\large$\textstyle\frac{n}{m}$}\bigr{)}$
	$\displaystyle\varDelta_{2}(m,n,\lambda)$	$\displaystyle=-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}k+\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\lambda(m+n)-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\lambda^{2}mn.$

Proof.

If $N\to\infty$ and $\lambda=O(N^{-1/4})$ , with $\lambda N$ integer,

$\displaystyle(N)_{\lambda N}$	$\displaystyle=N^{\lambda N}\exp\biggl{(}\,\sum_{i=0}^{\lambda N-1}\log\Bigl{(}1-\lower 0.6458pt\hbox{\large$\textstyle\frac{i}{N}$}\Bigr{)}\biggr{)}$
	$\displaystyle=N^{\lambda N}\exp\Bigl{(}-\sum_{r=1}^{\infty}\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{r}$}\sum_{i=0}^{\lambda N-1}\bigl{(}i/N\bigr{)}^{r}\Bigr{)}$
	$\displaystyle=N^{\lambda N}\exp\Bigl{(}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{6}$}\lambda^{2}(3+\lambda)N+\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{4}$}\lambda(2+\lambda)-\lower 0.6458pt\hbox{\large$\textstyle\frac{\lambda}{12N}$}+O(\lambda^{4}N)\Bigr{)}.$	(1.3)

Note that

\binom{N}{\lambda_{0},\ldots,\lambda_{k}}=\frac{(N)_{\lambda N}}{\prod_{i=1}^{k}(\lambda_{i}N)!}.

Since $\lambda\geq\lower 0.6458pt\hbox{\large$\textstyle\frac{k}{m}$}$ , $k/m^{2}=O(\lambda^{4}mn)$ , so we also have

(1-1/m)^{k(m-1)/2}=\exp\Bigl{(}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}k+\lower 0.6458pt\hbox{\large$\textstyle\frac{k}{4m}$}+O(\lambda^{4}mn)\Bigr{)}.

Applying this, together with (1.3) for $N=m,n,mn$ , gives (1.1). Removing the terms that are $O(\lambda^{3}mn)$ gives (1.2). ∎

2 A first case of a single dense factor

In [9], the second author proved a generalized version of the following lemma.

Lemma 2.1.

Assume $m\leq n$ , $\lambda_{h}>0$ , $\lambda_{d}\geq 0$ and $\lambda_{h}(\lambda_{d}^{2}+\lambda_{h}^{2})m^{-1}n^{3}=o(1)$ . Let $D$ be any $(m,n,\lambda_{d})$ -semiregular graph. Then the number of $(m,n,\lambda_{h})$ -semiregular graphs edge-disjoint from $D$ is

\frac{(\lambda_{h}mn)!}{(\lambda_{h}m)!^{n}(\lambda_{h}n)!^{m}}\exp\bigl{(}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}(\lambda_{h}m-1)(\lambda_{h}n-1)-\lambda_{h}\lambda_{d}mn+O(\lambda_{h}(\lambda_{d}+\lambda_{h})^{2}m^{-1}n^{3})\bigr{)}.

Now we can prove Theorem 1.3(b).

Theorem 2.2.

Assume $m\leq n$ , $k\geq 1$ , and that $\lambda_{1},\ldots,\lambda_{k}$ are positive numbers with $\sum_{i=1}^{k}\lambda_{i}=o(m^{1/3}/n)$ . Define $\lambda=\sum_{i=1}^{k}\lambda_{i}$ and $\lambda_{0}=1-\lambda$ . Then

R(m,n;\lambda_{0},\ldots,\lambda_{k})=R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})\bigl{(}1+O(\lambda^{3}m^{-1}n^{3})\bigr{)}.

Proof.

The case $k=1$ corresponds to $\lambda_{d}=0$ in Lemma 2.1, so assume $k\geq 2$ . For notational convenience, write the argument of the exponential in Lemma 2.1 as $A(\lambda_{d},\lambda_{h})+O(\delta(\lambda_{d},\lambda_{h}))$ . We can partition $K_{m,n}$ into spanning semiregular subgraphs of density $\lambda_{0},\ldots,\lambda_{k}$ by first choosing an $(m,n,\lambda_{1})$ -semiregular graph $D_{1}$ , then choosing an $(m,n,\lambda_{2})$ -semiregular graph $D_{2}$ disjoint from $D_{1}$ , then an $(m,n,\lambda_{3})$ -semiregular graph $D_{3}$ disjoint from $D_{1}\cup D_{2}$ , and so on until we have chosen disjoint $D_{1},\ldots,D_{k}$ . Since the density of $D_{1}\cup\cdots\cup D_{j}=\lambda_{1}+\cdots+\lambda_{j}$ for each $j$ , we have

	$\displaystyle R(m,n;$	$\displaystyle\lambda_{0},\ldots,\lambda_{k})=\exp\bigl{(}\hat{A}+O(\hat{\delta})\bigr{)}\prod_{i=1}^{k}\frac{(\lambda_{i}mn)!}{(\lambda_{i}m)!^{n}\,(\lambda_{i}n)!^{m}},\qquad\text{where}$
	$\displaystyle\hat{A}$	$\displaystyle=A(0,\lambda_{1})+A(\lambda_{1},\lambda_{2})+A(\lambda_{1}+\lambda_{2},\lambda_{3})+\cdots+A\Bigl{(}{\textstyle\sum_{i=1}^{k-1}}\lambda_{i},\lambda_{k}\Bigr{)},$
	$\displaystyle\hat{\delta}$	$\displaystyle=\delta(0,\lambda_{1})+\delta(\lambda_{1},\lambda_{2})+\delta(\lambda_{1}+\lambda_{2},\lambda_{3})+\cdots+\delta\Bigl{(}{\textstyle\sum_{i=1}^{k-1}}\lambda_{i},\lambda_{k}\Bigr{)}.$

By routine induction, we find that

\hat{A}=-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}k+\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\lambda(m+n)-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\lambda^{2}mn

and $\hat{\delta}=O(\lambda^{3}m^{-1}n^{3})$ .

Since $m\leq n$ we have $mn=O(m^{-1}n^{3})$ , which completes the proof in conjunction with (1.2), ∎

3 A second case of one dense factor

The enumeration of sparse semiregular bipartite graphs was extended to higher degrees by McKay and Wang [11] and generalised by Greenhill, McKay and Wang [5]. However, unlike Lemma 2.1, there was no allowance in [5, 11] for a set of forbidden edges. In order to use the more accurate enumeration for our purposes, we consider the problem of forbidden edges in a more general form that may be of independent interest. Instead of considering a random semiregular graph, we consider an arbitrary semiregular graph that is labelled at random.

When we write of a semiregular bipartite graph on $(V_{1},V_{2})$ being randomly (re)labelled, we mean that $V_{1}$ and $V_{2}$ are independently permuted ( $m!\,n!$ possibilities altogether of equal probability). In this section we consider two semiregular bipartite graphs on $(V_{1},V_{2})$ : an $(m,n,\lambda_{d})$ -semiregular graph $D$ and an $(m,n,\lambda_{h})$ -semiregular graph $H$ . If $H$ is randomly labelled, what is the probability that it is edge-disjoint from $D$ ?

Define $M=\lceil\lambda_{d}\lambda_{h}mn\log n\rceil$ . We will work under the following assumptions.

n\to\infty,\quad m\leq n,\quad\lambda_{d},\lambda_{h}>0,\quad\lambda_{d}^{2}\lambda_{h}^{2}mn^{2}=o(1).

(3.1)

Lemma 3.1.

Under assumptions (3.1), we have $m\to\infty$ , $n=o(m^{3/2})$ , and $m^{-1}\leq\lambda_{d},\lambda_{h}=o(m^{1/2}n^{-1})$ . In addition, $\lambda_{d}\lambda_{h}=o(m^{-1/2}n^{-1})$ and $\log n\leq M=o(m^{1/2}\log n)$ .

Proof.

Since $D,H$ are not empty, $\lambda_{d},\lambda_{h}\geq\frac{1}{m}$ , corresponding to degree 1 in $V_{2}$ . The rest is elementary. ∎

Lemma 3.2.

Let $D$ be an $(m,n,\lambda_{d})$ -semiregular bipartite graph and $H$ be an $(m,n,\lambda_{h})$ -semiregular bipartite graph satisfying Assumptions (3.1). Then, with probability $1-O(\lambda_{d}^{2}\lambda_{h}^{2}mn^{2})$ , a random labeling of $H$ does not have any path of length 2 in common with $D$ and the number of edges in common with $D$ is less than $M$ .

Proof.

Graphs $D$ and $H$ have $O(mn^{2}\lambda_{d}^{2})$ and $O(mn^{2}\lambda_{h}^{2})$ paths of length 2 with the central vertex in $V_{1}$ , respectively. The probability that such a path in $H$ matches a given path in $D$ when randomly labelled is $O(m^{-1}n^{-2})$ . So the expected number of such coincidences is $O(\lambda_{d}^{2}\lambda_{h}^{2}mn^{2})$ . Similarly, the expected number of coincidences between paths of length 2 with central vertex in $V_{2}$ is $O(\lambda_{d}^{2}\lambda_{h}^{2}m^{2}n)$ , which is $O(\lambda_{d}^{2}\lambda_{h}^{2}mn^{2})$ because $m\leq n$ by assumption. Thus, with probability $1-O(\lambda_{d}^{2}\lambda_{h}^{2}m^{2}n)$ , a random labelling of $H$ has no paths of length 2 in common with $D$ .

Now consider a set $S$ of $M$ edges of $H$ . In light of the preceding, we can assume they are independent edges. There are at most $\binom{\lambda_{h}mn}{M}$ choices of $S$ , and at most $\binom{\lambda_{d}mn}{M}$ choices of a set of $M$ edges of $D$ that $S$ might map onto. The probability that $S$ maps onto a particular set of $M$ independent edges of $D$ is

\frac{M!\,(m-M)!\,(n-M)!}{m!\,n!}\leq\frac{M!}{(m-M)^{M}(n-M)^{M}}.

Since $M=o(m)$ and $M=o(n)$ , $mn\leq 2(m-M)(n-M)$ for sufficiently large $n$ . Using $M!\geq(M/e)^{M}$ , we find that the expected number of sets of $M$ independent edges of $H$ that map onto edges of $D$ is at most

\biggl{(}\frac{\lambda_{h}\lambda_{d}\,m^{2}n^{2}e}{M(m-M)(n-M)}\biggr{)}^{\!M}\leq\biggl{(}\frac{2e}{\log n}\biggr{)}^{\!\log n}=O(n^{-t})\quad\text{for any $t>0$}.

By Lemma 3.1, $\lambda_{d}^{2}\lambda_{h}^{2}mn^{2}\geq n^{-1}$ , so the probability that $D$ and $H$ have more than $M$ edges in common is $O(\lambda_{d}^{2}\lambda_{h}^{2}mn^{2})$ . This completes the proof. ∎

Let $\mathcal{L}(t)$ be the set of all labelings of the vertices of $H$ with no common paths of length 2 with $D$ and exactly $t$ edges in common with $D$ . Define $L(t)=|\mathcal{L}(t)|$ , so in particular the number of labelings of the vertices of $H$ with no common edges with $D$ is $L(0)$ . Let

T=\sum_{t=0}^{M-1}L(t).

In the next step we will estimate the value of $T/L(0)$ by the switching method.

A forward switching is a permutation $(a\,e)(b\,f)$ of the vertices of $H$ such that

•

$a,e\in V_{1}$ are distinct, and $b,f\in V_{2}$ are distinct.
•

$ab$ is a common edge of $D$ and $H$ ,
•

$ef$ is a non-edge of $D$ , and
•

after the permutation, the edges common to $D$ and $H$ are the same except that $ab$ is no longer a common edge.

A reverse switching is a permutation $(a\,e)(b\,f)$ of the vertices of $H$ such that

•

$a,e\in V_{1}$ are distinct, and $b,f\in V_{2}$ are distinct.
•

$ab$ is an edge of $D$ that is not an edge of $H$ ,
•

$ef$ is an edge of $H$ that is not an edge of $D$ , and
•

after the permutation, the edges common to $D$ and $H$ are the same except that $ab$ becomes a common edge of $D$ and $H$ .

Lemma 3.3.

Assume Conditions (3.1). Then, uniformly for $1\leq t\leq M$ ,

\frac{L(t)}{L(t-1)}=\frac{(\lambda_{d}\,mn-t+1)(\lambda_{h}\,mn-t+1)}{tmn}\biggl{(}1+O\Bigl{(}\frac{t}{m}+\frac{1}{m^{1/2}}\Bigr{)}\biggr{)}.

Proof.

By using a forward switching, we will convert a labeling $R\in\mathcal{L}(t)$ to a labeling $R^{\prime}\in\mathcal{L}(t-1)$ . Without loss of generality, we suppose that $R$ is the identity, since our bounds will be independent of the structure of $H$ other than its density.

There are $t$ choices for edge $ab$ . We will bound the choices of $e,f$ for a fixed choice of $ab$ . Graph $D$ has $(1-\lambda_{d})mn$ non-edges $ef$ , including at most $m+n=O(n)$ for which $e=a$ or $f=b$ . In addition, we must ensure that no common edges are created (implying that there remain no common paths of length 2), and none other than $ab$ are destroyed.

Since $D$ and $H$ have no paths of length 2 in common, there are no other common edges of $H$ and $D$ incident to $a$ or $b$ . Therefore the only way to destroy a common edge other than $ab$ is if $e$ or $f$ are incident to a common edge. This eliminates at most $t(n+m)=O(tn)$ pairs $e,f$ .

Creation of a new common edge can only occur if there is a path of length 2 from $a$ to $e$ , or from $b$ to $f$ , consisting of one edge from $H$ and one from $D$ . This eliminates at most $4\lambda_{d}\lambda_{h}mn$ choices of $ef$ .

Using Lemma 3.1 we find that the number of forward switchings is

	$\displaystyle W_{F}$	$\displaystyle=t\bigl{(}(1-\lambda_{d})mn-O(n+tn+\lambda_{d}\lambda_{h}mn)\bigr{)}$
		$\displaystyle=t\,mn\biggl{(}1+O\Bigl{(}\frac{t}{m}+\frac{m^{1/2}}{n}\Bigr{)}\biggr{)}.$

A reverse switching converts a labeling $R^{\prime}\in\mathcal{L}(t-1)$ to a labeling $R$ in $\mathcal{L}(t)$ . Again, without loss of generality, we suppose that $R^{\prime}$ is the identity. There are $\lambda_{d}\,mn-t+1$ choices for an edge $ab$ in $D$ and $\lambda_{h}mn-t+1$ choices for an edge $ef$ in $H$ , in each case avoiding the $t-1$ common edges. From these we must subtract any choices that create or destroy a common edge except the new common edge $ab$ we intend to create, as well as those with $a=e$ or $b=f$ .

There are at most $\lambda_{d}\lambda_{h}mn^{2}$ choices of $a,b,e,f$ such that $a=e$ and at most that number (since $m\leq n$ ) such that $b=f$ .

To destroy a common edge, at least one of $a,b,e,f$ must be the endpoint of a common edge. The number of such choices is bounded by $4(t-1)\lambda_{d}\lambda_{h}mn^{2}$ .

To create a new common edge other than $ab$ , there must be a path of length 2 from $a$ to $e$ , or from $b$ to $f$ , consisting of one edge from $H$ and one from $D$ . This eliminates at most $\lambda_{d}^{2}\lambda_{h}^{2}m^{2}n^{3}$ cases.

Using Lemma 3.1 we find that the number of reverse switchings is

	$\displaystyle W_{R}$	$\displaystyle=(\lambda_{d}mn-t+1)(\lambda_{h}mn-t+1)+O\bigl{(}t\lambda_{d}\lambda_{h}mn^{2}+\lambda_{d}^{2}\lambda_{h}^{2}m^{2}n^{3}\bigr{)}$
		$\displaystyle=(\lambda_{d}mn-t+1)(\lambda_{h}mn-t+1)\biggl{(}1+O\Bigl{(}\frac{t}{m}+\frac{1}{m^{1/2}}\Bigr{)}\biggr{)}.$

The lemma now follows from the ratio $W_{R}/W_{F}$ , using $m\leq n$ . ∎

We will need the following summation lemma from [5, Cor. 4.5].

Lemma 3.4.

Let $Z\geq 2$ be an integer and, for $1\leq i\leq Z$ , let real numbers $A(i)$ , $B(i)$ be given such that $A(i)\geq 0$ and $1-(i-1)B(i)\geq 0$ . Define $A_{1}=\min_{i=1}^{Z}A(i)$ , $A_{2}=\max_{i=1}^{Z}A(i),C_{1}=\min_{i=1}^{Z}A(i)B(i)$ and $C_{2}=\max_{i=1}^{Z}A(i)B(i)$ . Suppose that there exists $\hat{c}$ with $0<\hat{c}<\frac{1}{3}$ such that $\max\{A/Z,|C|\}\leq\hat{c}$ for all $A\in[A_{1},A_{2}]$ , $C\in[C_{1},C_{2}]$ . Define $n_{0},\ldots,n_{Z}$ by $n_{0}=1$ and

n_{i}/n_{i-1}=\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{i}$}A(i)(1-(i-1)B(i))

for $1\leq i\leq Z$ , with the following interpretation: if $A(i)=0$ or $1-(i-1)B(i)=0$ , then $n_{j}=0$ for $i\leq j\leq Z$ . Then

\Sigma_{1}\leq\sum_{i=0}^{Z}n_{i}\leq\Sigma_{2},

where

\Sigma_{1}=\exp\bigl{(}A_{1}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}A_{1}C_{2})-(2e\hat{c}\bigr{)}^{Z}

and

\Sigma_{2}=\exp\bigl{(}A_{2}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}A_{2}C_{1}+\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}A_{2}C_{1}^{2}\bigr{)}+(2e\hat{c})^{Z}.\hbox to0.0pt{\qquad\qquad\qed\hss}

Lemma 3.5.

Under Assumptions (3.1) we have

\frac{T}{L(0)}=\exp\bigl{(}\lambda_{d}\lambda_{h}mn+O(\lambda_{d}\lambda_{h}m^{1/2}n)\bigr{)}.

Proof.

Lemma 3.1 and the definition of $M$ allow us to write Lemma 3.3 as

\frac{L(t)}{L(t-1)}=\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{t}$}A(t)\bigl{(}1-(t-1)B(t)\bigr{)},

where $A(t)=\lambda_{d}\lambda_{h}mn(1+O(m^{-1/2}))$ and $B(t)=O(m^{-1})$ . In each case, the $O(\,)$ expression is a function of $t$ but uniform over $1\leq t\leq M$ .

Clearly $A(t)>0$ , and using Lemma 3.1, we can check that $1-(t-1)B(t)>0$ for $1\leq t\leq M$ . Define $A_{1}$ , $A_{2}$ , $C_{1}$ and $C_{2}$ as in Lemma 3.4. This gives

	$\displaystyle A_{1},A_{2}$	$\displaystyle=\lambda_{d}\lambda_{h}mn+O(\lambda_{d}\lambda_{h}m^{1/2}n),$
	$\displaystyle C_{1},C_{2}$	$\displaystyle=O(\lambda_{d}\lambda_{h}n)=o(m^{-1/2}).$

The condition $\max\{A/M,|C|\}\leq\hat{c}$ of Lemma 3.4 is satisfied with $\hat{c}$ any sufficiently small constant. Using Lemma 3.1, we also have $A_{1}C_{2},A_{2}C_{1}=O(\lambda_{d}^{2}\lambda_{h}^{2}mn^{2})$ , $A_{2}C_{1}^{2}=O(\lambda_{d}^{2}\lambda_{h}^{2}m^{1/2}n^{2})$ and $(2e\hat{c})^{M}=O(n^{-1})$ if $\hat{c}$ is small enough. Since $\lambda_{d}^{2}\lambda_{h}^{2}mn^{2}=o(1)$ by assumption, $\lambda_{d}^{2}\lambda_{h}^{2}mn^{2}=o(\lambda_{d}\lambda_{h}m^{1/2}n)$ . The lemma now follows from Lemma 3.4. ∎

Lemma 3.6.

Let $D$ be an $(m,n,\lambda_{d})$ -semiregular bipartite graph and $H$ be an $(m,n,\lambda_{h})$ -semiregular bipartite graph such that Assumptions (3.1) hold. Then the probability that a random labelling of $H$ is edge-disjoint from $D$ is

\exp\bigl{(}-\lambda_{d}\lambda_{h}mn+O(\lambda_{d}\lambda_{h}m^{1/2}n)\bigr{)}.

Proof.

The probability that there are no common paths of length two and less than $M$ edges in common is $1-O(\lambda_{d}^{2}\lambda_{h}^{2}mn^{2})$ by Lemma 3.2. Subject to those conditions, the probability of no common edge is

\exp\bigl{(}-\lambda_{d}\lambda_{h}mn+O(\lambda_{d}\lambda_{h}m^{1/2}n)\bigr{)}

by Lemma 3.5. Multiplying these probabilities together gives the theorem, since
$\lambda_{d}\lambda_{h}m^{1/2}n\to 0$ by (3.1). ∎

Theorem 3.7.

For $i=1,\ldots,k$ , let $D_{i}$ be an $(m,n,\lambda_{i})$ -semiregular bipartite graph. Assume $m\leq n$ and $m^{1/2}n\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}=o(1)$ . Then the probability that $D_{1},D_{2},\ldots,D_{k}$ are edge-disjoint after labelling at random is

\exp\biggl{(}-mn\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}+O\Bigl{(}m^{1/2}n\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}\Bigr{)}\biggr{)}.

Proof.

This is an immediate consequence of Lemma 3.6 applied iteratively. ∎

Now we are ready to prove Theorem 1.3(c). First we state the enumeration theorem from [11], extended with the help of Lemma 3.6. Note that, despite this theorem and Lemma 2.1 having considerable overlap, neither of them implies the other.

Theorem 3.8.

Assume $m\leq n$ , $\lambda_{h}>0$ , $\lambda_{d}\geq 0$ and $\lambda_{h}\lambda_{d}\,m^{1/2}n=o(1)$ . Let $D$ be any $(m,n,\lambda_{d})$ -semiregular graph. Then the number of $(m,n,\lambda_{h})$ -semiregular graphs edge-disjoint from $D$ is

	$\displaystyle\frac{(\lambda_{h}mn)!}{(\lambda_{h}m)!^{n}(\lambda_{h}n)!^{m}}$	$\displaystyle\exp\bigl{(}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}(\lambda_{h}m-1)(\lambda_{h}n-1)-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{6}$}\lambda_{h}^{3}mn$
		$\displaystyle{\qquad\quad}-\lambda_{h}\lambda_{d}\,mn+O(\lambda_{h}\lambda_{d}\,m^{1/2}n)\bigr{)}.$

Theorem 3.9.

Let $\lambda_{0},\lambda_{1},\ldots,\lambda_{k}>0$ be such that $k\geq 2$ and $\sum_{i=0}^{k}\lambda_{i}=1$ . Assume that $m\leq n$ and $m^{1/2}n\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}=o(1)$ . Then

R(m,n;\lambda_{0},\ldots,\lambda_{k})=R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})\biggl{(}1+O\Bigl{(}m^{1/2}n\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}\Bigr{)}\biggr{)},

where $R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})$ is defined in Conjecture 1.2.

Proof.

The proof follows the same line as Theorem 2.2. Define $\lambda=\sum_{i=1}^{k}\lambda_{i}$ and $\varLambda=\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}$ . Write the argument of the exponential in Theorem 3.8 as $A^{\prime}(\lambda_{d},\lambda_{h})+O(\delta^{\prime}(\lambda_{d},\lambda_{h}))$ . Then, as before,

	$\displaystyle R(m,n;$	$\displaystyle\lambda_{0},\ldots,\lambda_{k})=\exp\bigl{(}\check{A}+O(\check{\delta})\bigr{)}\prod_{i=1}^{k}\frac{(\lambda_{i}mn)!}{(\lambda_{i}m)!^{n}\,(\lambda_{i}n)!^{m}},\qquad\text{where}$
	$\displaystyle\check{A}$	$\displaystyle=A^{\prime}(0,\lambda_{1})+A^{\prime}(\lambda_{1},\lambda_{2})+A^{\prime}(\lambda_{1}+\lambda_{2},\lambda_{3})+\cdots+A^{\prime}\Bigl{(}{\textstyle\sum_{i=1}^{k-1}}\lambda_{i},\lambda_{k}\Bigr{)},$
	$\displaystyle\check{\delta}$	$\displaystyle=\delta^{\prime}(0,\lambda_{1})+\delta^{\prime}(\lambda_{1},\lambda_{2})+\delta^{\prime}(\lambda_{1}+\lambda_{2},\lambda_{3})+\cdots+\delta^{\prime}\Bigl{(}{\textstyle\sum_{i=1}^{k-1}}\lambda_{i},\lambda_{k}\Bigr{)}.$

By routine induction, we find that

\check{A}=-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}k+\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\lambda(m+n)-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{6}$}mn\sum_{i=1}^{k}\lambda_{i}^{3}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\lambda^{2}mn\quad\text{and}\quad\check{\delta}=m^{1/2}n\varLambda.

Since $\lambda_{i}\geq\frac{1}{m}$ for $1\leq i\leq k$ , we have $\varLambda=\frac{1}{2}\sum_{i=1}^{k}\lambda_{i}\sum_{j\neq i}\lambda_{j}\geq\frac{k-1}{2m}\lambda\geq\frac{\lambda}{2m}$ . Therefore, the condition $m^{1/2}n\varLambda=o(1)$ implies that $m^{-1/2}n\lambda=o(1)$ and $\check{\delta}=\Omega(m^{-1/2}n\lambda)$ . Since $\lambda^{4}mn=(m^{-1/2}n\lambda)^{4}m^{3}n^{-3}$ and $m\leq n$ , we also have $\lambda^{4}mn=O(\check{\delta})=o(1)$ . This allows us to apply (1.1) to estimate $R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})$ . We also have $km^{-1}\leq\lambda=O(\check{\delta})m^{1/2}n^{-1}=O(\check{\delta})$ , $\lambda^{2}m\leq\lambda^{2}n=O(\check{\delta}^{2})mn^{-1}=O(\check{\delta})$ , and $\lambda mn^{-1}\leq\lambda nm^{-1}=O(\check{\delta}^{2})m^{-1/2}=O(\check{\delta})$ , which eliminates many terms of (1.1). What remains gives

R(m,n;\lambda_{0},\ldots,\lambda_{k})=R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})\exp\biggl{(}\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{6}$}\lambda^{3}mn-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{6}$}mn\sum_{i=1}^{k}\lambda_{i}^{3}+O(\check{\delta})\biggr{)}.

Finally, we have

mn\biggl{(}\lambda^{3}-\sum_{i=1}^{k}\lambda_{i}^{3}\biggr{)}=O(mn)\sum_{\ell=1}^{k}\sum_{i<j}\lambda_{i}\lambda_{j}\lambda_{\ell}=O(\lambda mn\varLambda)=O(\check{\delta}^{2})m^{1/2}n^{-1/2}=O(\check{\delta}),

which completes the proof. ∎

Refer to caption — Figure 1: Latin rectangles. $F(n,k)/R^{\prime}(n,n;1-\frac{k}{n},\frac{1}{n},\ldots,\frac{1}{n})$ for $n=10$ (diamonds) and $n=11$ (circles). The horizontal scale is $x=k/(n-1)$ and the line is $1+x/12$ .

4 The case of Latin rectangles

The case $m=n,\lambda_{1},\ldots,\lambda_{k}=\frac{1}{n}$ corresponds to choosing an ordered sequence of $k$ perfect matchings in $K_{n,n}$ , which is a $k\times n$ Latin rectangle.

Let $F(n,k)$ be the number $k\times n$ Latin rectangles. Note that $F(n,n-1)=F(n,n)$ ; we will use only $F(n,n-1)$ . In [3], Godsil and McKay found the asymptotic value of $F(n,k)$ for $k=o(n^{6/7})$ and conjectured that the same formula holds for any $k=O(n^{1-\delta})$ with $\delta>0$ , namely that

F(n,k)\sim(n!)^{k}\biggl{(}\frac{n!}{(n-k)!\,n^{k}}\biggr{)}^{\!n}\biggl{(}1-\frac{k}{n}\biggr{)}^{\!-n/2}e^{-k/2}.

The reader can check that this expression is equal to $R^{\prime}(n,n;1-\frac{k}{n},\frac{1}{n},\ldots,\frac{1}{n})$ asymptotically when $k=o(n)$ , where here and in the following $\frac{1}{n}$ occurs $k$ times as an argument of $R^{\prime}$ .

To illustrate what happens when $k$ is even larger, Figure 1 shows the ratio $F(n,k)/\allowbreak R^{\prime}(n,n;1-\frac{k}{n},\frac{1}{n},\ldots,\frac{1}{n})$ for $n=10,11$ , as a function of $k/(n-1)$ [12]. Experiment suggests that $F(n,x(n-1))/R^{\prime}(n,n;1-\frac{k}{n},\frac{1}{n},\ldots,\frac{1}{n})$ converges to a continuous function $f(x)$ as $n\to\infty$ with $x$ fixed. Conjecture 1.2 in this case corresponds to $f(0)=1$ .

5 Two factors of high degree

In this section, we consider the case where $\lambda_{0}$ and $\lambda_{1}$ are approximately constant. We will use a constant $\varepsilon>0$ that must be sufficiently small. Suppose the following conditions hold.

	$\displaystyle(1-2\lambda_{1})^{2}\biggl{(}1+\frac{5m}{6n}+\frac{5n}{6m}\biggr{)}$	$\displaystyle\leq(4-\varepsilon)\lambda_{1}(1-\lambda_{1})\log n$		(5.1)
	$\displaystyle m\leq n$	$\displaystyle=o\bigl{(}\lambda_{1}(1-\lambda_{1})m^{1+\varepsilon}\bigr{)}.$		(5.1)

Let $D$ be an $(m,n,\hat{\lambda})$ -semiregular graph where $0<\hat{\lambda}\leq n^{-1+\varepsilon}$ . Greenhill and McKay [4] proved that the number of $(m,n,\lambda_{1})$ -semiregular graphs is given by Theorem 1.1, and the probability that a uniformly random $(m,n,\lambda_{1})$ -semiregular graph is edge-disjoint from $D$ is asymptotically

P(m,n,\lambda_{1},\hat{\lambda})=(1-\lambda_{1})^{\hat{\lambda}mn}\exp\biggl{(}-\frac{\lambda_{1}\hat{\lambda}(\hat{\lambda}mn-m-n)}{2(1-\lambda_{1})}\biggr{)}.

(5.2)

Theorem 5.1.

Suppose conditions (5.1) hold and suppose $\hat{\lambda}=\lambda_{2}+\cdots+\lambda_{k}=O(n^{-1+\varepsilon})$ with sufficiently small constant $\varepsilon>0$ . Then, as $n\to\infty$ ,

R(m,n;\lambda_{0},\ldots,\lambda_{k})\sim R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k}).

Proof.

Our approach is to first construct an arbitrary graph $D$ of density $\hat{\lambda}$ partitioned into factors of density $\lambda_{2},\ldots,\lambda_{k}$ . Then Theorem 1.1 together with (5.2) tells us the number of graphs $G$ of density $\lambda_{1}$ disjoint from $D$ . The complement of $G\cup D$ is then the factor of density $\lambda_{0}$ .

The second part of Condition (5.1) implies that $n^{-1+\varepsilon}\leq m^{1/3}/n$ for sufficiently small $\varepsilon>0$ . Therefore we can apply Theorem 2.2 to deduce that the possibilities for $D$ are

R(m,n;\lambda_{0}+\lambda_{1},\lambda_{2},\ldots,\lambda_{k})\sim R^{\prime}(m,n;\lambda_{0}+\lambda_{1},\lambda_{2},\ldots,\lambda_{k}).

In addition, $R(m,n;1-\lambda_{1},\lambda_{1})\sim R^{\prime}(m,n;1-\lambda_{1},\lambda_{1})$ by Theorem 1.1 part 2. Therefore,

R(m,n;\lambda_{0},\ldots,\lambda_{k})\sim P(m,n,\lambda_{1},\hat{\lambda})R^{\prime}(m,n;1-\lambda_{1},\lambda_{1})R^{\prime}(m,n;\lambda_{0}+\lambda_{1},\lambda_{2},\ldots,\lambda_{k}).

Then we have

\frac{R(m,n;\lambda_{0},\ldots,\lambda_{k})}{R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})}\sim P(m,n,\lambda_{1},\hat{\lambda})\frac{\Bigl{(}\frac{m!\,((1-\lambda_{1}-\hat{\lambda})m)!}{((1-\lambda_{1})m)!\,((1-\hat{\lambda})m)!}\Bigr{)}^{\!n}\Bigl{(}\frac{n!\,((1-\lambda_{1}-\hat{\lambda})n)!}{((1-\lambda_{1})n)!\,((1-\hat{\lambda})n)!}\Bigr{)}^{\!m}}{\Bigl{(}\frac{(mn)!\,((1-\lambda_{1}-\hat{\lambda})mn)}{((1-\lambda_{1})mn)!\,((1-\hat{\lambda})mn)!}\Bigr{)}}.

Define $g(N)$ by $N!=\sqrt{2\pi}\,N^{N+1/2}e^{-N+g(N)}$ and

\bar{g}(N)=g(N)+g((1{-}\hat{\lambda}{-}\lambda_{1})N)-g((1{-}\hat{\lambda})N)-g((1{-}\lambda_{1})N.

Then, using (5.2),

	$\displaystyle\frac{R(m,n;\lambda_{0},\ldots,\lambda_{k})}{R^{\prime}(m,n;\lambda_{0},\ldots,\lambda_{k})}$
	$\displaystyle{\qquad}\sim\bigl{(}1-\hat{\lambda}\bigr{)}^{-(1-\hat{\lambda})mn-(m+n-1)/2}\biggl{(}1-\frac{\hat{\lambda}}{1-\lambda_{1}}\biggr{)}^{\!(1-\hat{\lambda}-\lambda_{1})mn+(m+n-1)/2}$
	$\displaystyle{\qquad\qquad\qquad}\times\exp\biggl{(}-\frac{\lambda_{1}\hat{\lambda}(\hat{\lambda}mn-m-n)}{2(1-\lambda_{1})}+n\bar{g}(m)+m\bar{g}(n)-\bar{g}(mn)\biggr{)}.$

Now we can apply the estimates $1-x=e^{-x-x^{2}/2+O(x^{3})}$ and $g(N)=\frac{1}{12N}+O(N^{-3})$ to show that the above quantity is $e^{o(1)}$ . This completes the proof. ∎

6 The highly oblong case

Suppose $2\leq m=O(1)$ and $1\leq k\leq m-1$ . In that case we can prove Conjecture 1.2 by application of the Central Limit Theorem, without requiring the condition $k=o(m)$ .

We will consider the partition of $K_{m,n}$ into $k+1$ semiregular graphs as an edge-colouring with colours $0,1,\ldots,k$ , where colour $c$ gives a semiregular subgraph of density $\lambda_{c}$ for $0\leq c\leq k$ . Label $V_{1}$ as $u_{1},\ldots,u_{m}$ and consider one vertex $v\in V_{2}$ . For $0\leq c\leq k$ , $v$ must be adjacent to $\lambda_{c}m$ vertices of $V_{1}$ by edges of colour $c$ ; let us make the choice uniformly at random from the

\binom{m}{\lambda_{0}m,\ldots,\lambda_{k}m}

possibilities. Define the random variable $X_{i,c}$ to be the indicator of the event “ $v$ is joined to vertex $u_{i}$ by colour $c$ ”. Let $\boldsymbol{X}$ be the $(m-1)k$ -dimensional random vector $(X_{i,c})_{1\leq i\leq m-1,1\leq c\leq k}$ . Note that we are omitting $i=m$ and $c=0$ since those indicators can be determined from the others (this avoids degeneracy in the following). Let $\boldsymbol{X}^{(n)}$ denote the sum of $n$ independent copies of $\boldsymbol{X}$ , corresponding to a copy of $\boldsymbol{X}$ for each vertex in $V_{2}$ . For each vertex in $V_{2}$ to have the correct number $\lambda_{c}m$ of incident edges of each colour $c$ , $\boldsymbol{X}^{(n)}$ must equal its mean. That is,

R(m,n;\lambda_{0},\ldots,\lambda_{k})=\binom{m}{\lambda_{0}m,\ldots,\lambda_{k}m}^{\!n}\,\mathrm{Prob}(\boldsymbol{X}^{(n)}=\mathbb{E}\boldsymbol{X}^{(n)}).

We have $\mathbb{E}X_{i,c}=\lambda_{c}$ for every $i,c$ and the following expectations of products.

\mathbb{E}(X_{i,c}\,X_{i^{\prime},c^{\prime}})=\begin{cases}\lambda_{c},&\text{if $i=i^{\prime},c=c^{\prime}$};\\ 0,&\text{if $i=i^{\prime},c\neq c^{\prime}$};\\ \frac{\lambda_{c}(\lambda_{c}m-1)}{m-1},&\text{if $i\neq i^{\prime},c=c^{\prime}$};\\ \frac{m}{m-1}\lambda_{c}\lambda_{c^{\prime}},&\text{if $i\neq i^{\prime},c\neq c^{\prime}$}.\end{cases}

Using $\mathrm{Cov}(X_{i,c},X_{i^{\prime},c^{\prime}})=\mathbb{E}(X_{i,c}\,X_{i^{\prime},c^{\prime}})-\mathbb{E}X_{i,c}\,\mathbb{E}X_{i^{\prime},c^{\prime}}$ this gives

\mathrm{Cov}(X_{i,c},X_{i^{\prime},c^{\prime}})=\begin{cases}\lambda_{c}(1-\lambda_{c}),&\text{if $i=i^{\prime},c=c^{\prime}$};\\ -\lambda_{c}\lambda_{c^{\prime}},&\text{if $i=i^{\prime},c\neq c^{\prime}$};\\ -\frac{\lambda_{c}(1-\lambda_{c})}{m-1},&\text{if $i\neq i^{\prime},c=c^{\prime}$};\\ \frac{\lambda_{c}\lambda_{c^{\prime}}}{m-1},&\text{if $i\neq i^{\prime},c\neq c^{\prime}$}.\end{cases}

Let $\varSigma$ be the covariance matrix of $\boldsymbol{X}$ , labelled in the order $(1,1),(1,2),\ldots,(m-1,k)$ .

By [2, Thm. 1], $\boldsymbol{X}^{(n)}$ satisfies a local Central Limit Theorem as $n\to\infty$ . In particular, since the covariance matrix of $\boldsymbol{X}^{(n)}$ is $n\varSigma$ ,

\mathrm{Prob}(\boldsymbol{X}^{(n)}=\mathbb{E}\boldsymbol{X}^{(n)})\sim\frac{1}{(2\pi)^{k(m-1)/2}n^{k(m-1)/2}\mathopen{|}\varSigma\mathclose{|}^{1/2}}.

To find the determinant $\mathopen{|}\varSigma\mathclose{|}$ , it helps to notice that $\varSigma$ is a tensor product $B\otimes C$ . Here $B$ is a $k\times k$ matrix with $B_{ii}=\lambda_{i}(1-\lambda_{i})$ for all $i$ and $B_{ij}=-\lambda_{i}\lambda_{j}$ for $i\neq j$ ; while $C$ is an $(m-1)\times(m-1)$ matrix with 1 on the diagonal and $-\frac{1}{m-1}$ off the diagonal. Both $B$ and $C$ are rank-1 modifications of diagonal matrices, and the matrix determinant lemma gives $\mathopen{|}B\mathclose{|}=\prod_{i=0}^{k}\lambda_{i}$ and $\mathopen{|}C\mathclose{|}=m^{m-2}/(m-1)^{m-1}$ . Therefore,

\mathopen{|}\varSigma\mathclose{|}=\mathopen{|}B\mathclose{|}^{m-1}\mathopen{|}C\mathclose{|}^{k}=m^{-k}(1-1/m)^{-k(m-1)}\biggl{(}\,\prod_{i=0}^{k}\lambda_{i}\biggr{)}^{\!m-1}.

To complete the proof of Theorem 1.3(e), apply $N!=\sqrt{2\pi}\,N^{N+1/2}e^{-N+O(1/N)}$ to find

\frac{\displaystyle\binom{n}{\lambda_{0}n,\ldots,\lambda_{k}n}^{\!m}}{\displaystyle\binom{mn}{\lambda_{0}mn,\ldots,\lambda_{k}mn}}\sim(2\pi n)^{-k(m-1)/2}m^{k/2}\biggl{(}\,\prod_{i=0}^{k}\lambda_{i}\biggr{)}^{\!-(m-1)/2}.

7 Concluding remarks

We have proposed an asymptotic formula for the number of ways to partition a complete bipartite graph into spanning semiregular regular subgraphs and proved it in several cases. The analytic method described in [7] will be sufficient to test the conjecture when there are several factors of high density. This will be the topic of a future paper. A similar investigation for regular graphs that are not necessarily bipartite appears in [6].

The authors declare that they have no conflict of interest.

References

[1] Canfield, E. R. and McKay, B. D., Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums, Electron. J. Combinatorics, 12 (2005) R29. https://doi.org/10.37236/1926
[2] Gamkrelidze, N. G., On a local limit theorem for integer random vectors, Theory Probab. Appl., 59 (2015) 494–499. https://doi.org/10.1137/S0040585X97T987247
[3] Godsil, C. D. and McKay, B. D., Asymptotic enumeration of Latin rectangles, J. Combinatorial Theory, Ser. B, 48 (1990) 19–44. https://doi.org/10.1016/0095-8956(90)90128-m
[4] Greenhill, C. and McKay, B. D., Random dense bipartite graphs and directed graphs with specified degrees, Random Structures Algorithms 35 (2009) 222–249. https://doi.org/10.1002/rsa.20273
[5] Greenhill, C., McKay, B. D. and Wang, X., Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums, J. Comb. Theory Ser. A 113 (2006) 291–324. https://doi.org/10.1016/j.jcta.2005.03.005
[6] M. Hasheminezhad and B. D. McKay, Factorisation of the complete graph into spanning regular factors, Advances Appl. Math., to appear.
[7] Isaev, M. and McKay, B. D., Complex martingales and asymptotic enumeration, Random Structures Algorithms 52 (2018) 617–661. https://doi.org/10.1002/rsa.20754
[8] Liebenau, A. and Wormald, N., Asymptotic enumeration of digraphs and bipartite graphs by degree sequence, Random Structures Algorithms, online July 2022. https://doi.org/10.1002/rsa.21105.
[9] McKay, B. D., Asymptotics for 0-1 matrices with prescribed line sums, in Enumeration and Design (D. M. Jackson and S. A. Vanstone, eds.), Academic Press (1984) 225–238.
[10] McKay, B. D., Subgraphs of dense random graphs with specified degrees, Combin. Prob. Comput., 20 (2011) 413–433. https://doi.org/10.1017/S0963548311000034
[11] McKay, B. D. and Wang, X., Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums, Linear Alg. Appl., 373 (2003) 273–288. https://doi.org/10.1016/S0024-3795(03)00506-8
[12] McKay, B. D. and Wanless, I., On the number of Latin squares, Ann. Combinatorics 9 (2005) 335–344. https://doi.org/10.1007/s00026-005-0261-7