On the Number of Linear Multipartite Hypergraphs with Given Size

Abstract

For any given integer $r\geqslant 3$, let $k=k(n)$ be an integer with $r\leqslant k\leqslant n$. A hypergraph is r-uniform if each edge is a set of r vertices, and is said to be linear if two edges intersect in at most one vertex. Let $A_1,\ldots ,A_k$ be a given k-partition of [n] with $|A_i|=n_i\geqslant 1$. An r-uniform hypergraph H is called k-partite if each edge e satisfies $|e\cap A_i|\leqslant 1$ for $1\leqslant i\leqslant k$. In this paper, the number of linear k-partite r-uniform hypergraphs on $n\rightarrow \infty$ vertices is determined asymptotically when the number of edges is $m(n)=o(n^{\frac{4}{3}})$. For $k=n$, it is the number of linear r-uniform hypergraphs on vertex set [n] with $m=o(n^{ \frac{4}{3}})$ edges.

1 Introduction

For any given integer $r\geqslant 3$, a hypergraph H on vertex set [n] is an r-uniform hypergraph (r-graph for short) if each edge is a set of r vertices, and is said to be a linear hypergraph if two edges intersect in at most one vertex. Little is known about the number of distinct linear hypergraphs. An asymptotic enumeration formula for the logarithm of the number of linear hypergraphs on $n\rightarrow \infty$ vertices is obtained by Grable and Phelps [5]. They also obtained the logarithm of the number of partial Steiner $(n,r,\ell )$-systems with $2\leqslant \ell \leqslant r-1$, where a partial Steiner $(n,r,\ell )$-system is an r-graph H such that every subset of size $\ell$ lies in at most one edge of H; the (n, r, 2)-systems are linear hypergraphs. Asratian and Kuzjurin [1] gave another proof. Blinovsky and Greenhill [3, 4] used the switching method to obtain the asymptotic number of sparse uniform and linear uniform hypergraphs with given order and degree sequence. Balogh and Li [2] obtained an upper bound on the number of linear uniform hypergraphs with given order and girth.

It is interesting to consider the enumeration of linear hypergraphs with given size. Let ${\mathcal {H}}_r(n,m)$ denote the set of r-graphs on vertex set [n] with m edges. Let ${\mathcal {L}}_r(n,m)$ denote the set of linear hypergraphs in ${\mathcal {H}}_r(n,m)$. The previous works most relevant to this one are [7, 8]. Hasheminezhad and McKay [7] obtained the asymptotic number of linear hypergraphs with a given number of edges of each size, assuming a constant bound on the edge size and $o(n^{\frac{4}{3}})$ edges. McKay and Tian [8] obtained the asymptotic enumeration formula for the set of ${\mathcal {L}}_r(n,m)$ as far as $m=o(n^{ \frac{3}{2}})$. Let $[x]_t=x(x-1)\cdots (x-t+1)$ be the falling factorial. The standard asymptotic notations o and O refer to $n\rightarrow \infty$. The floor and ceiling signs are omitted whenever they are not crucial.

Let s and $k=k(n)$ be integers with $1\leqslant s\leqslant r\leqslant k\leqslant n$, and $N_s$ be an abbreviation for $\left( {\begin{array}{c}n\\ s\end{array}}\right)$. Let $A_1,\ldots ,A_k$ be a given k-partition of [n] with $|A_i|=n_i\geqslant 1$, ${\tilde{\mathbf{n}}}=(n_1,\ldots ,n_k)$ and $\sigma _{s}({\tilde{\mathbf{n}}}) =\sum _{1\leqslant i_1<\cdots <i_s\leqslant k}n_{i_1}\cdots n_{i_{s}}$ be the s-th elementary symmetric function of ${\tilde{\mathbf{n}}}$. We use $A_{i_1}\cdots A_{i_s}$ to denote the set of s-sets $F_s$ of [n] such that $|F_s \cap A_{i_j}|= 1$ for all $1\leqslant j\leqslant s$, and ${\mathcal {E}}_s({\tilde{\mathbf{n}}})=\bigcup _{1\leqslant i_1<\cdots <i_s\leqslant k} A_{i_1}\cdots A_{i_s}$ for all $1\leqslant s\leqslant r$. An r-graph H is called k-partite if each edge e satisfies $e\in {\mathcal {E}}_r(\tilde{\mathbf{n}})$. Let ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$ denote the set of k-partite r-graphs with m edges and with vertex partition determined by ${\tilde{\mathbf{n}}}$, and let ${\mathcal {L}}_r({\tilde{\mathbf{n}}},m)$ denote the set of all linear hypergraphs in ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$. In this paper, we obtain an asymptotic enumeration formula for $|{\mathcal {L}}_r({\tilde{\mathbf{n}}},m)|$ as far as $m=o(n^{ \frac{4}{3}})$.

Theorem 1.1

For a fixed integer $r\geqslant 3$, let s and $k=k(n)$ be integers with $1\leqslant s\leqslant r\leqslant k\leqslant n$, and let $m=m(n)$ be an integer with $m=o(n^{ \frac{4}{3}})$. Let ${\tilde{\mathbf{n}}}=(n_1,\ldots ,n_k)$ and $\sigma _{s}({\tilde{\mathbf{n}}})=\sum _{1\leqslant i_1<\cdots <i_s\leqslant k}n_{i_1}\cdots n_{i_{s}}$ be the s-th elementary symmetric function of ${\tilde{\mathbf{n}}}$. Suppose that there exists a constant $C>0$ such that $\sum _{i=1}^k \frac{1}{n_i}\leqslant C \frac{k^2}{n}$. Then, as $n\rightarrow \infty$

$$\begin{aligned} |{\mathcal {L}}_r({\tilde{\mathbf{n}}},m)|={ \frac{ \sigma _{r}^m({\tilde{\mathbf{n}}})}{m!}} \exp \biggl [- \frac{\sigma _{2}({\tilde{\mathbf{n}}}) \sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _{r}^2({\tilde{\mathbf{n}}})}+ O\biggl ( \frac{m^2}{n^{3}}+ \frac{m^3}{n^{4}}\biggr )\biggr ]. \end{aligned}$$

Note that if there exists a constant $c>0$ such that $n_i\geqslant c \frac{n}{k}$ for $1\leqslant i\leqslant k$, Theorem 1.1 holds. Also, for example, if $n_1=\ldots =n_p=n^{ \frac{1}{2}}$ for some positive constant $p<k$, $n_{p+1}=\ldots =n_k=1$, then $k=n+p-pn^{ \frac{1}{2}}$ and Theorem 1.1 holds; if $n_1=\ldots =n_\ell =c'n$, $n_{\ell +1}=\ldots =n_k=1$ for some positive constants $\ell <k$ and $c'$ such that $c'\ell <1$, then $k=(1- c'\ell ) n+\ell$ and Theorem 1.1 holds. For n sufficiently large, many cases satisfy $\sum _{i=1}^k \frac{1}{n_i}\leqslant C \frac{k^2}{n}$ for some constant $C>0$. In particular, for $k=n$, k-partite r-graphs are general r-graphs, $\sigma _{2}({\tilde{\mathbf{n}}})= N_2$, $\sigma _{r-2}({\tilde{\mathbf{n}}})= N_{r-2}$ and $\sigma _{r}({\tilde{\mathbf{n}}})= N_r$. We have the following corollary on the number of linear r-graphs on [n] with $m=o(n^{ \frac{4}{3}})$ edges, which coincides with the uniform case in [7] and is a subcase in [8].

Corollary 1.2

For any fixed integer $r\geqslant 3$, let $m=m(n)$ be an integer with $m=o(n^{ \frac{4}{3}})$. Then, as $n\rightarrow \infty$,

$$\begin{aligned} |{\mathcal {L}}_r(n,m)| ={ \frac{ N_r^m}{m!}} \exp \biggl [- \frac{[r]_2^2[m]_2}{4n^2}+O\biggl ( \frac{m^2}{n^{3}}+ \frac{m^3}{n^{4}}\biggr )\biggr ]. \end{aligned}$$

The remainder of the paper is structured as follows. Lemmas are presented in Section 2. In Section 3, we complete the enumeration of ${\mathcal {L}}_r({\tilde{\mathbf{n}}},m)$ with $m=o(n^{ \frac{4}{3}})$.

2 Some Lemmas

In order to identify several events which have low probabilities in the uniform probability space ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$ with $m=o(n^{ \frac{4}{3}})$, the following lemmas will be useful.

Lemma 2.1

For a fixed integer $r\geqslant 3$, let s and $k=k(n)$ be integers with $1\leqslant s\leqslant r\leqslant k\leqslant n$. Let $\sigma _{s}({\tilde{\mathbf{n}}})$ be the s-th elementary symmetric function of ${\tilde{\mathbf{n}}}=(n_1,\ldots ,n_k)$. Suppose that there exists a constant $C>0$ such that $\sum _{i=1}^k \frac{1}{n_i}\leqslant C \frac{k^2}{n}$. Then $\sigma _{s}({\tilde{\mathbf{n}}})= O( n^{s-r})\sigma _r({\tilde{\mathbf{n}}})$.

Proof

Let $S_j({\tilde{\mathbf{n}}})=\left( {\begin{array}{c}k\\ j\end{array}}\right) ^{-1}\sigma _j({\tilde{\mathbf{n}}})$ for all $j=0,\ldots ,k$. It is clear that $S_{k-1}({\tilde{\mathbf{n}}})=k^{-1}\sum _{i=1}^k \frac{n_1\cdots n_k}{n_i}$ and $S_{k}({\tilde{\mathbf{n}}})=n_1\cdots n_k$. By Newton’s inequality, we have $S_{j-1}({\tilde{\mathbf{n}}})S_{j+1}({\tilde{\mathbf{n}}})\leqslant S_{j}^2({\tilde{\mathbf{n}}})$, and then

$$\begin{aligned} \frac{S_{s-1}({\tilde{\mathbf{n}}})}{S_{s}({\tilde{\mathbf{n}}})}\leqslant \frac{S_{s}({\tilde{\mathbf{n}}})}{S_{s+1}({\tilde{\mathbf{n}}})}\leqslant \cdots \leqslant \frac{S_{k-1}({\tilde{\mathbf{n}}})}{S_{k}({\tilde{\mathbf{n}}})}= \frac{1}{k}\sum _{i=1}^k\frac{1}{n_i}\leqslant C \frac{k}{n}. \end{aligned}$$

Therefore

$$\begin{aligned} \frac{\sigma _s({\tilde{\mathbf{n}}})}{\sigma _r({\tilde{\mathbf{n}}})} = \frac{[r]_{r-s}}{[k-s]_{r-s}}\, \frac{S_s({\tilde{\mathbf{n}}})}{S_r({\tilde{\mathbf{n}}})} \leqslant \frac{[r]_{r-s}}{[k-s]_{r-s}} \, \frac{C^{r-s}k^{r-s}}{n^{r-s}} = O(n^{s-r}), \end{aligned}$$

where the last step holds since $s\leqslant r=O(1)$ and $k\geqslant r$ imply that $k^{r-s} = O([k-s]_{r-s})$. $\square$

The following two lemmas are vector forms of [8, Lemmas 2.1 and 2.2]. Their proofs are similar to those in [8], but Lemma 2.1 is a key requirement in the proof of Lemma 2.3.

Lemma 2.2

For a fixed integer $r\geqslant 3$, let $k=k(n)$ be an integer with $r\leqslant k\leqslant n$, and H be chosen uniformly at random from ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$. Let $t=t(n)\geqslant 1$ be an integer and $e_1,\ldots ,e_{t}$ be distinct r-sets in ${\mathcal {E}}_r({\tilde{\mathbf{n}}})$. Then the probability that $\{e_1,\ldots ,e_t\}$ are edges of H is at most $\bigl ( \frac{m}{\sigma _{r}({\tilde{\mathbf{n}}})}\bigr )^t$.

Proof

Since H is a k-partite r-graph that is chosen uniformly at random from ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$, the probability that $e_1,\ldots ,e_t$ are edges of H is

$$\begin{aligned} \frac{\left( {\begin{array}{c}\sigma _{r}({\tilde{\mathbf{n}}})-t\\ m-t\end{array}}\right) }{\left( {\begin{array}{c}\sigma _{r}({\tilde{\mathbf{n}}})\\ m\end{array}}\right) }&= \frac{[m]_t}{[\sigma _{r}({\tilde{\mathbf{n}}})]_t}= \prod _{i=0}^{t-1} \frac{m-i}{\sigma _{r}({\tilde{\mathbf{n}}})-i} \leqslant \Bigl ( \frac{m}{\sigma _{r}({\tilde{\mathbf{n}}})}\Bigr )^t. \end{aligned}$$

$\square$

Lemma 2.3

Let $r\geqslant 3$, t and $\alpha$ be integers such that $r,t,\alpha =O(1)$ and $0\leqslant \alpha \leqslant rt$. For any integer $k=k(n)$ with $r\leqslant k\leqslant n$, let H be chosen uniformly at random from ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$. If there exists a constant $C>0$ such that $\sum _{i=1}^k \frac{1}{n_i}\leqslant C \frac{k^2}{n}$, then the expected number of sets of t edges whose union has $rt-\alpha$ or fewer vertices is $O(m^tn^{-\alpha })$.

Proof

Let $e_1,\ldots ,e_t$ be distinct r-sets in ${\mathcal {E}}_r({\tilde{\mathbf{n}}})$. We first bound the number of sequences $e_1,\ldots ,e_t$ such that $|e_1\cup \cdots \cup e_t|=rt-\beta$ for some $\beta$ with $\alpha \leqslant \beta <rt$, regardless of whether they are edges of H. For $2\leqslant i\leqslant t$, define $a_i=|(e_1\cup \cdots \cup e_{i-1})\cap e_i|$, thus we have $\sum _{i=2}^ta_i=\beta$. The first r-set $e_1$ can be chosen in $\sigma _{r}({\tilde{\mathbf{n}}})$ ways, then for $2\leqslant i\leqslant t$, the number of choices for $e_i$ given $e_1,\ldots ,e_{i-1}$ is at most $(rt)^{a_i}\sigma _{r-a_i}({\tilde{\mathbf{n}}})$. Note that by Lemma 2.1, $\sigma _{r-a_i}({\tilde{\mathbf{n}}})=\sigma _{r}({\tilde{\mathbf{n}}})O(n^{-a_i})$. Therefore, the number of choices of $e_1,\ldots ,e_t$ for given $\beta ,a_2,\ldots ,a_t$ is at most $O(1)\sigma _{r}^t({\tilde{\mathbf{n}}})\prod _{i=2}^{t}(rt)^{a_i}n^{-a_i}=O(\sigma _{r}^t({\tilde{\mathbf{n}}})n^{-\beta })$.

The number of choices of $a_2,\ldots ,a_t$ given $\beta$ is at most O(1) by $r, t=O(1)$. Also, by Lemma 2.2, the probability that $e_1,\ldots ,e_t\in H$ is at most $(m/\sigma _{r}({\tilde{\mathbf{n}}}))^t$. Therefore, the expected number of sets of t edges of H whose union has size $rt-\beta$ is $O(m^tn^{-\beta })$, uniformly over $\beta$. Finally, the sum of this expression over $\beta \geqslant \alpha$ is bounded by a decreasing geometric series dominated by the term $\beta =\alpha$. This completes the proof. $\square$

We also need the following Lemma from [6], which was used to enumerate some hypergraphs in [3, 4, 7, 8].

Lemma 2.4

( [6], Corollary 4.5) Let $N\geqslant 2$ be an integer, and for $1\leqslant i\leqslant N$, let real numbers A(i), B(i) be given such that $A(i)\geqslant 0$ and $1-(i-1)B(i)\geqslant 0$. Define $A_1=\min _{i=1}^NA(i)$, $A_2=\max _{i=1}^NA(i)$, $C_1=\min _{i=1}^NA(i)B(i)$ and $C_2=\max _{i=1}^NA(i)B(i)$. Suppose that there exists a real number ${\hat{c}}$ with $0<{\hat{c}}< \frac{1}{3}$ such that $\max \{A/N,|C|\}\leqslant {\hat{c}}$ for all $A\in [A_1,A_2]$, $C\in [C_1,C_2]$. Define $h_0$, $h_1$, $\ldots$, $h_N$ by $h_0=1$ and $\frac{h_i}{h_{i-1}}= \frac{A(i)}{i}(1-(i-1)B(i))$ for $1\leqslant i\leqslant N$, with the following interpretation: if $A(i)= 0$ or $1-(i-1)B(i)=0$, then $h_j=0$ for $i\leqslant j\leqslant N$. Then $\Sigma _1\leqslant \sum _{i=0}^{N}h_i\leqslant \Sigma _2$, where $\Sigma _1=\exp [A_1- \frac{1}{2}A_1C_2]-(2e{\hat{c}})^N$ and $\Sigma _2=\exp [A_2- \frac{1}{2}A_2C_1+ \frac{1}{2}A_2C_1^2]+(2e{\hat{c}})^N$.

3 Enumeration of ${\mathcal {L}}_r({\tilde{\mathbf{n}}},m)$ with $m=o(n^{ \frac{4}{3}})$

Let H be a k-partite r-graph in ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$. As defined in [8], a 2-set $\{x,y\}\subseteq [n]$ is called a link if there are two distinct edges e, f such that $\{x,y\}\subseteq e\cap f$. The two edges e and f are called linked edges if $|e\cap f|\geqslant 2$. Let $G_H$ be the simple graph whose vertices are the edges of H, with two vertices of G adjacent iff the corresponding edges of H are linked. An edge-induced subgraph of H corresponding to a non-trivial component of $G_H$ is called a cluster of H.

Let $\mathbb {P}_r({\tilde{\mathbf{n}}},m)$ denote the probability that a k-partite r-graph $H\in {\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$ chosen uniformly at random is linear. Hence,

$$\begin{aligned} |{\mathcal {L}}_r({\tilde{\mathbf{n}}},m)|=\left( {\begin{array}{c}\sigma _{r}({\tilde{\mathbf{n}}})\\ m\end{array}}\right) \mathbb {P}_r({\tilde{\mathbf{n}}},m). \end{aligned}$$

(1)

We will prove that $\mathbb {P}_r({\tilde{\mathbf{n}}},m)$ equals the exponential factor in Theorem 1.1.

Firstly, we show that most of ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$ has a simple structure. Define ${\mathcal {H}}_r^+({\tilde{\mathbf{n}}},m)\subseteq {\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$ to be the set of k-partite r-graphs H which satisfy the following two properties $\mathbf (a)$ and $\mathbf (b)$.

• (a) Every cluster of H consists of two edges overlapping by two vertices.

• (b) The number of clusters in H is at most M, where $M=\Bigl \lceil \log n+ \frac{56\sigma _{r-2}^2({\tilde{\mathbf{n}}})\sigma _2({\tilde{\mathbf{n}}})m^2}{\sigma _{r}^2({\tilde{\mathbf{n}}})}\Bigr \rceil.$

We show that the expected number of k-partite r-graphs in ${\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$ not satisfying the properties of ${\mathcal {H}}_r^+({\tilde{\mathbf{n}}},m)$ is quite small.

Lemma 3.1

For a fixed integer $r\geqslant 3$, let $k=k(n)$ and $m=m(n)$ be integers with $r\leqslant k\leqslant n$ and $m=o(n^{ \frac{4}{3}})$. Then, as $n\rightarrow \infty$, $\frac{|{\mathcal {H}}_r^+({\tilde{\mathbf{n}}},m)|}{|{\mathcal {H}}_r({\tilde{\mathbf{n}}},m)|} =1-O\bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\bigr )$.

Proof

Consider $H\in {\mathcal {H}}_r({\tilde{\mathbf{n}}},m)$ chosen uniformly at random. We apply Lemma 2.3 several times to show that H satisfies the properties $\mathbf (a)$ and $\mathbf (b)$ with probability $1-O\bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\bigr )$.

If two edges overlap by three or more vertices, then they have at most $2r-3$ vertices in total, which has probability $O\bigl ( \frac{m^2}{n^{3}}\bigr )$ by Lemma 2.3. Similarly if there is a cluster of more than two edges, then three of those edges have at most $3r-4$ vertices in total, which has probability $O\bigl ( \frac{m^3}{n^{4}}\bigr )$ by Lemma 2.3. Therefore, H satisfies the property $\mathbf (a)$ with probability $1-O\bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\bigr )$.

Note that if $\mathbf (a)$ holds, all clusters have two edges and no two clusters share an edge or a link. Define the event

$$\begin{aligned} {\mathcal {D}}=\{\hbox {there exist at least } d \hbox { edge- and link-disjoint clusters in } H\}, \end{aligned}$$

where $d=M+1$. Using Lemma 2.2, we have

$$\begin{aligned} \mathbb {P}[{\mathcal {D}}]&=O\biggl (\sigma _{r-2}^{2d}({\tilde{\mathbf{n}}}) {\sigma _2({\tilde{\mathbf{n}}})\atopwithdelims ()d}\biggl (\frac{m}{\sigma _{r}({\tilde{\mathbf{n}}})}\biggr )^{\!2d\,}\biggr )\\&=O\biggl (\biggl ( \frac{e\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})m^2}{d \sigma _{r}^2({\tilde{\mathbf{n}}})}\biggr )^{\!d\,}\biggr )\\&=O\Bigl ( \Bigl (\frac{e}{56}\Bigr )^{\!d\,}\Bigr )\\&=O\Bigl ( \frac{1}{n^{3}}\Bigr ), \end{aligned}$$

where the last two inequalities are true because $d> \frac{56\sigma _{r-2}^2({\tilde{\mathbf{n}}})\sigma _2({\tilde{\mathbf{n}}})m^2}{\sigma _{r}^2({\tilde{\mathbf{n}}})}$ and $d>\log n$. The proof is complete on noting that the event “$\mathbf (a)$ and $\mathbf (b)$ hold” is contained in the union of the events “$\mathbf (a)$ holds” and “${\mathcal {D}}$ doesn’t hold”. $\square$

From the proof of Lemma 3.1, we have $|{\mathcal {H}}_r^+({\tilde{\mathbf{n}}},m)|\ne 0$. Hence, there exists a nonnegative integer t such that the set of k-partite r-graphs with exactly t clusters in ${\mathcal {H}}_r^+({\tilde{\mathbf{n}}},m)$ is nonempty and is denoted by ${\mathcal {C}}_{t}^{+}$. By the definition of ${\mathcal {H}}_r^+({\tilde{\mathbf{n}}},m)$ we have $|{\mathcal {H}}_r^+({\tilde{\mathbf{n}}},m)| =\sum _{t=0}^{M}|{\mathcal {C}}_{t}^{+}|$. By the switching operations below, we will prove that ${\mathcal {L}}_r({\tilde{\mathbf{n}}},m) ={\mathcal {C}}_{0}^{+}\ne \emptyset$. It follows that

$$\begin{aligned} \frac{1}{\mathbb {P}_r({\tilde{\mathbf{n}}},m)}&=\Bigl (1-O\Bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\Bigr )\Bigr )\sum _{t=0}^{M} \frac{|{\mathcal {C}}_{t}^{+}|}{|{\mathcal {L}}_r({\tilde{\mathbf{n}}},m)|} =\Bigl (1-O\Bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\Bigr )\Bigr )\sum _{t=0}^{M} \frac{|{\mathcal {C}}_{t}^{+}|}{|{\mathcal {C}}_{0}^{+}|}. \end{aligned}$$

(2)

In order to find the ratio $|{\mathcal {C}}_{t}^{+}|/|{\mathcal {C}}_{0}^{+}|$ when $1\leqslant t\leqslant M$, we design switchings to find a relationship between the sizes of ${\mathcal {C}}_{t}^{+}$ and ${\mathcal {C}}_{t-1}^{+}$. Let $H\in {\mathcal {C}}_{t}^{+}$. A forward switching from H is used to reduce the number of clusters in H. Take any cluster consisting of two edges e and f, and remove them from H. Define $H_0$ with the the same vertex set [n] and the edge set $E(H_0)=E(H)\setminus \{e,f\}$. Choose any r-set $e_1$ from ${\mathcal {E}}_r({\tilde{\mathbf{n}}})$ such that $e_1$ does not share a link with any edge of $H_0$, and define $H'$ by setting $E(H')=E(H_0)\cup \{e_1\}$. Next, similarly choose another r-set $e_2$ from ${\mathcal {E}}_r({\tilde{\mathbf{n}}})$ such that $e_2$ does not share a link with any edge of $H'$. Add edge $e_2$ to $H'$ to produce $H''$, which is the result of the forward switching from H. Note that the two edges $e_1$ and $e_2$ may have at most one vertex in common and $H''\in {\mathcal {C}}_{t-1}^{+}$.

A reverse switching is the reverse of a forward switching. Let $H''\in {\mathcal {C}}_{t-1}^{+}$. Sequentially choose two edges $e_1$ and $e_2$ of $H''$ such that neither of them contains a link. Define $H_0$ with the same vertex set [n] and $E(H_0)=E(H'')\setminus \{e_1,e_2\}$. Take two r-sets e and f in ${\mathcal {E}}_r({\tilde{\mathbf{n}}})$ such that $|e\cap f|=2$ and neither of them share a link with any edge of $H_0$. Insert e and f into $H_0$. Call the resulting graph H. Then, $H\in {\mathcal {C}}_{t}^{+}$.

Lemma 3.2

For any fixed integer $r\geqslant 3$, let $k=k(n)$ and $m=m(n)$ be integers with $r\leqslant k\leqslant n$ and $m=o(n^{ \frac{4}{3}})$. Let t be some positive integer with $1\leqslant t\leqslant M$.

• (a) Let $H\in {\mathcal {C}}_{t}^{+}$. The number of forward switchings for H is $t\sigma _r^2({\tilde{\mathbf{n}}})\bigl (1+O\bigl ( \frac{m}{n^{2}}\bigr )\bigr )$.

• (b) Let $H''\in {\mathcal {C}}_{t-1}^{+}$. The number of reverse switchings for $H''$ is ${m-2(t-1)\atopwithdelims ()2}\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}}) \bigl (1+O\bigl ( \frac{1}{n}+ \frac{m}{n^{2}}\bigr )\bigr )$.

Proof

• (a) Let $H\in {\mathcal {C}}_{t}^{+}$. Let ${\mathcal {R}}(H)$ be the set of all forward switchings which can be applied to H. There are exactly t ways to choose a cluster; remove it from H to produce $H_0$. The number of choices for the r-set $e_1$ is at most $\sigma _r({\tilde{\mathbf{n}}})$. From this we must subtract the number of r-sets that overlap some edge of $H_0$ in two or more vertices, which is at most $\left( {\begin{array}{c}r\\ 2\end{array}}\right) (m-2)\sigma _{r-2}({\tilde{\mathbf{n}}})= O( \frac{m}{n^{2}})\sigma _r({\tilde{\mathbf{n}}})$ by Lemma 2.1 and $r=O(1)$. Thus, there are $\sigma _r({\tilde{\mathbf{n}}})(1+O( \frac{m}{n^{2}}))$ ways to choose $e_1$. Similarly, there are $\sigma _r({\tilde{\mathbf{n}}})(1+O( \frac{m}{n^{2}}))$ ways to choose $e_2$. We have $|{\mathcal {R}}(H)|=t\sigma _r^2({\tilde{\mathbf{n}}})(1+O( \frac{m}{n^{2}}))$.

• (b) Conversely, suppose that $H''\in {\mathcal {C}}_{t-1}^{+}$. Similarly, let ${\mathcal {R}}'(H'')$ be the set of all reverse switchings for $H''$. There are exactly $2\left( {\begin{array}{c}m-2(t-1)\\ 2\end{array}}\right)$ ways to delete two edges in sequence such that neither of them contains a link in $H''$. Let the resulting graph be $H_0$. There are at most $\frac{1}{2}\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})$ ways to choose two r-sets e and f in ${\mathcal {E}}_r({\tilde{\mathbf{n}}})$ such that e and f are linked edges. From this we firstly subtract the ones with $|e\cap f|\geqslant 3$, which is at most $\frac{r}{2}\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2} ({\tilde{\mathbf{n}}})\sigma _{r-3}({\tilde{\mathbf{n}}})= \sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}}) O( \frac{1}{n})$ by Lemma 2.1, since $r=O(1)$. Secondly, we subtract the cases where at least one of e, f (say e) shares a link with one of the $m-2$ edges $e'$ in $H_0$. Let $\ell _1$ be the link shared by e, f and $\ell _2$ be the link shared by $e,e'$. The number of cases for $|\ell _1\cup \ell _2|=2,3,4$ is at most $mr^2\sigma _{r-2}^2({\tilde{\mathbf{n}}})$, $mr^2 \sigma _1({\tilde{\mathbf{n}}})\sigma _{r-3}({\tilde{\mathbf{n}}})\sigma _{r-2}({\tilde{\mathbf{n}}})$ and $mr^2\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-4}({\tilde{\mathbf{n}}})\sigma _{r-2}({\tilde{\mathbf{n}}})$, respectively, where the last one is only possible if $r\geqslant 4$. By Lemma 2.1, each of these expressions is $\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})O( \frac{m}{n^{2}})$. This completes the proof.

$\square$

Corollary 3.3

With notation as above, for some $1\leqslant t\leqslant M$,

• (a) $|{\mathcal {C}}_{t}^{+}|>0$ iff $m\geqslant 2t$.

• (b) Let $t'$ be the first value of $t\leqslant M$ such that ${\mathcal {C}}_{t}^{+}=\emptyset$, or $t'=M+1$ if no such value exists. Then, as $n\rightarrow \infty$, uniformly for $1\leqslant t< t'$,

  $$\begin{aligned} \frac{|{\mathcal {C}}_{t}^{+}|}{|{\mathcal {C}}_{t-1}^{+}|}&= \frac{ \left( {\begin{array}{c}m-2(t-1)\\ 2\end{array}}\right) \sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})}{t\sigma _r^2({\tilde{\mathbf{n}}})}\Bigl (1+O\Bigl ( \frac{1}{n}+ \frac{m}{n^{2}}\Bigr )\Bigr ). \end{aligned}$$

Proof

• (a) Firstly, $m\geqslant 2t$ is necessary for $|{\mathcal {C}}_{t}^{+}|>0$. By Lemma 3.1, there is some $0\leqslant {\hat{t}}\leqslant M$ such that ${\mathcal {C}}_{{\hat{t}}}^{+}\ne \emptyset$. We can move ${\hat{t}}$ to t by a sequence of forward and reverse switchings while no greater than M. Note that since the values given in Lemma 3.2 at each step of this path are positive for any $0\leqslant t\leqslant M$, we have $|{\mathcal {C}}_{t}^{+}|>0$.

• (b) By (a), if ${\mathcal {C}}_{t}^{+}=\emptyset$, then ${\mathcal {C}}_{t+1}^{+},\ldots , {\mathcal {C}}_{M}^{+} =\emptyset$. By the definition of $t'$, if $1\leqslant t<t'$, then the left hand ratio is well defined. By Lemma 3.2 completes the proof.

$\square$

At last, we estimate the sum $\sum _{t=0}^{M} {|{\mathcal {C}}_{t}^{+}|}/{|{\mathcal {C}}_0^+|}$ by applying Lemma 2.4, which is used to count certain hypergraphs in [3, 4, 7, 8].

Lemma 3.4

For any given integer $r\geqslant 3$, let $k=k(n)$ and $m=m(n)$ be integers with $r\leqslant k\leqslant n$ and $m=o(n^{ \frac{4}{3}})$. With notation above, as $n\rightarrow \infty$,

$$\begin{aligned} \sum _{t=0}^{M} \frac{|{\mathcal {C}}_{t}^{+}|}{|{\mathcal {C}}_{0}^{+}|}&=\exp \biggl [ \frac{\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _r^2({\tilde{\mathbf{n}}})}+O\Bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\Bigr )\biggr ]. \end{aligned}$$

Proof

Let $t'$ be as defined in Corollary 3.3 (b). We know that $|{\mathcal {C}}_{0}^{+}|\ne 0$, then $t'\geqslant 1$. If $t'=1$, then we have $m<2$ from Corollary 3.3 (a), and the conclusion is obviously true. In the following, suppose $t'\geqslant 2$. Define $h_{0},\ldots ,h_{M}$ by $h_{0}=1$, $h_{t}= |{\mathcal {C}}_{t}^{+}|/|{\mathcal {C}}_{0}^{+}|$ for $1\leqslant t<t'$ and $h_{t}=0$ for $t'\leqslant t\leqslant M$. By Corollary 3.3 (b), we have for $1\leqslant t< t'$,

$$\begin{aligned} \begin{aligned} \frac{h_{t}}{h_{t-1}}&= \frac{1}{t} \left( {\begin{array}{c}m-2(t-1)\\ 2\end{array}}\right) \frac{\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})}{\sigma _r^2({\tilde{\mathbf{n}}})} \Bigl (1+O\Bigl ( \frac{1}{n}+ \frac{m}{n^2}\Bigr )\Bigr ). \end{aligned} \end{aligned}$$

(3)

For $1\leqslant t\leqslant M$, define

$$\begin{aligned} \begin{aligned} A(t)&= \frac{\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _r^2({\tilde{\mathbf{n}}})} +O\Bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\Bigr ),\\ B(t)&={\left\{ \begin{array}{ll} \frac{2(2m-2t+1)}{m(m-1)},\text {for}\ 1\leqslant t<t';\\ (t-1)^{-1},\text {otherwise}.\end{array}\right. } \end{aligned} \end{aligned}$$

(4)

Using the equations shown in (3) and (4), for $1\leqslant t< t'$, we further have

$$\begin{aligned} \frac{h_{t}}{h_{t-1}}&= \frac{A(t)}{t}\bigl (1-(t-1)B(t)\bigr ). \end{aligned}$$

Following the notation of Lemma 2.4, we also have

$$\begin{aligned} A_1,A_2= \frac{\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _r^2({\tilde{\mathbf{n}}})} +O\Bigl ( \frac{m^2}{n^3}+ \frac{m^3}{n^4}\Bigr ). \end{aligned}$$

(5)

For $1\leqslant t< t'$, we have

$$\begin{aligned} A(t)B(t)&= \frac{\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}}) (2m-2t+1)}{\sigma _r^2({\tilde{\mathbf{n}}})} +O\Bigl ( \frac{m}{n^3}+ \frac{m^2}{n^4}\Bigr ). \end{aligned}$$

Then $A(t)B(t)= O\bigl ( \frac{m}{n^2}\bigr )$ because ${\sigma _{r-2}^2({\tilde{\mathbf{n}}})}/ {\sigma _r^2({\tilde{\mathbf{n}}})}=O( {n^{-4}})$ by applying Lemma 2.1, and $\sigma _2({\tilde{\mathbf{n}}})=O(n^2)$ based on the fact that $\sigma _2({\tilde{\mathbf{n}}})$ is the number of edges of complete k-partite graphs and its maximum value occurs at the approximately equal partition. For the case $t'\leqslant t\leqslant M$ and $t'\geqslant 2$, by Corollary 3.3 (a), we have $2\leqslant m<2t$, and then $A(t)B(t)= O\bigl (\frac{m}{n^2}\bigr )$ for $t'\leqslant t\leqslant M$. In both cases, following the notation of Lemma 2.4, we have

$$\begin{aligned} C_1,C_2=O\Bigl (\frac{m}{n^2}\Bigr ). \end{aligned}$$

(6)

Then $|C|=o(1)$ for all $C\in [C_{1},C_{2}]$ when $m=o(n^{ \frac{4}{3}})$.

Let ${\hat{c}}=\frac{1}{110}$. Note that $M=\bigl \lceil \log n+ \frac{56\sigma _{r-2}^2({\tilde{\mathbf{n}}})\sigma _2({\tilde{\mathbf{n}}})m^2}{\sigma _{r}^2({\tilde{\mathbf{n}}})}\bigr \rceil$. We have $\frac{A}{M}\leqslant \frac{1+ O( 1/n+ m/n^2)}{112}$ for all $A\in [A_1,A_2]$ as shown in (5). Thus, $\max \{ \frac{A}{M},|C|\}< {\hat{c}}$ and $(2e{\hat{c}})^{M}=O( \frac{1}{n^3})$ as $n\rightarrow \infty$. Using the equations shown in (5) and (6), we have

$$\begin{aligned} A_1C_2,A_2C_1=O\Bigl ( \frac{m^2}{n^2}\cdot \frac{m}{n^2}\Bigr )= O\Bigl ( \frac{m^3}{n^4}\Bigr ) \ \text {and}\ A_2C_1^2= O\Bigl ( \frac{m^2}{n^2}\cdot \frac{m^2}{n^4}\Bigr )= O\Bigl ( \frac{m^4}{n^6}\Bigr ). \end{aligned}$$

Lemma 2.4 applies to obtain

$$\begin{aligned} \sum _{t=0}^{M} \frac{|{\mathcal {C}}_{t}^{+}|}{|{\mathcal {C}}_{0}^{+}|}&=\exp \Bigl [ \frac{\sigma _2({\tilde{\mathbf{n}}}) \sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _r^2({\tilde{\mathbf{n}}})}+ O\Bigl ( \frac{m^{2}}{n^3}+ \frac{m^{3}}{n^4}\Bigr )\Bigr ]+ O\Bigl ( \frac{1}{n^3}\Bigr )\\&=\exp \Bigl [ \frac{\sigma _2({\tilde{\mathbf{n}}}) \sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _r^2({\tilde{\mathbf{n}}})}+ O\Bigl ( \frac{m^{2}}{n^3}+ \frac{m^{3}}{n^4}\Bigr )\Bigr ] \end{aligned}$$

when $m=o(n^{ \frac{4}{3}})$. $\square$

Proof of Theorem 1.1

By applying Lemma 3.4, using the equations shown in (1) and (2), we have

$$\begin{aligned} |{\mathcal {L}}_r({\tilde{\mathbf{n}}},m)|&=\left( {\begin{array}{c}\sigma _{r}({\tilde{\mathbf{n}}})\\ m\end{array}}\right) \exp \Bigl [ -\frac{\sigma _2({\tilde{\mathbf{n}}})\sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _r^2({\tilde{\mathbf{n}}})}+ O\Bigl ( \frac{m^{2}}{n^3}+ \frac{m^{3}}{n^4}\Bigr )\Bigr ]\\&= \frac{\sigma _{r}^m({\tilde{\mathbf{n}}})}{m!} \exp \Bigl [ -\frac{\sigma _2({\tilde{\mathbf{n}}}) \sigma _{r-2}^2({\tilde{\mathbf{n}}})[m]_2}{2\sigma _r^2({\tilde{\mathbf{n}}})}+ O\Bigl ( \frac{m^{2}}{n^3}+ \frac{m^{3}}{n^4}\Bigr )\Bigr ], \end{aligned}$$

since

$$\begin{aligned} \left( {\begin{array}{c}\sigma _{r}({\tilde{\mathbf{n}}})\\ m\end{array}}\right) = \frac{\sigma _{r}^m({\tilde{\mathbf{n}}})}{m!} \exp \Bigl [O\Bigl ( \frac{m^{2}}{\sigma _{r}({\tilde{\mathbf{n}}})}\Bigr )\Bigr ] = \frac{\sigma _{r}^m({\tilde{\mathbf{n}}})}{m!}\exp \Bigl [O\Bigl ( \frac{m^{2}}{n^3}\Bigr )\Bigr ] \end{aligned}$$

because $\sigma _{r}({\tilde{\mathbf{n}}})\geqslant \left( {\begin{array}{c}k\\ r\end{array}}\right) c^r ( \frac{n}{k})^r$ and $r\geqslant 3$.

Proof of Corollary 1.2

If $k=n$, then $\sigma _{2}({\tilde{\mathbf{n}}})= N_2$, $\sigma _{r-2}({\tilde{\mathbf{n}}})= N_{r-2}$, $\sigma _{r}({\tilde{\mathbf{n}}})= N_r$ and k-partite r-graphs are r-graphs. By applying Theorem 1.1, it follows that

$$\begin{aligned} |{\mathcal {L}}_r(n,m)| ={ \frac{ N_r^m}{m!}} \exp \Bigl [- \frac{[r]_2^2[m]_2}{4n^2}+O\Bigl ( \frac{m^2}{n^{3}}+ \frac{m^3}{n^{4}}\Bigr )\Bigr ] \end{aligned}$$

when $m=o(n^{ \frac{4}{3}})$. $\square$

Remark 3.5

The formula in Corollary 1.2 coincides with the uniform case in [7] and is a subcase in [8]. Compared with the enumeration formula of $|{\mathcal {L}}_r(n,m)|$ in [8],

$$\begin{aligned} |{\mathcal {L}}_r(n,m)|&={ \frac{ N_r^m}{m!}}\exp \biggl [- \frac{[r]_2^2[m]_2}{4n^2}- \frac{[r]_2^3(3r^2-15r+20)m^3}{24n^4}+O\Bigl ( \frac{m^2}{n^3}\Bigr )\biggr ], \end{aligned}$$

the term $\frac{[r]_2^3(3r^2-15r+20)m^3}{24n^4}=O\bigl (\frac{m^3}{n^4}\bigr )$ is under our conditions. It will take new ideas to handle larger m in ${\mathcal {L}}_r({\tilde{\mathbf{n}}},m)$ and they will be more complicated than those in [7, 8]. We leave these problems for future work.