Factorisation of the complete graph into spanning regular factors

Mahdieh Hasheminezhad
Department of Mathematical Sciences
Yazd University
Yazd, Iran
[email protected] Brendan D. McKay
School of Computing
Australian National University
Canberra, ACT 2601, Australia
[email protected] Supported by the Australian Research Council

Abstract

We enumerate factorisations of the complete graph into spanning regular graphs in several cases, including when the degrees of all the factors except for one or two are small. The resulting asymptotic behaviour is seen to generalise the number of regular graphs in a simple way. This leads us to conjecture a general formula when the number of factors is vanishing compared to the number of vertices.

1 Introduction

A classical problem in enumerative graph theory is the asymptotic number of regular graphs. This has now been solved by the overlap of three papers [4, 6, 7], with the interesting conclusion that the same formula holds in the sparse and dense regimes.

Theorem 1.1.

Let $R_{d}(n)$ be the number of regular graphs of degree $d$ and order $n$ , where $1\leq d\leq n-2$ . Define $\lambda=d/(n-1)$ . Then, as $n\to\infty$ ,

R_{d}(n)\sim\bigl{(}\lambda^{\lambda}(1-\lambda)^{1-\lambda}\bigr{)}^{\!\binom{n}{2}}\binom{n-1}{d}^{\!n}e^{1/2}\,2^{1/2}.

In the above, and throughout the paper, we tacitly assume that regular graphs have even degree whenever the number of vertices is odd.

We can consider $R_{d}(n)$ to count the number partitions of the edges of $K_{n}$ into two spanning regular subgraphs, one of degree $d$ and one of degree $n-d-1$ . This suggests a generalization: how many ways are there to partition the edges of $K_{n}$ into more than two spanning regular subgraphs, of specified degrees?

For integers $d_{0},d_{1},\ldots,d_{k}\geq 1$ such that $\sum_{i=0}^{k}d_{i}=n-1$ , define $R(n;d_{0},\ldots,d_{k})$ to be the number of ways to partition the edges of $K_{n}$ into spanning regular subgraphs of degree $d_{0},d_{1},\ldots,d_{k}$ ? We conjecture that for $k=o(n)$ , the asymptotic answer is a simple generalisation of Theorem 1.1.

Conjecture 1.2.

Define $\lambda_{i}=d_{i}/(n-1)$ for $0\leq i\leq k$ . If $k=o(n)$ , then $R(n;d_{0},\ldots,d_{k})\sim R^{\prime}(n;d_{0},\ldots,d_{k})$ , where

R^{\prime}(n;d_{0},\ldots,d_{k})=\biggl{(}\prod_{i=0}^{k}\lambda_{i}^{\lambda_{i}}\biggr{)}^{\!\binom{n}{2}}\binom{n-1}{d_{0},\ldots,d_{k}}^{\!n}e^{k/4}\,2^{k/2},

using a multinomial coefficient.

We will prove the conjecture in four cases.

1.

$k=1$ and $1\leq d_{1}\leq n-2$ .
2.

$\sum_{i=1}^{k}d_{i}=o(n^{1/3})$ and $\sum_{1\leq i\leq j<t\leq k}d_{i}d_{j}d_{t}^{2}=o(n)$ .
3.

$k=o(n^{5/6})$ and $d_{1}=\cdots=d_{k}=1$ .
4.

$\min\{d_{1},n-1-d_{1}\}\geq cn/\log n$ for some constant $c>\frac{2}{3}$ and $\sum_{i=2}^{k}d_{i}=O(n^{\varepsilon})$ for sufficiently small $\varepsilon>0$ .

Case 1 is just a restatement of Theorem 1.1, since $R_{d}(n)=R(n;n{-}1{-}d,d)$ . Case 2 will follow from a switching argument applied to the probability of two randomly labelled regular graphs being edge-disjoint. Case 3 is a consequence of [8]. Case 4 will follow from a combination of [5], [7] and Part 1. Case 2 with $k=2$ , $d_{1}=2$ and $d_{2}=O(1)$ appears in [10].

2 Two regular graphs

We begin by considering the case of two arbitrary regular graphs which are randomly labelled. What is the probability of them being edge-disjoint?

Lemma 2.1.

Let $D$ and $H$ be regular graphs on $n$ vertices, where $D$ is $d$ -regular for $d\geq 1$ and $H$ is $h$ -regular for $h\geq 1$ . Suppose $d^{2}h^{2}=o(n)$ and define $M=\lceil\max\{8dh,\log n\}\rceil$ , Then, with probability $1-O(\frac{d^{2}h^{2}}{n})$ , a random relabeling of the vertices of $H$ does not have any common path of length 2 with $D$ and the number of common edges with $D$ is less than $M$ .

Proof.

The probability that a given path of length 2 of $H$ is mapped to a path of length 2 of $D$ is $\frac{2n\binom{d}{2}(n-3)!}{n!}$ and the number of paths of length 2 of $H$ is $n\binom{h}{2}$ . So the expected number of paths of length 2 which are mapped to a path of length 2 is at most

\frac{2n^{2}\binom{d}{2}\binom{h}{2}(n-3)!}{n!}=O\Bigl{(}\frac{d^{2}h^{2}}{n}\Bigr{)}.

So with probability $1-O(\frac{d^{2}h^{2}}{n})$ , a random relabeling of the vertices of $H$ does not have any common path of length 2 with $D$ .

Considering a given set $S$ of $M$ edges of $H$ , the probability that a random relabeling of the vertices of $H$ maps $S$ to $M$ distinct edges of $D$ is

\frac{\binom{nd/2}{M}M!\,2^{M}(n-2M)!}{n!}

Since there are $\binom{nh/2}{M}$ sets of $M$ different edges of $H$ , the expected number of such relabeling is at most

E=\frac{\binom{nh/2}{M}\binom{nd/2}{M}M!\,2^{M}(n-2M)!}{n!}\leq\frac{n^{2M}e^{M}d^{M}h^{M}}{2^{M}M^{M}(n-2M)^{2M}}.

For big enough $n$ , $\frac{n^{2}}{(n-2M)^{2}}\leq 2$ . Hence, the expected number of such relabeling is at most $O((\frac{edh}{M})^{M})$ . Since $M\geq 8dh\geq e^{2}dh$ and $M\geq\log n$ , $(\frac{edh}{M})^{M}\leq e^{-M}\leq n^{-1}$ . This is dominated by the term $\frac{d^{2}h^{2}}{n}$ from the first part of the proof, so with probability $1-O(\frac{d^{2}h^{2}}{n})$ a random relabeling of the vertices of $H$ does not have any common path of length 2 with $D$ and the number of common edges with $D$ is less than $M$ . ∎

Let $\mathcal{L}(t)$ be the set of all relabeling of the vertices of $H$ with no common paths of length 2 with $D$ and exactly $t$ common distinct edges with $D$ . Define $L(t)=|\mathcal{L}(t)|$ , so in particular the number of relabeling 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 estimate the value of $T/L(0)$ by the switching method.

3 The switching

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

•

vertices $a$ , $e$ , $b$ , $f$ are all distinct.
•

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

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

after the permutation, the common edges of $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

•

vertices $a$ , $e$ , $b$ , $f$ are all distinct.
•

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

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

after the permutation, the common edges of $D$ and $H$ are the same except that $ef$ is a common edge of $D$ and $H$ .

Lemma 3.1.

Assume $d,h\geq 1$ , $d^{2}h^{2}=o(n)$ , and define $m_{d}=\frac{nd}{2}$ and $m_{h}=\frac{nh}{2}$ . Then for $1\leq t\leq M$ and $n\to\infty$ we have uniformly

\frac{L(t)}{L(t-1)}=\frac{(m_{d}-(t-1))(m_{h}-(t-1))}{t\,\binom{n}{2}}\Bigl{(}1+O\Bigl{(}\frac{dh}{n}\Bigr{)}\Bigr{)}.

Proof.

By using a forward switching, we will convert a relabeling $\pi\in\mathcal{L}(t)$ to a relabeling $\pi^{\prime}\in\mathcal{L}(t-1)$ . Without lose of generality, we suppose that $\pi=(1)$ , since our estimates will be independent of the structure of $H$ other than its degree.

There are $t$ choices for edge $ab$ and at most $2(\binom{n}{2}-m_{d})=2\binom{n}{2}(1+O(d/n))$ choices for $e$ and $f$ . But some of the choices of $e$ and $f$ are not suitable. There are at most $4n$ choices of $e$ and $f$ such that $a$ , $e$ , $b$ , $f$ are not all distinct.

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$ . If neither $e$ nor $f$ are an end vertex of a common edge, then no common edge is destroyed. Therefore, there are at most $4tn$ pairs $\{e,f\}$ that can destroy a common edge.

If none of the following happens, no new common edge is created by the forward switching:

•

vertex $e$ has a neighbor in $H$ which is a neighbor of $a$ in $D$ .
•

vertex $e$ has a neighbor in $D$ which is a neighbor of $a$ in $H$ .
•

vertex $f$ has a neighbor in $H$ which is a neighbor of $b$ in $D$ .
•

vertex $f$ has a neighbor in $D$ which is a neighbor of $b$ in $H$ .

So, there are at most $4dh$ vertices which do not satisfy one of the above conditions. So there are at most $4dh(n-2(t-1))$ unsuitable couples which can produces some new common edges. Therefore the number of forward switchings is

W_{F}=t\binom{n}{2}\Bigl{(}1+O\Bigl{(}\frac{dh}{n}\Bigr{)}\Bigr{)}.

A reverse switching converts a relabeling $\pi^{\prime}\in\mathcal{L}(t-1)$ to a relabeling $\pi$ in $\mathcal{L}(t)$ . Again, without loss of generality, we can suppose that $\pi^{\prime}=(1)$ . There are $(m_{h}-t+1)$ choices for edge $ab$ and there is at most $2(m_{d}-t+1)$ choices for $e$ and $f$ . But some of the choices of $e$ and $f$ are not suitable.

There are at most $4n$ choices of $e$ and $f$ such that $a$ , $e$ , $b$ , $f$ are not all distinct. If neither $e$ nor $f$ are an end vertex of a common edge, then no common edge is destroyed and also no common edge except $ef$ has an end vertex in $e$ or $f$ . So, there are at most $2td$ unsuitable choices for $e$ and $f$ that may can destroy a common edge or construct a common path of length 2.

If none of the following happens, no other new common edge obtains after doing the reverse switching:

•

vertex $e$ has a neighbor in $H$ which is a neighbor of $a$ in $D$ .
•

vertex $e$ has a neighbor in $D$ which is a neighbor of $a$ in $H$ .
•

vertex $f$ has a neighbor in $H$ which is a neighbor of $b$ in $D$ .
•

vertex $f$ has a neighbor in $D$ which is a neighbor of $b$ in $H$ .

So, there are at most $4dh$ vertices which does not satisfy one of the above conditions. So there are at most $4d^{2}h$ unsuitable couples which can produces some other new common edges.

Therefore the number of reverse switchings is

W_{R}=\bigl{(}m_{d}-t+1\bigr{)}\bigl{(}m_{h}-t+1\bigr{)}\Bigl{(}1+O\Bigl{(}\frac{dh}{n}\Bigr{)}\Bigr{)}.

By considering the number of forward switchings and the number of reverse switchings, we have

\frac{L(t)}{L(t-1)}=\frac{(m_{d}-t+1)(m_{h}-t+1)}{{t\binom{n}{2}}}\Bigl{(}1+O\Bigl{(}\frac{dh}{n}\Bigr{)}\Bigr{)}.\qed

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

Lemma 3.2.

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}.

Lemma 3.3.

Let $d,h\geq 1$ and $d^{2}h^{2}=o(n)$ . Then, as $n\to\infty$ ,

\frac{T}{L(0)}=\exp\Bigl{(}\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}dh+O\Bigl{(}\frac{d^{2}h^{2}}{n}\Bigr{)}\Bigr{)}.

Proof.

The condition $d^{2}h^{2}=o(n)$ and the definition of $M$ allow us to write Lemma 3.1 as

\frac{L(t)}{L(t-1)}=\frac{dh}{2t}\Bigl{(}1-(t-1)\frac{2(d+h)}{dhn}\Bigr{)}\Bigl{(}1+O\Bigl{(}\frac{dh}{n}\Bigr{)}\Bigr{)},

where the implicit constant in the $O(\,)$ depends on $t$ but is uniformly bounded for $1\leq t\leq M$ . For $0\leq t\leq M$ , define

	$\displaystyle A(t)$	$\displaystyle=\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}dh\Bigl{(}1+O\Bigl{(}\frac{dh}{n}\Bigr{)}\Bigr{)}$
	$\displaystyle B(t)$	$\displaystyle=\frac{2(d+h)}{dhn},$

Then $A(t)\geq 0$ and $1-(t-1)B(t)\geq 0$ as $n\to\infty$ . Define $A_{1}$ , $A_{2}$ , $C_{1}$ and $C_{2}$ as in Lemma 3.2. This gives

	$\displaystyle A_{1},A_{2}$	$\displaystyle=\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}dh\Bigl{(}1+O\Bigl{(}\frac{dh}{n}\Bigr{)}\Bigr{)}=O(dh),$
	$\displaystyle C_{1},C_{2}$	$\displaystyle=O\Bigl{(}\frac{d+h}{n}\Bigr{)}.$

The condition $\max\{A/M,|C|\}\leq\hat{c}$ of Lemma 3.2 is satisfied with $\hat{c}=\frac{1}{15}$ , due to $d^{2}h^{2}=o(n)$ and the definition of $M$ . We also have

A_{1}C_{2},A_{2}C_{1},A_{2}C_{1}^{2}=O\Bigl{(}\frac{dh(d+h)}{n}\Bigr{)}

and $(2e\hat{c})^{M}\leq n^{\log(2e/15)}=o(n^{-1})$ . Therefore, by Lemma 3.2,

\frac{T}{L(0)}=\exp\Bigl{(}\,\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}dh+O\Bigl{(}\frac{d^{2}h^{2}}{n}\Bigr{)}\Bigr{)}.\qed

Theorem 3.4.

Let $D$ and $H$ be regular graphs on $n$ vertices, where $D$ is $d$ -regular for $d\geq 1$ and $H$ is $h$ -regular for $h\geq 1$ . Suppose $d^{2}h^{2}=o(n)$ as $n\to\infty$ . Then the probability that a random relabelling of $H$ is edge-disjoint from $D$ is

\exp\Bigl{(}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}dh+O\Bigl{(}\frac{d^{2}h^{2}}{n}\Bigr{)}\Bigr{)}.

Proof.

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

\exp\Bigl{(}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}dh+O\Bigl{(}\frac{d^{2}h^{2}}{n}\Bigr{)}\Bigr{)},

by Lemma 3.3. Multiplying these probabilities together gives the theorem. ∎

Since the formula in Theorem 3.4 does not depend on the structure of $D$ or $H$ , the same formula holds if one or both $H$ and $D$ are random regular graphs with the given degrees.

Corollary 3.5.

Let $D_{1},D_{2},\ldots,D_{k}$ be regular graphs on $n$ vertices, with degrees $d_{1},\ldots,d_{k}$ , respectively. Assume $d_{i}\geq 1$ , $i=1,\ldots,k$ and $\sum_{1\leq i\leq j<t\leq k}d_{i}d_{j}d_{t}^{2}=o(n)$ as $n\to\infty$ . Then the probability that $D_{1},D_{2},\ldots,D_{k}$ are edge-disjoint after random relabelling is

\exp\Bigl{(}-\lower 0.6458pt\hbox{\large$\textstyle\frac{1}{2}$}\sum_{1\leq i<j\leq k}d_{i}d_{j}+O\Bigl{(}\frac{\sum_{1\leq i\leq j<t\leq k}d_{i}d_{j}d_{t}^{2}}{n}\Bigr{)}\Bigr{)}.

Proof.

First compute the probability that a random relabeling of $D_{2}$ has no common edges with $D_{1}$ . Then, let $D_{1}+D_{2}$ be the $d_{1}+d_{2}$ -regular graph obtained from merging $D_{1}$ and $D_{2}$ and compute the probability that a random relabeling of $D_{3}$ has no common edges with $D_{1}+D_{2}$ . We continue doing these computations inductively. The corollary obtained by applying Theorem 3.4 repeatedly. It can be shown that this form of the error term is the best that follows from Theorem 3.4 and that it is minimized when $d_{1}\geq\cdots\geq d_{k}$ . ∎

Now we can prove our first new case of Conjecture 1.2.

Theorem 3.6.

Let $d_{0},d_{1},\ldots,d_{k}\geq 1$ be integers such that $\sum_{j=0}^{n}d_{j}=n-1$ . Define $d=\sum_{i=1}^{k}d_{i}$ and suppose that $\sum_{1\leq i\leq j<t\leq k}d_{i}d_{j}d_{t}^{2}=o(n)$ and $d^{3}=o(n)$ as $n\to\infty$ . Define $\lambda_{j}=\frac{d_{j}}{n-1}$ for each $j$ . Then

R(n;d_{0},\ldots,d_{k})=R^{\prime}(n;d_{0},\ldots,d_{k})\Bigl{(}1+O\Bigl{(}\frac{d^{3}}{n}+\frac{1}{n}\sum_{1\leq i\leq j<t\leq k}d_{i}d_{j}d_{t}^{2}\Bigr{)}\Bigr{)},

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

Proof.

We can construct all such factorisations by choosing edge-disjoint regular graphs $D_{1},\ldots,D_{k}$ of degrees $d_{1},\ldots,d_{k}$ .

In the case of $k=1$ , we are counting regular graphs, and it was shown in [7] that

R_{d_{i}}(n)=R^{\prime}(n;n{-}1{-}d_{i},d_{i})\bigl{(}1+O(d_{i}^{2}/n)\bigr{)},

(3.1)

provided the error term is $o(1)$ . Now we can write

R(n;d_{0},\ldots,d_{k})=P(n;d_{1},\ldots,d_{k})\,\prod_{i=1}^{k}\,R_{d_{i}}(n),

where $P(n;d_{1},\ldots,d_{k})$ is the expression in Corollary 3.5. Using $(1-x)\log(1-x)=-x+\frac{1}{2}x^{2}+O(x^{3})$ we have

	$\displaystyle\log\frac{\prod_{i=1}^{k}\bigl{(}\lambda_{i}^{\lambda_{i}}(1-\lambda_{i})^{1-\lambda_{i}}\bigr{)}}{\bigl{(}1-\sum_{i=1}^{k}\lambda_{i}\bigr{)}^{1-\sum_{i=1}^{k}\lambda_{i}}\prod_{i=1}^{k}\lambda_{i}^{\lambda_{i}}}$	$\displaystyle=-\sum_{1\leq i<j\leq k}\lambda_{i}\lambda_{j}+O(d^{3}/n^{3})$
		$\displaystyle=-\frac{1}{n(n-1)}\sum_{1\leq i<j\leq k}d_{i}d_{j}+O(d^{3}/n^{3}).$

For $1\leq x=o(n^{1/2})$ we have $\sum_{i=0}^{x-1}\log(1-i/(n-1))=-x(x-1)/(2n)+O(x^{3}/n^{2})$ , so

\log\frac{\binom{n-1}{d_{0},\ldots,d_{k}}}{\prod_{i=1}^{k}\binom{n-1}{d_{i}}}=\frac{1}{n}\sum_{1\leq i<j\leq k}d_{i}d_{j}+O(d^{3}/n^{2}).

Putting the parts together with (3.1) completes the proof. ∎

Conjecture 1.2 proposes that $R^{\prime}(n;d_{0},d_{1},\ldots,d_{n})$ matches $R^{\prime}(n;d_{0},d_{1},\ldots,d_{n})$ over a much wider domain than we can proved. One case we can test using earlier work concerns partial 1-factorisations of $K_{n}$ . Let $F(n,k)$ be the number of sequences of $k$ disjoint perfect matchings in $K_{n}$ . Note that $F(n,n-2)=F(n,n-1)$ ; we will use only $F(n,n-2)$ . In our notation, $F(n,k)=R(n;n{-}k{-}1,1,\ldots,1)$ , where there are $k$ explicit ones. In [8], McLeod found the asymptotic value of $F(n,k)$ for $k=o(n^{5/6})$ , namely,

F(n,k)\sim\Bigl{(}\frac{n!}{2^{n/2}(n/2)!}\Bigr{)}^{\!k}\Bigl{(}\frac{n!}{n^{k}(n-k)!}\Bigr{)}^{\!n/2}\Bigl{(}1-\frac{k}{n}\Bigr{)}^{\!n/4}e^{k/4}.

The reader can check that this expression is equal to $R^{\prime}(n;n{-}1{-}k,1,\ldots,1)$ asymptotically when $k=o(n^{6/7})$ .

Refer to caption — Figure 1: Partial 1-factorisations. $F(n,k)/R^{\prime}(n;n{-}1{-}k,1,\ldots,1)$ for $n=12$ (circles) and $n=14$ (diamonds). The horizontal scale is $x=k/(n-2)$ and the curve is $e^{-x/6}$ .

To illustrate what happens when $k$ is even larger, Figure 1 shows the ratio

F(n,k)/R^{\prime}(n;n{-}1{-}k,1,\ldots,1)

for the largest sizes for which $F(n,k)$ is known exactly [1, 3]. Experiment suggests that $F(n,x(n-2))/R^{\prime}(n;n{-}1{-}x(n-2),1,\ldots,1)$ converges to a continuous function $f(x)$ as $n\to\infty$ with $x$ fixed. Conjecture 1.2 in this cases corresponds to $f(0)=1$ . At the other end, $x=1$ corresponding to complete 1-factorisations, we can also check the 3-digit estimates of $F(n,n-2)$ in [1] for $n=16,18$ —they give ratios 0.844 and 0.845, respectively.

Another case that we can solve is when there are two components of high degree and some number of low degree. In [5], the second author considered the case when $k=2$ , $\min\{d_{1},n-1-d_{1}\}\geq cn/\log n$ for some $c>\frac{2}{3}$ , and $d_{2}=o(n^{\varepsilon})$ for some sufficiently small $\varepsilon>0$ . In this case, the probability that a random $d_{1}$ -regular graph and an arbitrary $d_{2}$ -regular graph are edge-disjoint is asymptotic to

(1-\lambda_{1})^{d_{2}n/2}\exp\Bigl{(}-\frac{\lambda_{1}d_{2}(d_{2}-2)}{4(1-\lambda_{1})}\Bigr{)}.

(3.2)

Note that this is not uniform over $d_{1}$ -regular graphs, but an average over them. However, within the error term it is uniform over $d_{2}$ -regular graphs and that is enough.

Theorem 3.7.

Let $d_{1},d_{2},\ldots,d_{k}\geq 1$ be such that $\min\{d_{1},n-1-d_{1}\}\geq cn/\log n$ for some $c>\frac{2}{3}$ and $d_{2}+\cdots+d_{k}=O(n^{\varepsilon})$ for sufficiently small $\varepsilon>0$ . Let $d_{0}=n-1-\sum_{i=1}^{k}d_{i}$ . Then, as $n\to\infty$ ,

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

Proof.

Let $\hat{d}=\sum_{i=2}^{k}d_{i}$ . By Theorem 3.6, the number of $\hat{d}$ -regular graphs partitioned into $d_{2},\ldots,d_{k}$ -regular graphs is asymptotic to $R^{\prime}(n;n{-}1{-}\hat{d},d_{2},\ldots,d_{k})$ . By (3.1), the number of $d_{1}$ -regular graphs is asymptotic to $R^{\prime}(n;n{-}1{-}d_{1},d_{1})$ . The probability of these two graphs being edge disjoint when the $d_{1}$ -regular graph is chosen randomly is given by (3.2) (with $\hat{d}$ in place of $d_{2}$ ). The product of these three quantities is asymptotic to $R^{\prime}(n;n{-}1{-}d_{1}{-}\hat{d},d_{1},\ldots,d_{k})$ . ∎

4 Concluding remarks

We have proposed an asymptotic formula for the number of ways to partition a complete graph into spanning regular subgraphs and proved it in several cases. The analytic method described in [2] will be sufficient to test the conjecture when there are many factors of high degree. That will be the topic of a future paper.

References

[1] J. H. Dinitz, D. K. Garnick and B. D. McKay, There are 526,915,620 nonisomorphic one-factorizations of $K_{12}$ J. Combin. Designs, 2 (1994) 273–285.
[2] M. Isaev and B. D. McKay, Complex martingales and asymptotic enumeration, Random Structures Algorithms, 52 (2018) 617–661.
[3] P. Kaski and P. R. J. Östergård, There are 1,132,835,421,602,062,347 nonisomorphic one-factorizations of $K_{14}$ , J. Combin. Designs, 17 (2009) 147–159.
[4] A. Liebenau and N. Wormald, Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, preprint 2017. https://arxiv.org/abs/1702.08373.
[5] B. D. McKay, Subgraphs of dense random graphs with specified degrees, Combin. Prob. Comput., 20 (2011) 413–433.
[6] B. D. McKay and N. C. Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, European J. Combin, 11 (1990) 565–580.
[7] B. D. McKay and N. C. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees $o(\sqrt{n})$ , Combinatorica, 11 (1991) 369–382.
[8] J. C. McLeod, Asymptotic enumeration of $k$ -edge-colored $k$ -regular graphs, SIAM J. Discrete Math. 23 (2010) 2178–2197.
[9] C. Greenhill, B. D. McKay and X. Wang, Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums, J. Comb. Theory Ser. A, 113 (2006) 291–324.
[10] H. D. Robalewska, 2-Factors in random regular graphs, J. Graph Theory, 23 (1996) 215–224.