# Matchings on Random Regular Hypergraphs

Zhongyang Li  (ZL) Department of Mathematics, University of Connecticut,
Storrs, Connecticut 06269-3009, USA<EMAIL_ADDRESS>http://www.math.uconn.edu/~zhongyang/

###### Abstract.

We prove the convergence in probability of free energy for matchings on random
regular, uniform hypergraphs and explicitly compute the limit. We also obtain
a region on parameters where replica symmetry holds.

##  1\. Introduction

Counting the number of matchings on a graph has been an interesting problem to
scientists dating back to at least 1960s (see [9, 16, 17]). Unlike perfect
matchings, the number of which on a graph can be computed explicitly by a
determinant formula (see [19, 24, 21]), counting the number of matchings (or
monomer dimers) on a graph is complicated in general (see [18]); and
algorithms are designed for that purpose ([20, 10]).

In this paper, we study the free energy of matchings on random, uniform
hypergraphs. Let $d,l$ be positive integers such that $l\geq 2$ and $d\geq 2$.
A hypergraph $G=(V,E,H)$ consists of a collection $H$ of labeled half-edges, a
set $E$ of hyperedges such that each hyperedge $e\in E$ consists of $l$
distinct half-edges, and a set $V$ of vertices in which each vertex is
represented by $d$ distinct half-edges incident to it. Here each half edge is
part of a unique hyperedge and is incident to a unique vertex. However, it is
allowed that two distinct half edges are incident to the same vertex and part
of the same hyperedge. We call such a hypergraph a $(d,l)$-regular hypergraph.

A subset $M\subset E$ is a matching of $G=(V,E,H)$ if for any two hyperedges
$e_{1},e_{2}\in M$, let $f_{1},\ldots,f_{l}$ be half edges in $e_{1}$ and
$g_{1},\ldots,g_{l}$ be half edges in $e_{2}$, then no two half edges in
$\\{f_{1},\ldots,f_{l},g_{1},\ldots,g_{l}\\}$ share a vertex.

Let $m$ be a positive integer, and assume that $lm$ is an integer multiple of
$d$. We may consider a $(d,l)$-regular hypergraph with hyperedge set
$[m]=\\{1,2,\ldots,m\\}$ as a division on the set $[lm]$ of labeled half-edges
into disjoint size-$d$ subsets, where half-edge $i$ is part of the edge
$\lceil\frac{i}{l}\rceil$, and each size-$d$ subset of half-edges represent a
vertex. Then the total number of $(d,l)$-regular hypergraphs with hyperedge
set $[m]$ is

(1.1)
$\displaystyle\prod_{j=0}^{\frac{lm}{d}-1}\prod_{k=1}^{d-1}(k+jd)=\frac{(lm)!}{d^{\frac{lm}{d}}\left(\frac{lm}{d}\right)!}$

When $l,d$ are fixed and let $m\rightarrow\infty$, by Stirling’s formula we
obtain

$\displaystyle\frac{(lm)!}{d^{\frac{lm}{d}}\left(\frac{lm}{d}\right)!}=e^{O\left(\frac{1}{m}\right)}\sqrt{d}\left(\frac{lm}{e}\right)^{\frac{lm(d-1)}{d}}$

Let $\Omega_{m,d,l}$ consists of all the $(d,l)$-regular hypergraphs with $m$
hyperedges. A random $(d,l)$-regular graph
$\mathcal{G}_{m,d,l}\in\Omega_{m,d,l}$ is a random graph uniformly distributed
in $\Omega_{m,d,l}$.

We shall apply the first and second moments method; and find a region for
parameters when the exponential growth rate of the second moment is twice of
that of the first moment. Similar approach was used to determine the
asymptotic independence number for the dense Erdös-Rényi random graph ([14]);
and to show the existence and non-existence of perfect matchings on
hypergraphs ([5]). The major difference between a matching problem and a
perfect matching problem lies in the fact that in the matching problem, we
need to find the global maximizer for a function of two real variables, in
contrast to the case that in a perfect matching problem, the global maximizer
of a single variable function is studied. When the second moment is
approximately the square of the first moment, we use a generalized version of
the subgraph conditioning technique to show the convergence in probability of
the free energy. The subgraph conditioning method was first used to study
Hamiltonian cycles on a random graph (see [23]); the major difference here is
that we prove that the asymptotic Poisson distribution of the number of cycles
on a random graph conditional on the existence of a specific matching.

Note that when $l=2$, the model is the same as monomer dimers on a random
graph, whose free energy was computed in [1] and the convergence of the
density of maximal matching was proved in [8, 4] using the technique of weak
convergence (see [2, 6]). When $d=2$, the model is the same as the independent
set model on a random graph, of which the fluctuations of the maximum were
studied in [7] when $l$ is sufficiently large. Free energies of vertex models
on a graph with more general constraints were computed in [22, 13, 11, 12].

Here are the main results of the paper.

######  Theorem 1.1.

  1. (1)

Let $\beta_{*}$ be the unique root of

(1.2) $\displaystyle(1-d\beta)^{l}=\beta(1-\beta)^{l-1}$

in $\left(0,\frac{1}{d}\right)$. Let $Z$ be the total number of matchings on a
random $d,l$-regular graph $\mathcal{G}_{m,d,l}$. Then when $m$ is
sufficiently large

$\displaystyle\lim_{m\rightarrow\infty}e^{-m\Phi_{d}(\beta_{*})}\mathbb{E}Z=\frac{\sqrt{1-\beta_{*}}}{\sqrt{1+(ld-
d-l)\beta_{*}}}$

  2. (2)

Let

(1.3) $\displaystyle L_{1}:$ $\displaystyle=$
$\displaystyle\min\left\\{\frac{1}{dl-
d-l+2},\frac{1}{\sqrt{(d-1)(l-1)}+1}\right\\}$ (1.4) $\displaystyle L_{2}:$
$\displaystyle=$
$\displaystyle\min\left\\{\frac{1}{d}\left(1-\sqrt{\frac{d-1}{d^{\frac{l}{l-1}}-1}}\right),\frac{dl+l^{2}-2l-d+1}{2dl^{2}-dl},\frac{1}{\sqrt{(d-1)(l-1)}+1}\right\\}$

and

(1.5) $\displaystyle\Phi_{d,l}(\beta)$ $\displaystyle=$
$\displaystyle-\beta\ln\beta+(l-1)(1-\beta)\ln(1-\beta)-\frac{l}{d}\left(1-d\beta\right)\ln\left(1-d\beta\right)$

Assume $l\geq 2$, $d\geq 2$ satisfy one of the following conditions

    1. (a)

$l=2$ and $\beta\in\left(0,\frac{1}{d}\right)$; or

    2. (b)

$d\geq 3$, $l\geq 2$ such that $\Phi^{\prime}_{d,l}(L_{1})\leq 0$.

Then as $m\rightarrow\infty$,

$\displaystyle\frac{1}{m}\log Z\longrightarrow\Phi_{d,l}(\beta_{*})$

in probability.

  3. (3)

Let

(1.6) $\displaystyle Z(x):=\sum_{k=0}^{\frac{m}{d}}Z_{k}x^{k},$

where $Z_{k}$ is the total number of matchings on $\mathcal{G}_{m,d,l}$ with
exactly $k$ present hyperedges. Assume $l\geq 2$, $d\geq 2$ satisfy one of the
following conditions:

    1. (a)

$l=2$, and $\beta\in\left(0,\frac{1}{d}\right)$; or

    2. (b)

$d\geq 3$, $l\geq 2$, such that $\Phi^{\prime}_{d,l}(L_{1})+\ln(x)\leq 0$; or

    3. (c)

$d\geq 3$, $l\geq 2$, such that $\Phi^{\prime}_{d,l}(L_{2})+\ln(x)\leq 0$.

Then as $m\rightarrow\infty$

$\displaystyle\frac{1}{m}\log
Z(x)\longrightarrow\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x).$

in probability.

Theorem 1.1(2) has the following applications.

######  Example 1.2.

It is straight forward to check that when

$\displaystyle(d,l)\in\\{(2,3),(2,4),(2,5),(3,3),(4,3)\\},$

when have $\Phi^{\prime}_{d,l}(L_{1})<0$. Then the free energy of matchings on
$\mathcal{G}_{m,d,l}$ converges in probability to $\Phi_{d,l}(\beta_{*})$ as
$m\rightarrow\infty$.

The organization of the paper is as follows. In Section 2, we compute the
first moment of the total number of matchings of a given density, and the
first moment of the totoal number of all matchings on $\mathcal{G}_{m,d,l}$.
In section 3, we compute the second moment of matchings with a given density
and find explicit conditions under which the second moment and the square of
the first moment have the same exponential growth rate. In section 4, we show
that conditional on a matching , the distributions of the number of cycles of
different lengths on $\mathcal{G}_{m,d,l}$ converge to independent Poisson
random variables as $m\rightarrow\infty$. In Section 5, we show the
convergence in probability of the free energy to an explicit limit. In Section
6, we show the convergence in probability of the weighted energy to an
explicit limit when each hyperedge in the matching is given a sufficiently
small weight $x>0$ and prove Theorem 1.1(3b). In Seciton 7, we prove Theorem
1.1(3c). In Section 8, we discuss the implications of our results on maximal
matchings.

##  2\. First Moment

Let $\beta\in(0,1)$. Let $Z_{m\beta}$ be the total number of matchings
consisting of $m\beta$ hyperedges on a random $(d,l)$-regular graph
$\mathcal{G}_{m,d,l}$. In this section, we compute the first moment of
$\mathbb{E}Z_{m\beta}$ and the first moment of $Z$, the totoal number of
matchings on $\mathcal{G}_{m,d,l}$.

Note that if $\beta>\frac{1}{d}$ then $Z_{m\beta}=0$. Now assume

(2.1) $\displaystyle\beta\in\left(0,\frac{1}{d}\right).$

Then

$\displaystyle\mathbb{E}Z_{m\beta}$ $\displaystyle=$ $\displaystyle{m\choose
m\beta}\prod_{j=0}^{d-2}\prod_{i=0}^{lm\beta-1}\frac{lm(1-\beta)-(d-1)i-j}{lm-1-di-j}$
$\displaystyle=$
$\displaystyle\frac{m!}{(m\beta)!(m(1-\beta))!}\frac{(lm(1-\beta))!}{(lm(1-d\beta))!}\frac{(lm(1-d\beta))!}{(lm)!}\frac{d^{lm\beta}\left(\frac{lm}{d}\right)!}{\left(\frac{lm}{d}(1-d\beta)\right)!}$

Fix $d,\beta,l$, and let $m\rightarrow\infty$, by Stirling’s formula we obtain

(2.3) $\displaystyle\mathbb{E}Z_{m\beta}\asymp
m^{-\frac{1}{2}}e^{m\Phi_{d,l}(\beta)}$

where $\Phi_{d,l}$ is defined by (1.5).

Hence

(2.4)
$\displaystyle\Phi_{d,l}^{\prime}(\beta)=-\ln\beta-(l-1)\ln(1-\beta)+l\ln\left(1-d\beta\right)$
(2.5)
$\displaystyle\Phi_{d,l}^{\prime\prime}(\beta)=-\frac{1}{\beta}-\frac{ld-d\beta-(l-1)}{(1-\beta)(1-d\beta)}<0;\qquad\forall\beta\in\left(0,\frac{1}{d}\right).$

Then we have

######  Lemma 2.1.

  1. (1)

$\max_{\beta\in\left(0,\frac{1}{d}\right)}\Phi_{d,l}(\beta)=\Phi_{d,l}(\beta_{*})$,
where $\beta_{*}$ is given by (1.2).

  2. (2)

If

$\displaystyle\frac{(l-1)(d-1)}{d}\ln\left(\frac{d-1}{d}\right)-\frac{1}{d}\ln\left(\frac{1}{d}\right):=f_{l}\left(\frac{1}{d}\right)\geq
0$

$\Phi_{d,l}(\beta)>0$ for all $\beta\in\left(0,\frac{1}{d}\right)$.

  3. (3)

If $f\left(\frac{1}{d}\right)<0$, let $\beta_{0}$ be the unique number in
$\left(\beta_{*},\frac{1}{d}\right)$ such that

$\displaystyle\Phi_{d,l}(\beta_{0})=0.$

Then

    1. (a)

If $\beta\in\left(0,\beta_{0}\right)$, then $\Phi_{d,l}(\beta)>0$.

    2. (b)

If $\beta\in\left(\beta_{0},\frac{1}{d}\right)$, then $\Phi_{d,l}(\beta)<0$.

###### Proof.

From (2.4) we obtain

$\displaystyle\lim_{\beta\rightarrow
0+}\Phi_{d,l}^{\prime}(\beta)=+\infty;\qquad\lim_{\beta\rightarrow\frac{1}{d}-}\Phi_{d,l}^{\prime}(\beta)=-\infty.$

By (2.5), the equation $\Phi_{d,l}^{\prime}(\beta)=0$ has exactly one root in
$\beta_{*}\in\left(0,\frac{1}{d}\right)$ satisfying(1.2).

From (2.5) we see $\Phi_{d,l}^{\prime}$ is monotone decreasing in
$\left(0,\frac{1}{d}\right)$, therefore

  * •

when $\beta\in\left(0,\beta_{*}\right)$, $\Phi^{\prime}_{d,l}>0$, and
$\Phi_{d,l}(\beta)$ is monotone increasing;

  * •

when $\beta\in\left(\beta_{*},\frac{1}{d}\right)$, $\Phi^{\prime}_{d,l}<0$,
and $\Phi_{d,l}(\beta)$ is monotone decreasing.

Then Part (1) of the lemma follows. Moreover,

$\displaystyle\inf_{\beta\in\left(0,\frac{1}{d}\right)}\Phi_{d,l}(\beta)=\min\left\\{\lim_{\beta\rightarrow
0+}\Phi_{d,l}(\beta),\
\lim_{\beta\rightarrow\frac{1}{d}-}\Phi_{d,l}(\beta)\right\\}$

By (1.5) we obtain

$\displaystyle\lim_{\beta\rightarrow 0+}\Phi_{d,l}(\beta)=0;$

and

$\displaystyle\lim_{\beta\rightarrow\frac{1}{d}-}\Phi_{d,l}(\beta)=\frac{(l-1)(d-1)}{d}\ln\left(\frac{d-1}{d}\right)-\frac{1}{d}\ln\left(\frac{1}{d}\right):=f\left(\frac{1}{d}\right)$

Then it is straightforward to check Part (2) and (3) of the lemma. ∎

######  Lemma 2.2.

Let $n\in{\mathbb{N}}$. Then

(2.6) $\displaystyle\sqrt{2\pi
n}\left(\frac{n}{e}\right)^{n}e^{\frac{1}{12n+1}}\leq n!\leq\sqrt{2\pi
n}\left(\frac{n}{e}\right)^{n}e^{\frac{1}{12n}}$

Moreover,

$\displaystyle{\displaystyle{\sqrt{2\pi}}\ n^{n+{\frac{1}{2}}}e^{-n}\leq
n!\leq e\ n^{n+{\frac{1}{2}}}e^{-n}}$

###### Proof.

See Exercise 3.1.9 of [15]. ∎

######  Lemma 2.3.

Let $\beta\in\left(0,\frac{1}{d}\right)$. Then

$\displaystyle\lim_{m\rightarrow\infty}\sqrt{m}e^{-m\Phi_{d,l}(\beta)}Z_{m\beta}=\frac{1}{\sqrt{2\pi\beta(1-d\beta)}}$

The convergence is uniform in any compact subset of
$\left(0,\frac{1}{d}\right)$.

###### Proof.

Let $h\in[1,\frac{m}{d}-1]$ be a positive integer. By (2) and (2.6), we obtain

(2.7)
$\displaystyle\frac{B(m,h)e^{m\Phi_{d,l}\left(\frac{h}{m}\right)}}{\sqrt{2m\pi\frac{h}{m}\left(1-\frac{dh}{m}\right)}}\leq\mathbb{E}Z_{h}\leq\frac{A(m,h)e^{m\Phi_{d,l}\left(\frac{h}{m}\right)}}{\sqrt{2m\pi\frac{h}{m}\left(1-\frac{dh}{m}\right)}};$

where

$\displaystyle A(m,h)$ $\displaystyle=$ $\displaystyle
e^{\frac{1}{12m}+\frac{1}{12l(m-h)}-\frac{1}{12h+1}-\frac{1}{12(m-h)+1}-\frac{1}{12ml+1}+\frac{d}{12ml}-\frac{d}{12l(m-hd)+d}}$
$\displaystyle B(m,h)$ $\displaystyle=$ $\displaystyle
e^{\frac{1}{12m+1}+\frac{1}{12l(m-h)+1}-\frac{1}{12h}-\frac{1}{12(m-h)}-\frac{1}{12lm}+\frac{d}{12lm+d}-\frac{d}{12l(m-hd)}}$

Then the lemma follows. ∎

Proof of Theorem 1.1(1). Note that

$\displaystyle Z_{0}=1$ $\displaystyle
Z_{\frac{m}{d}}=\frac{m!}{\left(\frac{m}{d}\right)!\left(\frac{m(d-1)}{d}\right)!}\frac{\left(\frac{lm(d-1)}{d}\right)!}{(lm)!}d^{2m\beta}\left(\frac{lm}{d}\right)!$

We have

$\displaystyle
B\left(m,\frac{m}{d}\right)\sqrt{l}e^{m\Phi_{d,l}\left(\frac{1}{d}\right)}\leq\mathbb{E}Z_{\frac{m}{d}}\leq
A\left(m,\frac{m}{d}\right)\sqrt{l}e^{m\Phi_{d,l}\left(\frac{1}{d}\right)};$

where

$\displaystyle A\left(m,\frac{m}{d}\right)$ $\displaystyle=$ $\displaystyle
e^{\frac{1}{12m}+\frac{d}{12lm(d-1)}-\frac{d}{12m+d}-\frac{d}{12m(d-1)+d}-\frac{1}{12lm+1}+\frac{d}{12lm}}$
$\displaystyle B\left(m,\frac{m}{d}\right)$ $\displaystyle=$ $\displaystyle
e^{\frac{1}{12m+1}+\frac{d}{12lm(d-1)+d}-\frac{d}{12m}-\frac{d}{12m(d-1)}-\frac{1}{12lm}+\frac{d}{12lm+d}}$

Then by (2.7)

(2.8) $\displaystyle\mathbb{E}Z$ $\displaystyle=$
$\displaystyle\sum_{h=0}^{\frac{m}{d}}\mathbb{E}Z_{h}=e^{m\Phi_{d,l}(\beta_{*})}\left(\sum_{h=1}^{\frac{m}{d}-1}\frac{e^{m\left[\Phi_{d,l}\left(\frac{h}{m}\right)-\Phi_{d,l}(\beta_{*})\right]}}{\sqrt{2h\pi\left(1-\frac{dh}{m}\right)}}\right)\left(1+O\left(\frac{1}{m}\right)\right)$

Let $K\geq 1$ be a positive integer. We shall divide the sum over $h$ in the
right hand side of (2.8) into two parts

  1. (1)

Part I is the sum over $h$ when $\frac{h}{m}$ is in a $\frac{K}{\sqrt{m}}$
neighborhood of $\beta_{*}$.

  2. (2)

Part II is the sum over $h$ when $\frac{h}{m}$ is outside the
$\frac{K}{\sqrt{m}}$ neighborhood of $\beta_{*}$.

More precisely, let

$\displaystyle\mathcal{Q}:=\left\\{h\in{\mathbb{N}}:1\leq
h\leq\frac{m}{d}-1,\left|\frac{h}{m}-\beta_{*}\right|\leq\frac{K}{\sqrt{m}}\right\\};$

then

$\displaystyle\sum_{h=1}^{\frac{m}{d}-1}\frac{e^{m\left[\Phi_{d,l}\left(\frac{h}{m}\right)-\Phi_{d,l}(\beta_{*})\right]}}{\sqrt{2h\pi\left(1-\frac{dh}{m}\right)}}=\mathrm{I}+\mathrm{II}$

where

$\displaystyle\mathrm{I}=\sum_{h\in\mathcal{Q}}\frac{e^{m\left[\Phi_{d,l}\left(\frac{h}{m}\right)-\Phi_{d,l}(\beta_{*})\right]}}{\sqrt{2h\pi\left(1-\frac{dh}{m}\right)}};\qquad\mathrm{II}=\sum_{1\leq
h\leq\frac{m}{d}-1,h\notin\mathcal{Q}}\frac{e^{m\left[\Phi_{d,l}\left(\frac{h}{m}\right)-\Phi_{d,l}(\beta_{*})\right]}}{\sqrt{2h\pi\left(1-\frac{dh}{m}\right)}}.$

Taylor expansion of $\Phi_{d,l}(\cdot)$ gives us

$\displaystyle\Phi_{d,l}\left(\frac{h}{m}\right)-\Phi_{d,l}(\beta_{*})=\frac{\Phi_{d,l}^{\prime\prime}(\beta_{*})}{2}\left(\frac{h}{m}-\beta_{*}\right)^{2}+O\left(\frac{h}{m}-\beta_{*}\right)^{3}$

Hence we have

$\displaystyle\mathrm{II}\leq
e^{-\frac{K^{2}}{2}\left(\frac{1}{\beta_{*}}+\frac{ld-d\beta_{*}-(l-1)}{(1-\beta_{*})(1-d\beta_{*})}\right)}\cdot\mathrm{convergent\
geometric\ series}\rightarrow 0,$

as $K\rightarrow\infty$. Moreover

$\displaystyle\lim_{K\rightarrow\infty}\lim_{m\rightarrow\infty}I$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2\pi\beta_{*}(1-d\beta_{*})}}\int_{-\infty}^{\infty}e^{-\frac{\left(\frac{1}{\beta_{*}}+\frac{ld-d\beta_{*}-(l-1)}{(1-\beta_{*})(1-d\beta_{*})}\right)x^{2}}{2}}dx$
$\displaystyle=$ $\displaystyle\sqrt{\frac{1-\beta_{*}}{1+(ld-
d-l)\beta_{*}}}.$

Then the lemma follows. $\hfill\Box$

##  3\. Second Moment

In this section, we compute the second moment of $Z_{m\beta}$ and find
explicit conditions under which $\mathbb{E}Z_{m\beta}^{2}$ and
$(\mathbb{E}Z_{m\beta})^{2}$ have the same exponential growth rate.

We can also compute the second moment of $Z_{m\beta}$ as follows

  1. (1)

A double matching configuration is the union of two matchings on the same
graph. Consider $Z_{m\beta}^{2}$ as the partition function of double matching
configurations on a random graph, in which each matching consists of exactly
$m\beta$ edges.

  2. (2)

In each double matching configuration $M_{1}\cup M_{2}$ on a random graph of
$m$ edges such that each matching consists of exactly $m\beta$ edges; all the
hyperedges in $[m]$ are divided into 4 types by the configuration

    1. (a)

Type (a) hyperedges are in $M_{1}\cap M_{2}$; assume there are $s$ Type (a)
edges, where $0\leq s\leq m\beta$. The $s$ Type (a) edges splits into $ls$
half edges, each one of which can not share a vertex with any half edge in
$M_{1}\cup M_{2}$. A half edge is of Type (a) if and only if it is part of a
Type (a) hyperedge. The total number of Type (a) half-edges is $ls$.

    2. (b)

Type (b) hyperedges are in $M_{1}\cap M_{2}^{c}$; the total number of Type (b)
edges is $m\beta-s$. The $(m\beta-s)$ Type (b) edges splits into $l(m\beta-s)$
half edges, each one of which cannot share a vertex with any half edge in
$M_{1}$. A half edge is of Type (b) if and only if it is part of a Type (b)
edge. The total number of Type (b) half edges is $lm\beta-ls$. Depending on
whether they share a vertex with a half edge in $M_{2}\cap M_{1}^{c}$, Type
(b) half edges can be further divided into 2 sub-types:

      1. (i)

Each Type (bi) half edge does not share a vertex with any edge in $M_{1}\cup
M_{2}$. The total number of Type (bi) half edges is $lm\beta-ls-t$.

      2. (ii)

Each Type (bii) half edge shares a vertex with exactly one half-edge in
$M_{2}\cap M_{1}^{c}$. The total number of Type (bii) half edges is $t$..

    3. (c)

Type (c) hyperedges are in $M_{1}^{c}\cap M_{2}$; the total number of Type (c)
edges is $m\beta-s$. The $(m\beta-s)$ Type (c) edges splits into $l(m\beta-s)$
half edges, each one of which cannot share a vertex with any half edge in
$M_{2}$. A half edge is of Type (c) if and only if it is part of a Type (c)
edge. The total number of Type (c) half edges is $lm\beta-ls$. Depending on
whether they share a vertex with a half edge in $M_{1}\cap M_{2}^{c}$, Type
(c) half edges can be further divided into 2 sub-types:

      1. (i)

Each Type (ci) half edge does not share a vertex with any edge in $M_{1}\cup
M_{2}$. The total number of Type (ci) half edges is $lm\beta-ls-t$.

      2. (ii)

Each Type (cii) half edge shares a vertex with exactly one half-edge in
$M_{2}\cap M_{1}^{c}$. The total number of Type (cii) half edges is $t$.

    4. (d)

Type (d) edges are in $M_{1}^{c}\cap M_{2}^{c}$; the total number of Type (d)
edges is $m-2m\beta+s$. A half edge is of Type (d) if and only if it is part
of a Type (d) edge. The total number of Type (d) half-edges is
$l(m-2m\beta+s)$.

Let

(3.1) $\displaystyle\rho:=\frac{s}{m};\qquad\theta:=\frac{t}{m}.$

It is straight forward to check the following lemma

######  Lemma 3.1.

(3.2) $\displaystyle\rho\in[0,\beta];\qquad\theta\in[0,l\beta-l\rho].$

######  Lemma 3.2.

(3.3) $\displaystyle\left(2\beta-\rho-\frac{\theta}{l}\right)d\leq 1.$

###### Proof.

It suffices to show that

$\displaystyle(lm(2\beta-\rho)-\theta m)d\leq lm$

Note that $lm$ is the total number of half edges in the graph
$\mathcal{G}_{m,d,l}$; $lm(2\beta-\rho)-2\theta m$ is the total number of half
edges of Type (a) (bi) and (ci); any two of these half edges cannot share a
vertex; hence the total number of half edges sharing a vertex with these half
edges is

(3.4) $\displaystyle(lm(2\beta-\rho)-2\theta m)d$

The total number of Type (bii) and (cii) half edges is $2t$; these half edges
are incident to exactly $t$ vertices, and the total number of half edges
incident to these $t$ vertices is

(3.5) $\displaystyle\theta md$

There are no common half edges in (3.4) and (3.5), therefore their sum is at
most $ml$-the total number of half edges in the graph $\mathcal{G}_{m,d,l}$.
Then the lemma follows. ∎

By (3.3), we obtain

$\displaystyle t\geq\max\left\\{0,2lm\beta-ls-\frac{lm}{d}\right\\}.$

Let $K_{m,\beta,s,t}$ be the total number of possible half edge assignments
for the first $(2lm\beta-ls-t)$ vertices. Then

$\displaystyle K_{m,\beta,s,t}$ $\displaystyle=$
$\displaystyle\prod_{i=0}^{2lm\beta-ls-t-1}\prod_{j=0}^{d-2}(lm-1-di-j)$
$\displaystyle=$ $\displaystyle\frac{(lm)!}{(lm-d(2lm\beta-
ls-t))!}\frac{\left(\frac{lm}{d}-2lm\beta+ls+t\right)!}{d^{2lm\beta-
ls-t}\left(\frac{lm}{d}\right)!}$ (3.6)
$\displaystyle\mathbb{E}Z_{m\beta}^{2}$ $\displaystyle=$
$\displaystyle\sum_{s=0}^{m\beta}{m\choose s}{m-s\choose
m\beta-s}{m-m\beta\choose
m\beta-s}\prod_{j=0}^{d-2}\left[\prod_{i=0}^{ls-1}l(m-2m\beta+s)-(d-1)i-j\right]$
$\displaystyle\left\\{\sum_{t=\max\left\\{0,2lm\beta-
ls-\frac{lm}{d}\right\\}}^{lm\beta-ls}{lm\beta-ls\choose
t}^{2}(d-1)^{t}t!\right.$ $\displaystyle\left[\prod_{k=0}^{lm\beta-
ls-t-1}lm(1-2\beta)+ls-(d-1)(2s+k)-j\right]$
$\displaystyle\left.\times\left[\prod_{h=0}^{lm\beta-
ls-t-1}lm(1-2\beta)+ls-(d-1)(lm\beta-t+h)-j\right]\right\\}$
$\displaystyle\times\left\\{\prod_{w=0}^{t-1}\prod_{r=0}^{d-3}2m-d(2lm\beta-
ls-2t+w)-(2t-2w)-r\right\\}\frac{1}{K_{m,\beta,s,t}}$ $\displaystyle=$
$\displaystyle\sum_{s=0}^{m\beta}\sum_{t=\max\left\\{0,2lm\beta-
ls-\frac{lm}{d}\right\\}}^{lm\beta-ls}F_{\beta}(s,t).$

where

$\displaystyle F_{\beta}(s,t)$ $\displaystyle=$
$\displaystyle\frac{m!(d-1)^{t}}{s!(m\beta-s)!(m\beta-s)!(m-2m\beta+s)!}\frac{[(lm\beta-
ls)!]^{2}}{t![(lm\beta-ls-t)!]^{2}}$
$\displaystyle\frac{[l(m-2m\beta+s)]!}{(lm)!}\frac{d^{2lm\beta-
ls-t}\left(\frac{lm}{d}\right)!}{\left(\frac{lm}{d}-2lm\beta+ls+t\right)!}$

Now we assume

(3.8) $\displaystyle\rho\in(0,\beta);$ (3.9)
$\displaystyle\theta\in(0,l\beta-l\rho).$

When $m\rightarrow\infty$, by Stirling’s formula we obtain

$\displaystyle F_{\beta}(\rho m,\theta m)\asymp
m^{-2}e^{m\Psi_{d,l}(\beta,\rho,\theta)}$

where

$\displaystyle\Psi_{d,l}(\beta,\rho,\theta)$ $\displaystyle=$
$\displaystyle-\rho\ln\rho-\theta\ln\frac{\theta}{l}+(l-1)(1-2\beta+\rho)\ln(1-2\beta+\rho)+\theta\ln(d-1)$
$\displaystyle+2(l-1)(\beta-\rho)\ln(\beta-\rho)-2l\left(\beta-\rho-\frac{\theta}{l}\right)\ln\left(\beta-\rho-\frac{\theta}{l}\right)$
$\displaystyle-\frac{l}{d}\left(1-2\beta d+\rho
d+\frac{\theta}{l}d\right)\ln\left(1-2\beta d+\rho d+\frac{\theta}{l}d\right)$

Then we have for all $\beta\in\left(0,\frac{1}{d}\right)$

$\displaystyle\frac{\partial\Psi_{d,l}(\beta,\rho,\theta)}{\partial\rho}$
$\displaystyle=$
$\displaystyle-\ln\rho+(l-1)\ln(1-2\beta+\rho)-2(l-1)\ln(\beta-\rho)$
$\displaystyle+2l\ln\left(\beta-\rho-\frac{\theta}{l}\right)-l\ln\left(1-2\beta
d+\rho d+\frac{\theta d}{l}\right)$
$\displaystyle\frac{\partial\Psi_{d,l}(\beta,\rho,\theta)}{\partial\theta}$
$\displaystyle=$
$\displaystyle-\ln\frac{\theta}{l}+2\ln\left(\beta-\rho-\frac{\theta}{l}\right)-\ln\left(1-2\beta
d+\rho d+\frac{\theta d}{l}\right)+\ln(d-1)$

and

(3.11)
$\displaystyle\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\rho^{2}}$
$\displaystyle=$
$\displaystyle-\frac{1}{\rho}+\frac{l-1}{1-2\beta+\rho}+\frac{2(l-1)}{\beta-\rho}-\frac{2l}{\beta-\rho-\frac{\theta}{l}}-\frac{ld}{1-2\beta
d+\rho d+\frac{\theta d}{l}}$ (3.12)
$\displaystyle\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\theta^{2}}$
$\displaystyle=$
$\displaystyle-\frac{1}{\theta}-\frac{\frac{2}{l}}{\beta-\rho-\frac{\theta}{l}}-\frac{\frac{d}{l}}{1-2\beta
d+\rho d+\frac{\theta d}{l}}<0.$
$\displaystyle\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\theta\partial\rho}$
$\displaystyle=$
$\displaystyle-\frac{2}{\beta-\rho-\frac{\theta}{l}}-\frac{d}{1-2\beta d+\rho
d+\frac{\theta d}{l}}$

Now we solve the following system of equations

(3.13)
$\displaystyle\begin{cases}\frac{\partial\Psi_{d,l}(\beta,\rho,\theta)}{\partial\rho}=0;\\\
\frac{\partial\Psi_{d,l}(\beta,\rho,\theta)}{\partial\theta}=0.\end{cases}$

and obtain

(3.14)
$\displaystyle(d-1)\left(\beta-\rho-\frac{\theta}{l}\right)^{2}=\frac{\theta}{l}\left(1-2\beta
d+\rho d+\frac{\theta d}{l}\right).$ (3.15)
$\displaystyle\rho(d-1)^{l}(\beta-\rho)^{2(l-1)}=\left(\frac{\theta}{l}\right)^{l}(1-2\beta+\rho)^{l-1}$

It is straightforward to check that

(3.16) $\displaystyle\rho=\beta^{2};\qquad\theta=l(d-1)\beta^{2}.$

is a pair of solutions for (3.14) and (3.15).

######  Lemma 3.3.

Assume (2.1),(3.8) (3.9) hold. Assume $d\geq 2$. For each
$\beta\in\left(0,\frac{1}{d}\right)$, let

(3.17)
$\displaystyle\mathcal{R}_{\beta}:=\left\\{(\rho,\theta):\rho\in(0,\beta),\theta\in\left(\max\left\\{0,2l\beta-l\rho-\frac{l}{d}\right\\},l\beta-l\rho\right)\right\\},$

Then for any $(\rho,\theta)\in\mathcal{R}_{\beta}$,

(3.18)
$\displaystyle\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\rho^{2}}<0.$

###### Proof.

Note that $\theta\leq\frac{l}{d}$ by (3.9) when $0<\beta<\frac{1}{d}$. By
(3.9), (3.3), we obtain

$\displaystyle\frac{l-1}{1-2\beta+\rho}-\frac{ld}{1-2\beta d+\rho
d+\frac{\theta d}{l}}$ $\displaystyle=$
$\displaystyle\frac{-l(d-1)+\frac{\theta d(l-1)}{l}-(1-2\beta d+\rho
d)}{(1-2\beta+\rho)\left(1-2\beta d+\rho d+\frac{\theta d}{l}\right)};$
$\displaystyle\leq$ $\displaystyle\frac{-l(d-2)-(1-2\beta d+\rho
d+\frac{\theta d}{l})}{(1-2\beta+\rho)\left(1-2\beta d+\rho d+\frac{\theta
d}{l}\right)}<0.$

Moreover,

$\displaystyle\frac{2(l-1)}{\beta-\rho}-\frac{2(l-1)}{\beta-\rho-\frac{\theta}{2}}<0.$

Then (3.18) follows from (3.11). ∎

Define the Hessian matrix

$\displaystyle
H(\beta,\rho,\theta):=\left(\begin{array}[]{cc}\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\rho^{2}}&\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\theta\partial\rho}\\\
\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\theta\partial\rho}&\frac{\partial^{2}\Psi_{d,l}(\beta,\rho,\theta)}{\partial\theta^{2}}\end{array}\right)$

######  Lemma 3.4.

Assume (2.1),(3.8) (3.9) hold.

  1. (1)

If

(3.20) $\displaystyle l\leq d$

Then (3.16) is a local maximizer of $\Psi_{d,l}(\beta,\rho,\theta)$ when
$(\rho,\theta)\in\mathcal{R}_{\beta}$ for every
$\beta\in\left(0,\frac{1}{d}\right)$;

  2. (2)

If

(3.21) $\displaystyle\beta<\frac{1}{1+\sqrt{(d-1)(l-1)}}$

then (3.16) is a local maximizer of $\Psi_{d,l}(\beta,\rho,\theta)$ when
$(\rho,\theta)\in\mathcal{R}_{\beta}$.

###### Proof.

Since (3.16) satisfies (3.13), it suffice to show that
$H(\beta,\beta^{2},l(d-1)\beta^{2})$ is negative definite when (3.20) holds.
By (3.18), (3.12),it suffices to show that

(3.22) $\displaystyle\det H(\beta,\beta^{2},l(d-1)\beta^{2})>0.$

when (3.20) holds. Note that

$\displaystyle H(\beta,\beta^{2},l(d-1)\beta^{2})$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}-\frac{1}{\beta^{2}}+\frac{l-1}{(1-\beta)^{2}}+\frac{2(l-1)}{\beta(1-\beta)}-\frac{2l}{\beta(1-d\beta)}-\frac{ld}{(1-\beta
d)^{2}}&-\frac{2}{\beta(1-d\beta)}-\frac{d}{(1-d\beta)^{2}}\\\
-\frac{2}{\beta(1-d\beta)}-\frac{d}{(1-d\beta)^{2}}&-\frac{1}{l(d-1)\beta^{2}}-\frac{2}{l\beta(1-d\beta)}-\frac{d}{l(1-\beta
d)^{2}}\end{array}\right),$

and therefore

(3.24) $\displaystyle\det
H(\beta,\beta^{2},l(d-1)\beta^{2})=\frac{\beta^{2}d-2\beta+\beta^{2}l-\beta^{2}dl+1}{l\beta^{4}(\beta
d-1)^{2}(\beta-1)^{2}(d-1)}$

Hence (3.22) holds if and only if

$\displaystyle g(\beta):=\beta^{2}(d+l-dl)-2\beta+1>0.$

Note that when $d\geq 2,l\geq 2$, $d+l-dl\leq 0$, and the identity holds if
and only if $d=l=2$.

  * •

When $d=l=2$, $1-2\beta>0$ given that $\beta\in\left(0,\frac{1}{d}\right)$.

  * •

When $d\geq 2$, $l\geq 2$, and at least one of $d$ and $l$ is strictly greater
than 2, $g(\beta)>0$ for all $\beta\in\left(0,\frac{1}{d}\right)$ if and only
if $g\left(\frac{1}{d}\right)\geq 0$. This gives $l\leq d$.

∎

######  Lemma 3.5.

Assume (2.1),(3.8) (3.9) hold. If $l=2$, then for each
$\beta\in\left(0,\frac{1}{d}\right)$, the Hessian matrix
$H(\beta,\rho,\theta)$ is negative definite for all
$(\rho,\theta)\in\mathcal{R}_{\beta}$.

###### Proof.

Again by (3.12) (3.18) it suffices to show that $\det H>0$ when $l=2$. Let

$\displaystyle A:$ $\displaystyle=$
$\displaystyle-\frac{1}{\rho}+\frac{1}{1-2\beta+\rho}+\frac{2}{\beta-\rho};$
$\displaystyle B:$ $\displaystyle=$
$\displaystyle-\frac{2}{\beta-\rho-\frac{\theta}{2}}-\frac{d}{1-2\beta d+\rho
d+\frac{\theta d}{2}}<0$ $\displaystyle C:$ $\displaystyle=$
$\displaystyle-\frac{1}{\theta}<0.$ $\displaystyle U:$ $\displaystyle=$
$\displaystyle-\frac{1}{\rho}+\frac{1}{1-2\beta+\rho}<0;$

Then

$\displaystyle\det H$ $\displaystyle=$
$\displaystyle(A+2B)\left(C+\frac{B}{2}\right)-B^{2}=AC+B\left(\frac{A}{2}+2C\right)$

Note that

$\displaystyle
AC=CU-\frac{2}{\theta(\beta-\rho)}\geq-\frac{2}{\theta(\beta-\rho)}$

and

$\displaystyle B\left(\frac{A}{2}+2C\right)$ $\displaystyle=$
$\displaystyle\frac{BU}{2}+B\left(\frac{1}{\beta-\rho}-\frac{2}{\theta}\right)$
$\displaystyle=$
$\displaystyle\frac{BU}{2}+\frac{4}{(\beta-\rho)\theta}+\left(-\frac{d}{1-2\beta
d+\rho d+\frac{\theta
d}{2}}\right)\left(\frac{1}{\beta-\rho}-\frac{2}{\theta}\right)$
$\displaystyle\geq$ $\displaystyle\frac{4}{(\beta-\rho)\theta}$

where the last inequality follows from (3.9). Hence we have $\det H>0$, and
the lemma follows. ∎

######  Lemma 3.6.

Assume (2.1),(3.8) (3.9) hold. Let $l\geq 3$. For each
$\beta\in\left(0,\frac{1}{2d}\right]$, the set

$\displaystyle\mathcal{R}_{\beta}\cap\\{(\rho,\theta):\det
H(\beta,\rho,\theta)>0\\}$

has at most one connected component in the $(\rho,\theta)$-plane.

###### Proof.

For simplicity let

$\displaystyle\eta:=\frac{\theta}{l}.$

For each fixed $\beta\in\left(0,\frac{1}{d}\right)$, explicit computations
show that $\det H(\beta,\rho,l\eta)=0$ if and only if

$\displaystyle\eta=(\beta-\rho)\left(1-\frac{2(1-\beta
d)(\beta+\rho-2\beta^{2}-\rho l(1-\beta))}{D(\rho)}\right):=\xi(\rho)$

where

$\displaystyle D(\rho)=\beta+\rho-2l\rho-d\rho^{2}-l\rho^{2}-2\beta^{2}-\beta
d\rho+3\beta l\rho+2\beta^{2}d\rho+dl\rho^{2}+\beta dl\rho-2\beta^{2}dl\rho$

Then for each fixed $(d,l,\beta)$ such that
$\beta\in\left(0,\frac{1}{d}\right)$, the equation

$\displaystyle\xi(\rho)=\beta-\rho$

has at most one solution in $\left(0,\beta\right)$ given by

(3.25) $\displaystyle\rho_{5}=\frac{\beta(1-2\beta)}{l(1-\beta)-1}.$

Moreover,

(3.26) $\displaystyle\xi^{\prime}(\rho)=-1+\frac{F(\rho)}{D^{2}}$

where

$\displaystyle F(\rho)$ $\displaystyle=$ $\displaystyle 2(\beta
d-1)^{2}(l-1)\left[\left(2l(1-\beta)^{2}-1\right)\rho^{2}-2\beta(1-2\beta)\rho-\beta^{2}(1-2\beta)^{2}\right]$

The equation

$\displaystyle\xi^{\prime}(\rho)=-1$

has a unique positive solution given by

(3.27) $\displaystyle\rho_{3}=\frac{\beta(1-2\beta)}{\sqrt{2l}(1-\beta)-1}$

Moreover, when $\rho<\rho_{3}$, $F(\rho)<0$ and when $\rho>\rho_{3}$,
$F(\rho)>0$. Note that

(3.28) $\displaystyle D(\rho)=(dl-l-d)\rho^{2}+(3\beta l-\beta
d-2l+2\beta^{2}d+\beta dl-2\beta^{2}dl+1)\rho-2\beta^{2}+\beta.$

Hence

$\displaystyle D(0)$ $\displaystyle=$ $\displaystyle\beta(1-2\beta)>0.$
$\displaystyle D(\beta)$ $\displaystyle=$ $\displaystyle 2\beta(1-\beta
d)(\beta-1)(l-1)<0.$

Let $\rho_{1}$ be the unique point in $\left(0,\beta\right)$ such that
$D(\rho_{1})=0$.

When $\beta d\leq\frac{1}{2}$ we have

$\displaystyle\mathcal{R}_{\beta}=\left\\{(\rho,\theta):\rho\in(0,\beta),\theta\in\left(0,l\beta-l\rho\right)\right\\},$

then

$\displaystyle\eta=\xi(\rho)=(\beta-\rho)\frac{J(\rho)}{D(\rho)};$

where

$\displaystyle J(\rho)$ $\displaystyle=$ $\displaystyle(dl-l-d)\rho^{2}+(\beta
d+\beta l+2\beta^{2}d-\beta
dl-1)\rho+2\beta^{2}d-\beta-4\beta^{3}d+2\beta^{2}$ $\displaystyle=$
$\displaystyle-\rho(dl-
l-d)(\beta-\rho)-\rho(1-2\beta^{2}d)-\beta(1-2\beta)(1-2\beta d)\leq 0$

where the identity holds if and only if $\rho=0$ and $\beta d=\frac{1}{2}$.

$\displaystyle J(\beta)$ $\displaystyle=$ $\displaystyle 2\beta(1-\beta
d)(\beta-1)<0$

The when $\rho\in(0,\beta)$, the curve $\eta=\xi(\rho)$ has two components:

  * •

When $\rho\in(0,\rho_{1})$, $\xi(\rho)\leq 0$ and
$\lim_{\rho\rightarrow\rho_{1}-}\xi(\rho)=-\infty$.

  * •

When $\rho\in(\rho_{1},\rho)$, $\xi(\rho)>0$,
$\lim_{\rho\rightarrow\rho_{1}+}\xi(\rho)=\infty$ and
$\frac{J(\beta)}{D(\beta)}=\frac{1}{l-1}<1$ when $l\geq 3$

Hence when $\rho\in(0,\rho_{1})$, the curve $\theta=l\xi(\rho)$ does not
intersect $\mathcal{R}_{\beta}$. When $\rho\in(\rho_{1},\rho)$, the curve
$\theta=l\xi(\rho)$ divide the triangular region $\mathcal{R}_{\beta}$ into
two connected components, exactly one of them satisfy $\det H>0$. It is
straightforward to check that the component on the right (resp. left)
satisfies $\det H<0$ (resp. $\det H>0$) given that $D(\rho)<0$ for
$\rho\in(\rho_{5},\beta)$; see Figure 3.1. ∎

Figure 3.1. The curve $\det H=0$ is represented by blue lines. When
$\beta\in\left(0,\frac{1}{2d}\right]$, $R_{\beta}$ is represented by the
triangular region in the $(\rho,\theta)$ plane with vertices $(\beta,0)$,
$(0,0)$ and $(0,\beta)$. The curve $\det H=0$ intersects the line
$\rho+\eta=\beta$ at a unique point $(\rho_{5},\beta-\rho_{5})$. The curve
$\det H=0$ divide the triangular region into two connected components - the
left component satisfies $\det H>0$ and the right component satisfies $\det
H<0$.

######  Lemma 3.7.

Assume (2.1),(3.8) (3.9) hold. Let $l\geq 3$. For each
$\beta\in\left(\frac{1}{2d},\frac{1}{d}\right)$, the set

$\displaystyle\mathcal{R}_{\beta}\cap\\{(\rho,\theta):\det
H(\beta,\rho,\theta)>0\\}$

has at most two connected components in the $(\rho,\theta)$-plane.

###### Proof.

If $1>\beta d>\frac{1}{2}$, then

$\displaystyle\mathcal{R}_{\beta}:$ $\displaystyle=$
$\displaystyle\left\\{(\rho,\theta):\rho\in\left(0,2\beta-\frac{1}{d}\right),\theta\in\left(2\beta
l-\rho l-\frac{l}{d},l\beta-l\rho\right)\right\\}$
$\displaystyle\cup\left\\{(\rho,\theta):\rho\in\left(2\beta-\frac{1}{d},\beta\right),\theta\in\left(0,l\beta-l\rho\right)\right\\},$
$\displaystyle 0<J(0)=-\beta(1-2\beta)(1-2\beta d)$

and

(3.30) $\displaystyle(\beta-0)\frac{J(0)}{D(0)}=\beta(2\beta
d-1)<2\beta-\frac{1}{d}$

Moreover

$\displaystyle J\left(2\beta-\frac{1}{d}\right)=\frac{l(d-1)(2\beta d-1)(\beta
d-1)}{d^{2}}<0.$

From (3) we can see that the graph of $J(\rho)$ is a parabola opening upwards.
Therefore there is a unique solution
$\rho_{2}\in\left(0,2\beta-\frac{1}{d}\right)$ such that $J(\rho_{2})=0$; and
$J(\rho)<0$ for all $\rho\in\left(2\beta-\frac{1}{d},\beta\right)$. Recall
that $\rho_{1}$ is the unique solution for $D(\rho)=0$ in
$\left(0,\beta\right)$. The following cases might occur

  1. (1)

$\rho_{1}\geq\rho_{2}$:

    1. (a)

when $\rho\in(0,\rho_{2}]$: $D(\rho)>0$, $J(\rho)>0$ hence
$\frac{J(\rho)}{D(\rho)}>0$. We claim that the graph of $\eta=\xi(\rho)$ when
$\rho\in(0,\rho_{2})$ in this case is always below the straight line
$\eta=2\beta-\rho-\frac{1}{d}$ in the $(\rho,\eta)$ plane. By (3.30) we know
this is true when $\rho=0$. This is also true when $\rho=\rho_{2}$ since
$\rho_{2}<2\beta-\frac{1}{d}$ and therefore $2\beta-\rho_{2}-\frac{1}{d}>0$
while $\frac{J(\rho_{2})}{D(\rho_{2})}=0$. Therefore if $\eta=\xi(\rho)$
intersects $\eta=2\beta-\rho-\frac{1}{d}$ when $\rho\in(0,\rho_{2})$, then the
intersection must be at least two points (counting multiplicities).

By (3.26) we have

$\displaystyle\frac{d\xi(\rho)-(2\beta-\rho-\frac{1}{d})}{d\rho}=\frac{F(\rho)}{D(\rho)^{2}}$

When $l\geq 3$ and $d\geq 2$, $F(\rho)$ a parabola opening upwards with
$F(0)<0$. Hence if there exists $0<\rho_{3}<\rho_{2}$ such that
$\frac{F(\rho_{3})}{D(\rho_{3})^{2}}=0$; then
$\frac{F(\rho_{3})}{D(\rho_{3})}>0$ for all $\rho\in(\rho_{3},\rho_{2})$, and
$\frac{F(\rho_{3})}{D(\rho_{3})}<0$ for all $\rho\in(0,\rho_{3})$. Then
$\eta=\xi(\rho)$ intersects $\eta=2\beta-\rho-\frac{1}{d}$ in at most one
point when $\rho\in(0,\rho_{2})$. It follows that
$\xi(\rho)<2\beta-\rho-\frac{1}{d}$ for all $\rho\in(0,\rho_{2})$.

    2. (b)

When $\rho\in(\rho_{2},\rho_{1}]$: $D(\rho)>0$ and $J(\rho)<0$, hence
$\frac{J(\rho)}{D(\rho)}<0$, and there for $\eta=\xi(\rho)$ is always below
the curve $\eta=\max\\{0,2\beta-\rho-\frac{1}{d}\\}$.

    3. (c)

When $\rho\in(\rho_{1},\beta)$. $D(\rho)<0$ and $J(\rho)<0$. Hence
$\frac{J(\rho)}{D(\rho)}>0$ and
$\lim_{\rho\rightarrow\rho_{1}+}\frac{J(\rho)}{D(\rho)}=+\infty$.

Note that $\xi(\rho)-(2\beta-\rho-\frac{1}{d})$ achieves its minimum in
$(\rho_{1},\beta)$ at $\rho_{3}$. Explicit computations show that

$\displaystyle\lim_{\beta\rightarrow\frac{1}{d}-}\left[\xi(\rho_{3})-\left(2\beta-\rho_{3}-\frac{1}{d}\right)\right]\frac{d}{1-\beta
d}=-1$

Therefore when $\beta\in\left(\frac{1}{d}-\epsilon,\frac{1}{d}\right)$ and
$\epsilon$ is sufficiently small,

$\displaystyle\xi(\rho_{3})-\left(2\beta-\rho_{3}-\frac{1}{d}\right)<0.$

Analyzing the derivative shows that
$\xi(\rho)-\max\\{\left(2\beta-\rho-\frac{1}{d}\right),0\\}$ can have at most
two zeros; hence in this case $\mathcal{R}_{\beta}\cap\\{(\rho,\theta),\det
H(\beta,\rho,\theta)>0\\}$ has at most two connected components in the
$(\rho,\theta)$-plane.

  2. (2)

$\rho_{1}<\rho_{2}$: when $\rho\in(0,\rho_{1})$, $D(\rho)>0$, $J(\rho)>0$,
hence $\frac{J(\rho)}{D(\rho)}>0$. By (3.30) we see that
$\xi(0)<2\beta-\frac{1}{d}<\beta$. Note also that
$(\beta-\rho)\lim_{\rho\rightarrow\rho_{1}-}\frac{J(\rho)}{D(\rho)}=+\infty>\beta-\rho_{1}>\max\\{2\beta-\rho_{1}-\frac{1}{d},0\\}$.
Then the curve $\eta=\xi(\rho)$ must intersect the curve $\eta=\beta-\rho$ at
$\rho_{5}\in(0,\rho_{1})$. Then somewhere in $(0,\rho_{5})$ we have
$\xi^{\prime}(\rho)>-1$. Then we have $\rho_{3}<\rho_{5}$. From (3.25) and
(3.27) we see that if $\rho_{3}<\rho_{5}$, then $l<2$. But this is a
contradiction to the fact that $l\geq 3$. Then we must have
$\rho_{1}\geq\rho_{2}$.

Then the lemma follows; see Figure 3.2. ∎

Figure 3.2. The top graph represents the case when $\det H>0$ has a unique
component in $R_{\beta}$; while the bottom graph represents the case when
$\det H>0$ has two components in $R_{\beta}$.

######  Lemma 3.8.

$\xi^{\prime}(\rho)$ is strictly increasing when $\rho\in(\rho_{5},\beta)$.

###### Proof.

It suffices to show that $\xi^{\prime\prime}(\rho)>0,\
\forall\rho\in(\rho_{5},\beta)$. Note that

$\displaystyle\xi^{\prime\prime}(\rho)=\frac{F^{\prime}(\rho)D(\rho)-2F(\rho)D^{\prime}(\rho)}{[D(\rho)]^{3}}=\frac{4(1-\beta
d)^{2}(l-1)K(\rho)}{[D(\rho)]^{3}}$

In particular we have

(3.31)
$\displaystyle\xi^{\prime\prime}(\rho_{3})=\frac{F^{\prime}(\rho_{3})}{[D(\rho_{3})]^{2}}>0$

and therefore

(3.32) $\displaystyle K(\rho_{3})<0.$

Note that

(3.33) $\displaystyle K^{\prime}(\rho)=3(dl-d-l)L(\rho);$

where

$\displaystyle L(\rho)=-2l(1-\beta)^{2}\rho^{2}+(\rho+\beta(1-2\beta))^{2}$

In particular we have

$\displaystyle L(\beta)=-\beta^{2}(1-\beta)^{2}(l-2)<0$

and

$\displaystyle L(\rho_{3})=0.$

Since $L$ is a parabola opening downwards, with exactly one negative root and
one positive root $\rho_{3}$, we obtain that

$\displaystyle L(\rho)<0;\ \forall\rho\in(\rho_{3},\beta);$

and

$\displaystyle L(\rho)>0;\ \forall\rho\in(\rho_{5},\rho_{3}).$

By (3.33) we obtain

$\displaystyle K^{\prime}(\rho)<0;\ \forall\rho\in(\rho_{3},\beta);$
$\displaystyle K^{\prime}(\rho)>0;\ \forall\rho\in(\rho_{5},\rho_{3}).$

Hence $K(\rho_{3})$ is the maximal value of $K(\rho)$ when
$\rho\in(\rho_{5},\beta)$.By (3.32), we obtain

$\displaystyle K(\rho)<0,\ \forall\rho\in(\rho_{5},\beta).$

By (3.31) we obtain

$\displaystyle\xi^{\prime\prime}(\rho)>0,\ \forall\rho\in(\rho_{5},\beta).$

Then the lemma follows. ∎

######  Lemma 3.9.

Let $l\geq 3$ and $d\geq 2$, $\beta\in\left(0,\frac{1}{d}\right)$ such that
(3.21) holds. Assume $R_{\beta}\cap\\{(\rho,\theta):\det H>0\\}$ is connected.
If

(3.34) $\displaystyle\xi^{\prime}(\rho)<-\frac{(d-1)\beta}{1-\beta};\
\forall\rho\in(\rho_{3},\beta)$

Then

$\displaystyle\max_{(\rho,\theta)\in R_{\beta}\cap\\{(\rho,\theta):\det H\geq
0\\}}\Psi_{d,l}(\beta,\rho,\theta)=2\Phi_{d,l}(\beta).$

Moreover, $(\beta^{2},l(d-1)\beta^{2})$ is the unique maximizer for
$\Psi_{d,l}(\beta,\rho,\theta)$ in the region
$R_{\beta}\cap\\{(\rho,\theta):\det H\geq 0\\}$.

###### Proof.

If $\beta\in\left(0,\frac{1}{2d}\right]$, we consider the corresponding region
in the $(\rho,\eta)$-plane which is bounded by

  1. (a)

$\rho=0$, $\eta\in[0,\beta]$; and

  2. (b)

$\eta=0$, $\rho\in[0,\theta]$; and

  3. (c)

$\eta=\xi(\rho)$, $\rho\in[\rho_{5},\beta]$; and

  4. (d)

$\eta=\beta-\rho$; $\rho\in[0,\rho_{5}]$.

See Figure 3.1.

If $\beta\in\left(\frac{1}{2d},\frac{1}{d}\right)$, when the set
$\mathcal{R}_{\beta}\cap\\{(\rho,\theta:\det H(\beta,\rho,\theta))>0\\}$ has
exactly one connected component in the $(\rho,\theta)$-plane, its
corresponding region in the $(\rho,\eta)$-plane is bounded by

  1. (A)

$\rho=0$, $\eta\in\left[2\beta-\frac{1}{d},\beta\right]$; and

  2. (B)

$\eta=0$, $\rho\in\left[2\beta-\frac{1}{d},\theta\right]$; and

  3. (C)

$\eta=\xi(\rho)$, $\rho\in[\rho_{5},\beta]$; and

  4. (D)

$\eta=\beta-\rho$, $\rho\in[0,\rho_{5}]$;and

  5. (E)

$\rho+\eta=2\beta-\frac{1}{d}$, $\eta\in\left[0,2\beta-\frac{1}{d}\right]$.

See Figure 3.2(1).

In either case by Lemma 3.4, the point $z_{0}:=(\beta,(d-1)\beta^{2})$ is a
local maximizer for $\Psi_{d,l}(\beta,\rho,\eta l)$. If the following
conditions hold

  1. (i)

for any point $z$ in the region or on the boundary of the region
$\mathcal{R}_{\beta}(\rho,\eta l)\cap\\{(\rho,\eta):\det
H(\beta,\rho,l\eta))>0\\}$, the straight line joining $z_{0}$ and $z$ lies in
the region $\mathcal{R}_{\beta}(\rho,\eta l)\cap\\{(\rho,\eta):\det
H(\beta,\rho,l\eta))>0\\}$ except the endpoint (in the case that $z$ is on the
boundary).

Then for any point $z$ in the region $\mathcal{R}_{\beta}(\rho,\eta
l)\cap\\{(\rho,\eta):\det H(\beta,\rho,l\eta))>0\\}$, or on the boundary of
the region; let $l_{z_{0}z}$ be the straight line joining $z$ and $z_{0}$
starting from $z_{0}$ and ending at $z$; we have

$\displaystyle\Psi_{d,l}(\beta,z)=\Psi_{d,l}(\beta,z_{0})+\int_{l_{z_{0}z}}\partial_{l_{z_{0}z},w}\Psi_{d,l}(\beta,w)dw$

where $\partial_{l_{z_{0}z},w}\Psi_{d,l}(\beta,w)$ is the directional
derivative of $\Psi_{d,l}(\beta,w)$ with respect to $w$ along $l_{z_{0}z}$.
Note that

$\displaystyle\left.\partial_{l_{z_{0}z}w}\Psi_{d,l}(\beta,w)\right|_{w=z_{0}}=0.$

Since $H$ is negative definite in the region $\mathcal{R}_{\beta}(\rho,\eta
l)\cap\\{(\rho,\eta):\det H(\beta,\rho,l\eta))>0\\}$ , the second order
directional derivative satisfies

$\displaystyle\partial^{2}_{l_{z_{0}z},w}\Psi_{d,l}(\beta,w)=\mathbf{v}^{T}H\mathbf{v}<0$

for all $w$ in the interior of the line $l_{z_{0}z}$; where
$\mathbf{v}\in{\mathbb{R}}^{1\times 2}$ is the unit directional vector along
the line $l_{z_{0},z}$. Then we obtain

$\displaystyle\partial_{l_{z_{0}z},w}\Psi_{d,l}(\beta,w)<0;$

for each $w$ in the interior of the line $l_{z_{0}z}$; and therefore

$\displaystyle\Psi_{d,l}(\beta,z)<\Psi_{d,l}(\beta,z_{0})$

for any point $z$ in the region $\mathcal{R}_{\beta}(\rho,\eta
l)\cap\\{(\rho,\eta):\det H(\beta,\rho,l\eta))>0\\}$, or on the boundary of
the region other than $z_{0}$.

Now it remains to prove condition (i). It suffices to check condition (i) for
each boundary point on the boundary of the region
$\mathcal{R}_{\beta}(\rho,\eta l)\cap\\{(\rho,\eta):\det
H(\beta,\rho,l\eta))>0\\}$. The straight line in the $(\rho,\eta)$-plane
joining $z_{0}$ and $(\beta,0)$ has equation

$\displaystyle\eta=-\frac{(d-1)\beta}{1-\beta}(\rho-\beta)$

If for each $\rho\in[\rho_{5},\beta)$,

(3.35) $\displaystyle\xi^{\prime}(\rho)<-\frac{(d-1)\beta}{1-\beta}$

Then conditions (i) holds. Since when $\rho\leq\rho_{3}$ and $d\beta<1$,

$\displaystyle\xi^{\prime}(\rho)\leq-1<-\frac{(d-1)\beta}{1-\beta};$

it suffices to check (3.35) for $\rho\in(\rho_{3},\beta)$; which is equivalent
to (3.34). ∎

######  Lemma 3.10.

Assume $d\geq 2$ and $l\geq 3$. If

(3.36) $\displaystyle\beta\leq\frac{1}{dl-d-l+2};$

then (3.34) holds.

###### Proof.

Then (3.34) holds if and only if

$\displaystyle\xi^{\prime}(\beta)\leq-\frac{(d-1)\beta}{1-\beta};$

which gives (3.36). ∎

######  Lemma 3.11.

Assume $d\geq 2$ and $l\geq 3$. If (3.36) holds, then
$R_{\beta}\cap\\{(\rho,\theta):\det H>0\\}$ has exactly one connected
component.

###### Proof.

We see that when (3.36) holds, the line segment passing through
$(\beta^{2},(d-1)\beta^{2})$ and $(\beta,0)$ in the $(\rho,\eta)$-plane
intersects the curve $\det H=0$ at a unique point $(\beta,0)$, and the line
segment lies below the curve, since

  * •

both of them pass through the point $(\beta,0)$; and

  * •

The slope of the line segment is greater than or equal to the slope of the
tangent line of the curve $\det H=0$ at $(\beta,0)$ in the
$(\rho,\eta)$-plane; and

  * •

The slope of the line segment is strictly greater than or the slope of the
tangent line of the curve $\det H=0$ at any point other than $(\beta,0)$ in
the $(\rho,\eta)$-plane.

Note that the line segment passing through $(\beta^{2},(d-1)\beta^{2})$ and
$(\beta,0)$ in the $(\rho,\eta)$-plane completely lies in the region
$\\{(\rho,\eta):(\rho,\eta l)\in R_{\beta}\\}$ since the region is convex.
Hence the line segment does not cross the (possible) boundary
$\eta=2\beta-\rho-\frac{1}{d}$. Therefore the curve $\det H=0$ does not cross
the boundary $\eta=2\beta-\rho-\frac{1}{d}$ either. Then the lemma follows. ∎

######  Lemma 3.12.

Assume $3\leq l$, $2\leq d$, and (3.36) holds. Then

$\displaystyle\max_{(\rho,\theta)\in
R_{\beta}}\Psi_{d,l}(\beta,\rho,\theta)=2\Phi_{d,l}(\beta)$

###### Proof.

By Lemmas 3.9 and 3.10, we obtain that under the assumptions of the lemma,

$\displaystyle\max_{(\rho,\theta)\in R_{\beta}\cap\\{\det H\geq
0\\}}\Psi_{d,l}(\beta,\rho,\theta)=2\Phi_{d,l}(\beta).$

We now find

$\displaystyle\max_{(\rho,\theta)\in R_{\beta}\cap\\{\det
H<0\\}}\Psi_{d,l}(\beta,\rho,\theta)$

When the Hessian determinant is negative, $\Psi_{d,l}(\beta,\rho,\theta)$ as a
function of $(\rho,\theta)$ cannot achieve a local maximal value at an
interior point; it cannot achieve the global maximal value in $R_{\beta}$
along the boundary satisfying $\det H=0$ either, since this is also the
boundary of the region $\det H>0$ where the function is strictly concave, and
the maximal value in $\det H\geq 0$ is already achieved at the unique interior
point $(\beta^{2},l(d-1)\beta^{2})$. Therefore if a global maximal value of
$\Psi_{d,l}(\beta,\rho,\theta)$ in $R_{\beta}$ is achieved when
$(\rho,\theta)\in R_{\beta}\cap\\{\det H<0\\}$, then it must be achieved along
the boundary $\theta=l(\beta-\rho)$; see Figure 3.1. More precisely, the only
possible candidate for the global maximal value when $\det H<0$ is

$\displaystyle\max_{\rho\in\left[\rho_{5},\beta\right]}\Psi_{d,l}(\beta,\rho,l(\beta-\rho))$

Along the line $\theta=l(\beta-\rho)$, by (3) we have

$\displaystyle T_{d,l,\beta}(\rho):$ $\displaystyle=$
$\displaystyle\Psi_{d,l}(\beta,\rho,l(\beta-\rho))$ $\displaystyle=$
$\displaystyle-\rho\ln\rho+(l-1)(1-2\beta+\rho)\ln(1-2\beta+\rho)+l(\beta-\rho)\ln(d-1)$
$\displaystyle+(l-2)(\beta-\rho)\ln(\beta-\rho)-\frac{l}{d}(1-\beta
d)\ln(1-\beta d)$

Then by (1.5),

$\displaystyle\lim_{\rho\rightarrow\beta-}\Psi_{d,l}(\beta,\rho,l(\beta-\rho))=-\beta\ln\beta+(l-1)(1-\beta)\ln(1-\beta)-\frac{l}{d}(1-\beta
d)\ln(1-\beta d)=\Phi_{d.l}(\beta)$

Moreover,

$\displaystyle\frac{dT_{d,l\beta}(\rho)}{d\rho}=-\ln\rho+(l-1)\ln(1-2\beta+\rho)-l\ln(d-1)-(l-2)\ln(\beta-\rho)$

and

(3.38) $\displaystyle\frac{d^{2}T_{d,l\beta}(\rho)}{d\rho^{2}}$
$\displaystyle=$
$\displaystyle-\frac{1}{\rho}+\frac{l-1}{1-2\beta+\rho}+\frac{l-2}{\beta-\rho}=\frac{l\rho(1-\beta)-(\beta+\rho-2\beta^{2})}{\rho(\beta-\rho)(1-2\beta+\rho)}.$

When $\rho\in[\rho_{5},\beta)$, $\frac{d^{2}T_{d,l\beta}(\rho)}{d\rho^{2}}\geq
0$, and the identity holds if and only if $\rho=\rho_{5}$. Therefore
$\frac{dT_{d,l\beta}(\rho)}{d\rho}$ is monotone increasing when
$\rho\in[\rho_{5},\beta)$. The following cases might occur:

  1. (1)

$\left.\frac{dT_{d,l\beta}(\rho)}{d\rho}\right|_{\rho=\rho_{5}}<0$; in this
case

$\displaystyle\max_{\rho\in[\rho_{5},\beta]}T_{d,l,\beta}(\rho)=\max\\{T_{d,l,b}(\rho_{5}),T_{d,l,b}(\beta)\\}.$

But both $\rho_{5}$ and $\beta$ are along the boundary of the unique connected
component of $R_{\beta}$ such that $\det H(\beta,\rho,\theta)>0$, where
$\Psi_{d,l}(\beta,\rho,\theta)$ is strictly concave with a maximal value given
by $2\Phi_{d}(\beta)$; hence we have

$\displaystyle\max\\{T_{d,l,\beta}(\rho_{5}),T_{d,l,b}(\beta)\\}\leq
2\Phi_{d,l}(\beta).$

Hence the lemma follows when
$\left.\frac{dT_{d,l\beta}(\rho)}{d\rho}\right|_{\rho=\rho_{5}}<0$. Or

  2. (2)

$\left.\frac{dT_{d,l\beta}(\rho)}{d\rho}\right|_{\rho=\rho_{5}}\geq 0$. In
this case $T_{d,l,\beta}(\rho)$ is increasing when $\rho\in[\rho_{5},\beta)$.
Hence we have

$\displaystyle\max\\{T_{d,l,\beta}(\rho_{5}),T_{d,l,b}(\beta)\\}=T_{d,l,b}(\beta)\leq
2\Phi_{d,l}(\beta).$

Then the lemma holds when
$\left.\frac{dT_{d,l\beta}(\rho)}{d\rho}\right|_{\rho=\rho_{5}}\geq 0$ as
well.

∎

######  Lemma 3.13.

Assume one of the following conditions holds:

  * •

$l=2$, and $\beta\in\left(0,\frac{1}{d}\right)$; or

  * •

The assumptions of Lemma 3.12 hold.

Furthermore, we assume that

$\displaystyle\Psi_{d,l}(\beta,\beta^{2},l(d-1)\beta^{2})>0.$

we have

$\displaystyle\lim_{m\rightarrow\infty}\frac{\mathbb{E}Z_{m\beta}^{2}}{(\mathbb{E}Z_{m\beta})^{2}}=\frac{1-\beta}{\sqrt{\beta^{2}(d+l-dl)-2\beta+1}}$

###### Proof.

Let $L\geq 1$ be a positive integer. By Lemma 2.2 and (3), we obtain

$\displaystyle
F_{\beta}(m\rho,m\theta)=m^{-2}e^{m\Psi_{d,l}(\beta,\rho,\theta)}\frac{1}{4\pi^{2}\left(\beta-\rho-\frac{\theta}{l}\right)\sqrt{\rho\theta\left(1-2\beta
d+\rho d+\frac{\theta d}{l}\right)}}\left(1+O\left(\frac{1}{m}\right)\right).$

Then

$\displaystyle\sum_{s=0}^{m\beta}\sum_{t=\max\left\\{0,4m\beta-2s-\frac{2m}{d}\right\\}}^{2m\beta-2s}F_{\beta}(s,t)=\left(1+O\left(\frac{1}{m}\right)\right)$
$\displaystyle\frac{e^{m\Psi_{d}\left(\beta,\beta^{2},2(d-1)\beta^{2}\right)}}{4\pi^{2}m^{2}}\sum_{s=1}^{m\beta-2}\sum_{t=\max\left\\{0,4m\beta-2s-\frac{2m}{d}\right\\}+1}^{2m\beta-2s-1}\frac{e^{-m\left[\Phi_{d}\left(\beta,\beta^{2},2(d-1)\beta^{2}\right)-\Phi_{d}\left(\beta,\frac{s}{m},\frac{t}{m}\right)\right]}}{\left(\beta-\frac{s}{m}-\frac{t}{lm}\right)\sqrt{\frac{st}{m^{2}}\left(1-2\beta
d+\frac{sd}{m}+\frac{td}{lm}\right)}}$

We shall split the sum over $1\leq s\leq m\beta-2$,
$\max\left\\{0,4m\beta-2s-\frac{2m}{d}\right\\}+1\leq t\leq 2m\beta-2s-1$ into
two parts

  * •

Part I is the sum over $(\frac{s}{m},\frac{t}{m})$ in a $\frac{L}{\sqrt{m}}$
neighborhood of $(\beta^{2},l(d-1)\beta^{2})$; more precisely

$\displaystyle(s,t)\in\mathcal{N}:=\left\\{(s,t)\in{\mathbb{Z}}^{2}:\left|\frac{s}{m}-\beta^{2}\right|\leq\frac{L}{\sqrt{m}};\right.$
$\displaystyle\left.\left|\frac{t}{m}-l(d-1)\beta^{2}\right|\leq\frac{L}{\sqrt{m}};1\leq
s\leq m\beta-2;\max\left\\{0,2lm\beta-ls-\frac{lm}{d}\right\\}+1\leq t\leq
lm\beta-ls-1.\right\\}$

  * •

Part II is the sum over $1\leq s\leq m\beta-2$, $\max\left\\{0,2lm\beta-
ls-\frac{lm}{d}\right\\}+1\leq t\leq lm\beta-ls-1$, such that
$\left(\frac{s}{m},\frac{t}{m}\right)$ is outside the $\frac{L}{\sqrt{m}}$
neighborhood of $(\beta^{2},l(d-1)\beta^{2})$.

Then we have

$\displaystyle\frac{1}{4\pi^{2}}\sum_{s=1}^{m\beta-2}\sum_{t=\max\left\\{0,2lm\beta-
ls-\frac{lm}{d}\right\\}+1}^{lm\beta-
ls-1}m^{-2}\frac{e^{-m\left[\Phi_{d}\left(\beta,\beta^{2},l(d-1)\beta^{2}\right)-\Phi_{d}\left(\beta,\frac{s}{m},\frac{t}{m}\right)\right]}}{\left(\beta-\frac{s}{m}-\frac{t}{lm}\right)\sqrt{\frac{st}{m^{2}}\left(1-2\beta
d+\frac{sd}{m}+\frac{td}{lm}\right)}}$ $\displaystyle=$
$\displaystyle\mathrm{I}+\mathrm{II}$

Let

$\displaystyle\xi_{s,t}:=\left(\frac{s}{m}-\beta^{2},\frac{t}{m}-l(d-1)\beta^{2}\right)\in{\mathbb{R}}^{1\times
2}.$

and $\xi_{s,t}^{T}\in{\mathbb{R}}^{2\times 1}$ be the transpose of
$\xi_{s,t}$. Note that when $(s,t)$ is on the boundary of $\mathcal{N}$, from
the Taylor expansion of $\Phi_{d}(\beta,\cdot,\cdot)$ at
$(\beta^{2},l(d-1)\beta^{2})$, we obtain

$\displaystyle\Phi_{d}\left(\beta,\beta^{2},l(d-1)\beta^{2}\right)-\Phi_{d}\left(\beta,\frac{s}{m},\frac{t}{m}\right)=-\frac{\xi_{s,t}H(\beta,\beta^{2},2(d-1)\beta^{2})\xi_{s,t}^{T}}{2!}+O\left(\left(\frac{L}{\sqrt{m}}\right)^{3}\right)$

Assume $-\lambda$ ($\lambda>0$) is the maximal eigenvalue of
$H(\beta,\beta^{2},l(d-1)\beta^{2})$, then

$\displaystyle
e^{-m\left[\Phi_{d}\left(\beta,\beta^{2},l(d-1)\beta^{2}\right)-\Phi_{d}\left(\beta,\frac{s}{m},\frac{t}{m}\right)\right]}=O\left(e^{-\frac{\lambda
L^{2}}{2}}\right)$

and

$\displaystyle\sum_{s=1}^{m\beta-2}\sum_{t=\max\left\\{0,2lm\beta-
ls-\frac{lm}{d}\right\\}+1}^{lm\beta-
ls-1}\frac{e^{-m\left[\Phi_{d}\left(\beta,\beta^{2},l(d-1)\beta^{2}\right)-\Phi_{d}\left(\beta,\frac{s}{m},\frac{t}{m}\right)\right]}}{\left(\beta-\frac{s}{m}-\frac{t}{lm}\right)\sqrt{\frac{st}{m^{2}}\left(1-2\beta
d+\frac{sd}{m}+\frac{td}{lm}\right)}}$

is approximately $e^{-\frac{\lambda L^{2}}{2}}$ multiplying a convergent
geometric series. Hence when $m$ is large,

$\displaystyle m\mathrm{II}\leq
C^{\prime\prime}\frac{e^{-\frac{L^{2}}{2}}}{m}\rightarrow 0$

as $L\rightarrow\infty$; where $C^{\prime\prime}>0$ is a constant independent
of $m$.

Moreover,

$\displaystyle\mathrm{I}=\frac{1}{4\pi^{2}m^{2}}\sum_{s,t\in\mathcal{N}}\frac{e^{m\left[\frac{\xi_{s,t}H(\beta,\beta^{2},l(d-1)\beta^{2})\xi_{s,t}^{T}}{2}+O\left(\left(\frac{r_{m}}{\sqrt{m}}\right)^{3}\right)\right]}}{\left(\beta-\frac{s}{m}-\frac{t}{lm}\right)\sqrt{\frac{st}{m^{2}}\left(1-2\beta
d+\frac{sd}{m}+\frac{td}{lm}\right)}}\left(1+O\left(\frac{1}{m}\right)\right)$

Hence we have

(3.39) $\displaystyle\lim_{I\rightarrow\infty}\lim_{m\rightarrow\infty}mI$
$\displaystyle=$
$\displaystyle\frac{1}{4\pi^{2}\sqrt{l(d-1)}\beta^{3}(1-d\beta)^{2}}\int_{{\mathbb{R}}^{2}}e^{\frac{\mathbf{x}H(\beta,\beta^{2},2(d-1)\beta^{2})\mathbf{x}^{T}}{2}}dx_{1}dx_{2}$
$\displaystyle=$
$\displaystyle\frac{2\pi}{4\pi^{2}\sqrt{l(d-1)}\beta^{3}(1-d\beta)^{2}\sqrt{\det
H(\beta,\beta^{2},l(d-1)\beta^{2})}}$

where

$\displaystyle\mathbf{x}=(x_{1},x_{2})\in{\mathbb{R}}^{1\times 2}$

Then the lemma follows from (3.39), (3.24) and (2.7). ∎

##  4\. Subgraph Conditioning

In this section, we show that conditional on a matching , the distributions of
the number of cycles of different lengths on $\mathcal{G}_{m,d,l}$ converge to
independent Poisson random variables as $m\rightarrow\infty$. Similar results
when conditional on a perfect matching was proved in [5].

Let $k\geq 1$ be a positive integer. Let

$\displaystyle[k]:=\\{1,2,\ldots,k\\}.$

Define a $k$-cycle on $\mathcal{G}_{m,d,l}$ to be an alternating sequence of
vertices and hyper-edges

$\displaystyle
v_{0},e_{1},v_{1},\ldots,v_{i-1},e_{i},v_{i},\ldots,v_{k-1},e_{k},v_{k}$

such that

  * •

each $v_{i}$ is a vertex for $0\leq i\leq k$;

  * •

each $e_{j}$ is a hyper-edge for $1\leq j\leq k$;

  * •

$v_{0}=v_{k}$; and

  * •

$v_{i}\neq v_{j}$, for any $i\neq j$, $\\{i,j\\}\neq\\{0,k\\}$; and

  * •

for each $i\in[k]$, $e_{i}$ is incident to both $v_{i-1}$ and $v_{i}$.

In particular, a $1$-cycle is a hyper-edge, at least two half-edges of which
share a vertex.

Let $C_{k}$ be the number of $k$-cycles on $\mathcal{G}_{m,d,l}$, and let
$b\geq 1$ be a positive integer.

For $\mathbf{c}=(c_{1},c_{2},\ldots,c_{b})\in\mathbb{N}^{b}$. Let

$\displaystyle\Omega_{\mathbf{c}}:=\\{\mathcal{G}_{m,d,l}\in\Omega_{m,d,l}:C_{k}=c_{k},k\in[b]\\}.$

For $\beta\in\left(0,\frac{1}{d}\right)$, define

$\displaystyle
E_{\beta,\mathbf{c}}:=\mathbb{E}(Z_{m\beta}|\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}}).$

For each $\mathcal{G}_{m,d,l}=(V,E)\in\Omega_{m,d,l}$, let
$Q_{\mathcal{G}_{m,d,l},\beta}$ be the set of all the matchings on
$\mathcal{G}_{m,d,l}$ consisting of exactly $m\beta$ present hyperedges. Let
$M_{0}\subseteq E$, $|M_{0}|=m\beta$ be a fixed set of $m\beta$ hyperedges.
Note that for any other set $M$ of $m\beta$ hyperedges, the probability that
$M_{0}$ is matching on a random graph $\mathcal{G}_{m,d}$ is the same as the
probability that $M$ is a matching on a random graph $\mathcal{G}_{m,d}$. More
precisely,

$\displaystyle\mathbb{P}(M\in\mathcal{Q}_{\mathcal{G}_{m,d,l},\beta})=\mathbb{P}(M_{0}\in\mathcal{Q}_{\mathcal{G}_{m,d,l},\beta})=\frac{(lm(1-\beta))!}{(lm(1-d\beta))!}\frac{(lm(1-d\beta))!}{(lm)!}\frac{d^{lm\beta}\left(\frac{lm}{d}\right)!}{\left(\frac{lm}{d}(1-d\beta)\right)!}$

and from the symmetry of hyperedges we can also see that

$\displaystyle\mathbb{P}(\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}}|M\in
Q_{\mathcal{G}_{m,d,l},\beta})=\mathbb{P}(\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}}|M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta})$

Then

(4.1) $\displaystyle E_{\beta,\mathbf{c}}$ $\displaystyle=$
$\displaystyle\frac{1}{|\Omega_{\mathbf{c}}|}\sum_{\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}}}\sum_{M\in
Q_{\mathcal{G}_{m,d,l},\beta}}1$ $\displaystyle=$
$\displaystyle\frac{|\Omega|}{|\Omega_{\mathbf{c}}|}\sum_{M\subset
E,|M|=m\beta}\mathbb{P}(M\in
Q_{\mathcal{G}_{m,d,l},\beta},\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}})$
$\displaystyle=$
$\displaystyle\frac{\mathbb{P}(\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}}|M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta})}{\mathbb{P}(\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}})}\sum_{M\subset
E,|M|=m\beta}\mathbb{P}(M_{0}\in Q_{G_{m,d,l}},\beta)$ $\displaystyle=$
$\displaystyle\frac{\mathbb{E}Z_{m\beta}\mathbb{P}(\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}}|M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta})}{\mathbb{P}(\mathcal{G}_{m,d,l}\in\Omega_{\mathbf{c}})}$

Let $E_{t}$, $t=0,1,\ldots,\lfloor\frac{k}{2}\rfloor$ be the expected number
of $k$-cycles including exactly $t$ hyperedges from $M_{0}$. Then we may
compute $E_{t}$ as follows

  1. (1)

Choose $t$ hyperedges from the $m\beta$ hyperedges in $M_{0}$; there are
${m\beta\choose t}$ choices. Cyclically order these edges, there are
$\frac{(t-1)!}{2!}$ different orders. Choose ordered pairs of half-edges from
each of these $t$ hyperedges to connect with half-edges not in $M_{0}$, there
are $(l(l-1))^{t}$ choices. For $1\leq i\leq t$, let $s_{i}\geq 1$ be the
number of edges along the $k$-cycle between the $(i-1)$th and $i$th hyperedge
in $M_{0}$ along the cycle. Then we need to choose positive integers
$s_{1},\ldots,s_{k}$, such that $s_{1}+\ldots+s_{k}=k-t$. There are
${k-t-1\choose t-1}$ choices.

  2. (2)

Choose $k-t$ hyperedges from the $m-m\beta$ hyperedges not in $M_{0}$.
Consider all the possible orderings of these hyperedges as well as choices of
two ordered half-edges in each of these chosen hyperedge to place them along
the cycle, there are $(k-t)![l(l-1)]^{k-t}$ possibilities. The factor
$(d-1)^{k}$ indicates the possible number of locations of two half edges
incident to the same vertex along the $k$-cycle.

  3. (3)

In the $k-2t$ vertices along the cycle which are not incident to an edge in
$M_{0}$ along the cycle, assume that $s$ of them are incident to an half-edge
in $M_{0}$ but not along the cycle.

Hence we have

$\displaystyle E_{0}$ $\displaystyle=$ $\displaystyle\left[{m-m\beta\choose
k}\frac{(k-1)!}{2!}[l(l-1)]^{k}\right](d-1)^{k}\left[\sum_{s=0}^{k}(d-2)^{s}{lm\beta\choose
s}{k\choose s}s!\right.$ $\displaystyle\left.\frac{(lm-
lm\beta-2k)!}{(lm-(lm\beta+k-s)d)!}\frac{(lm-(lm\beta+k-s)d)!}{(lm)!}\frac{d^{lm\beta+k-s}\left(\frac{lm}{d}\right)!}{\left(\frac{lm}{d}-(lm\beta+k-s)\right)!}\right]$

If $t\geq 1$,

$\displaystyle E_{t}$ $\displaystyle=$ $\displaystyle\left[{m\beta\choose
t}\frac{(t-1)!}{2!}[l(l-1)]^{t}{k-t-1\choose t-1}\right]\left[{m-m\beta\choose
k-t}(k-t)![l(l-1)]^{k-t}\right](d-1)^{k}$
$\displaystyle\times\left[\sum_{s=0}^{k-2t}(d-2)^{s}{lm\beta-2t\choose
s}{k-2t\choose s}s!\frac{(lm-lm\beta-2k+2t)!}{(lm-(lm\beta+k-2t-s)d)!}\right.$
$\displaystyle\left.\frac{(lm-(lm\beta+k-2t-s)d)!}{(lm)!}\frac{d^{lm\beta+k-2t-s}\left(\frac{lm}{d}\right)!}{\left(\frac{lm}{d}-(lm\beta+k-2t-s)\right)!}\right]$

Then

(4.2) $\displaystyle\mathbb{E}(C_{k}|M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta})=\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\frac{E_{t}}{\mathbb{P}(M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta})}=\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\sum_{s=0}^{k-2t}E_{\beta,k}(t,s)$

where when $t\geq 1$,

$\displaystyle E_{\beta,k}(t,s)$ $\displaystyle=$
$\displaystyle\frac{(m\beta)!(k-t-1)!}{2t!(m\beta-t)!}[l(l-1)]^{k}(d-1)^{k}(d-2)^{s}\frac{(m-m\beta)!}{(m-m\beta-k+t)!}$
$\displaystyle\frac{(lm\beta-2t)!}{(lm\beta-2t-s)!(k-2t-s)!s!}\frac{(lm-
lm\beta-2k+2t)!}{(lm(1-\beta))!}$
$\displaystyle\frac{d^{k-2t-s}\left(\frac{lm}{d}(1-d\beta)\right)!}{\left(\frac{lm}{d}-(lm\beta+k-2t-s)\right)!}$

and

$\displaystyle E_{\beta,k}(0,s)$ $\displaystyle=$
$\displaystyle\frac{(m-m\beta)!}{2(m-m\beta-k)!}(k-1)![l(l-1)]^{k}(d-1)^{k}(d-2)^{s}\frac{(lm\beta)!}{s!(lm\beta-s)!(k-s)!}$
$\displaystyle\frac{(lm-
lm\beta-2k)!}{(lm(1-\beta))!}\frac{d^{k-s}\left(\frac{lm}{d}(1-d\beta)\right)!}{\left(\frac{lm}{d}-(lm\beta+k-s)\right)!}$

######  Lemma 4.1.

When $k$ is fixed and $m\rightarrow\infty$,

$\displaystyle\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\sum_{s=0}^{k-2t}E_{\beta,k}(t,s)\approx\frac{(d-1)^{k}(l-1)^{k}}{2k}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)$

###### Proof.

When $k$ is fixed and $m\rightarrow\infty$, we have when $t\geq 1$,

$\displaystyle E_{\beta,k}(t,s)$ $\displaystyle\approx$
$\displaystyle\frac{(d-1)^{k}(l-1)^{k}(1-d\beta)^{k}}{2(1-\beta)^{k}}{k-t-1\choose
t-1}{k-2t\choose
s}\frac{1}{t}\frac{\beta^{t+s}(1-\beta)^{t}(d-2)^{s}}{(1-d\beta)^{2t+s}}$

and

$\displaystyle\sum_{s=0}^{k-2t}E_{\beta,k}(t,s)$ $\displaystyle\approx$
$\displaystyle\sum_{s=0}^{k-2t}\frac{(d-1)^{k}(l-1)^{k}(1-d\beta)^{k}}{2(1-\beta)^{k}}\frac{1}{k-t}{k-t\choose
t}{k-2t\choose s}\frac{\beta^{t+s}(1-\beta)^{t}(d-2)^{s}}{(1-d\beta)^{2t+s}}$
$\displaystyle=$
$\displaystyle\frac{(d-1)^{k}(l-1)^{k}}{2(1-\beta)^{k}}\frac{1}{k-t}{k-t\choose
t}\beta^{t}(1-\beta)^{t}\left(1-2\beta\right)^{k-2t}$

Moreover,

$\displaystyle
E_{\beta,k}(0,s)\approx\frac{(d-1)^{k}(l-1)^{k}(1-d\beta)^{k}}{2k(1-\beta)^{k}}{k\choose
s}\frac{\beta^{s}(d-2)^{s}}{(1-d\beta)^{s}}$

and

$\displaystyle\sum_{s=0}^{k}E_{\beta,k}(0,s)\approx\frac{(d-1)^{k}(l-1)^{k}(1-2\beta)^{k}}{2k(1-\beta)^{k}}$

Hence we have

$\displaystyle\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\sum_{s=0}^{k-2t}E_{\beta,k}(t,s)$
$\displaystyle\approx$
$\displaystyle\frac{(d-1)^{k}(l-1)^{k}(1-2\beta)^{k}}{2(1-\beta)^{k}}\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\frac{1}{k-t}{k-t\choose
t}\alpha^{t}$

where

$\displaystyle\alpha=\frac{\beta(1-\beta)}{(1-2\beta)^{2}}$

If $f(x)$ is a Laurent series of $x$, for $i\in{\mathbb{Z}}$, let
$[x^{i}]f(x)$ be the coefficient for $x^{i}$ in $f(x)$. Then we obtain,

$\displaystyle\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\frac{1}{k-t}{k-t\choose
t}\alpha^{t}$ $\displaystyle=$
$\displaystyle\alpha^{k}[x^{k}]\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\left(\frac{x(1+x)}{\alpha}\right)^{k-t}\frac{1}{k-t}$
$\displaystyle=$
$\displaystyle\alpha^{k}[x^{k}]\sum_{j=\lceil\frac{k}{2}\rceil}^{k}\left(\frac{x(1+x)}{\alpha}\right)^{j}\frac{1}{j}$
$\displaystyle=$
$\displaystyle\alpha^{k}[x^{k}]\sum_{j=1}^{\infty}\left(\frac{x(1+x)}{\alpha}\right)^{j}\frac{1}{j}$
$\displaystyle=$
$\displaystyle-\alpha^{k}[x^{k}]\log\left(1-\frac{x(1+x)}{\alpha}\right)$
$\displaystyle=$
$\displaystyle-\alpha^{k}[x^{k}]\log\left(\left(1-\frac{x}{\frac{\sqrt{1+4\alpha}-1}{2}}\right)\left(1+\frac{x}{\frac{1+\sqrt{1+4\alpha}}{2}}\right)\right)$
$\displaystyle=$
$\displaystyle-\alpha^{k}\frac{(-1)^{k-1}}{k}\left[\left(\frac{2}{1-\sqrt{1+4\alpha}}\right)^{k}+\left(\frac{2}{\sqrt{1+4\alpha}+1}\right)^{k}\right]$
$\displaystyle=$
$\displaystyle\frac{(-1)^{k}}{k}\frac{\beta^{k}+(\beta-1)^{k}}{(1-2\beta)^{k}}$

Then the lemma follows. ∎

Hence by (4.2) and Lemma 4.1 we have

(4.3) $\displaystyle\mathbb{E}(C_{k}|M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta})\approx\frac{(d-1)^{k}(l-1)^{k}}{2k}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right):=\mu_{\beta,k}.$

######  Lemma 4.2.

Let $g\geq 1$ be a positive integer; $k_{1},\ldots,k_{g}\geq 1$ be positive
integers, and $r_{1},\ldots,r_{g}\geq 1$ be nonnegative integers. Let
$\beta\in\left(0,\frac{1}{d}\right)$. Let $M_{0}\subset E$ and
$|M_{0}|=m\beta$. Let
$N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}$ be the number of
$(d,l)$-regular hypergraphs with $m$ hyperedges satisfying all the following
conditions:

  * •

$M_{0}$ is a matching; and

  * •

The hypergraph contains $r_{i}$ labeled $k_{i}$-cycles; i.e., we can find
$r_{i}$ $k_{i}$ cycles in the hypergraph and label them by $1,2,\ldots,r_{i}$;
different labelings of the same choice of $r_{i}$ $k$-cycles are counted
differently; and

  * •

Any two cycles among the $r_{1}$ $k_{1}$-cycles, $r_{2}$ $k_{2}$-cycles,…,
$r_{g}$ $k_{g}$ cycles are disjoint.

Let $N_{M_{0}}$ be the number of $(d,l)$-regular hypergraphs such that $M_{0}$
is a matching. Then for fixed
$g,(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g})$, let
$m\rightarrow\infty$,

$\displaystyle\frac{N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}}{N_{M_{0}}}$
$\displaystyle\approx$
$\displaystyle\prod_{i=1}^{g}\left(\mu_{\beta,k_{i}}\right)^{r_{i}}$

###### Proof.

The total number of $(d,l)$-regular hypergraphs such that $M_{0}$ is a
matching is given by

$\displaystyle
N_{M_{0}}=\frac{(lm(1-\beta))!}{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}$

We shall prove by induction. First we consider the case when $g=1$ and
$r_{1}=1$. We have

$\displaystyle
N^{*}_{(1,k_{1}),1}\frac{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}{(lm(1-\beta))!}=\sum_{t=0}^{\lfloor\frac{k_{1}}{2}\rfloor}\sum_{s=0}^{k_{1}-2t}E_{\beta,k_{1}}(t,s)$

where $t$ is the number of common hyperedges of the distinguished $k_{1}$
cycle and $M_{0}$, and $s$ is the number of common vertices of the
distinguished $k$ cycle and $M_{0}$ not incident to a common hyperedge of the
cycle and $M_{0}$.

Fix $k_{1},d,l$ and let $m\rightarrow\infty$, by Lemma 4.1 we have

(4.4) $\displaystyle
N^{*}_{(1,k_{1}),1}(s,t)\frac{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}{(lm(1-\beta))!}$
$\displaystyle\approx$ $\displaystyle\mu_{\beta,k_{1}}$

with $\mu_{\beta,k}$ given by (4.3).

Note also that

$\displaystyle N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g}+1,k_{g}),1}$
$\displaystyle=$
$\displaystyle\sum_{t_{1,1}=0}^{\lfloor\frac{k_{1}}{2}\rfloor}\sum_{s_{1,1}=0}^{k_{1}-2t_{1,1}}\ldots\sum_{t_{1,r_{1}}=0}^{\lfloor\frac{k_{1}}{2}\rfloor}\sum_{s_{1,r_{1}}=0}^{k_{1}-2t_{1,r_{1}}}\ldots\sum_{t_{g,1}=0}^{\lfloor\frac{k_{g}}{2}\rfloor}\sum_{s_{g,1}=0}^{k_{g}-2t_{g,1}}\ldots\sum_{t_{g,r_{g}+1}=0}^{\lfloor\frac{k_{g}}{2}\rfloor}\sum_{s_{g,r_{g}+1}=0}^{k_{g}-2t_{g,r_{g}+1}}$
$\displaystyle
N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}+1},t_{g,r_{g}+1}))$

where

$\displaystyle
N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}+1},t_{g,r_{g}+1}))=N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}},t_{g,r_{g}}))$
$\displaystyle\frac{(lm-lm\beta
d-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})d)!}{(lm-
lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(2k_{i}-2t_{i,j}))!}$
$\displaystyle\frac{d^{\frac{lm}{d}-lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})}(\frac{lm}{d}-lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j}))!}{(lm-
lm\beta d-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})d)!}$
$\displaystyle\left[{m\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}t_{i,j}\choose
t_{g,r_{g}+1}}\frac{(t_{g,r_{g}+1}-1)!}{2!}[l(l-1)]^{t_{g,r_{g}+1}}{k_{g}-t_{g,r_{g}+1}-1\choose
t_{g,r_{g}+1}-1}\right]$
$\displaystyle\left[{m-m\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-t_{i,j})\choose
k_{g}-t_{g,r_{g}+1}}(k_{g}-t_{g,r_{g}+1})![l(l-1)]^{k_{g}-t_{g,r_{g}+1}}\right](d-1)^{k_{g}}(d-2)^{s_{g,r_{g}+1}}$
$\displaystyle{lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(2t_{i,j}+s_{i,j})-2t_{g,r_{g}+1}\choose
s_{g,r_{g}+1}}{k_{g}-2t_{g,r_{g}+1}\choose s_{g,r_{g}+1}}(s_{g,r_{g}+1})!$
$\displaystyle\frac{(lm-
lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(2k_{i}-2t_{i,j})-(2k_{g}-2t_{g,r_{g}+1}))!}{(Ad)!}\frac{(Ad)!}{d^{A}A!}$

with

$\displaystyle
A:=\frac{lm}{d}-lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})-(k_{g}-2t_{g,r_{g}+1}-s_{g,r_{g}+1}).$

Here for $1\leq i\leq g$ and $1\leq j\leq r_{i}+1$, $t_{i,j}$ is the number of
common hyperedges of $k_{i}$ cycle labeled by $j$ and $M_{0}$, and $s_{i,j}$
is the number of common vertices of the $k_{i}$ cycle labeled by $j$ and
$M_{0}$ not incident to a common hyperedge of the cycle and $M_{0}$.

Fix $r_{1},k_{1},\ldots,r_{g},k_{g},d,l$ and let $m\rightarrow\infty$, we
obtain

$\displaystyle
N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}+1},t_{g,r_{g}+1}))\frac{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}{(lm(1-\beta))!}$
$\displaystyle\approx$ $\displaystyle
N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}},t_{g,r_{g}}))\frac{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}{(lm(1-\beta))!}$
$\displaystyle\times\frac{(d-1)^{k_{g}}(l-1)^{k_{g}}\beta^{t_{g,r_{g}+1}+s_{g,r_{g}+1}}(1-d\beta)^{k_{g}-2t_{g,r_{g}+1}-s_{g,r_{g}+1}}(d-2)^{s_{g},r_{g}+1}}{2(k_{g}-t_{g,r_{g}+1)}(1-\beta)^{k_{g}-t_{g,r_{g}+1}}}$
$\displaystyle{k_{g}-t_{g,r_{g}+1}\choose
t_{g,r_{g}+1}}{k_{g}-2t_{g,r_{g}+1}\choose s_{g,r_{g}+1}}$ $\displaystyle=$
$\displaystyle
N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}},t_{g,r_{g}}))\frac{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}{(lm(1-\beta))!}E_{\beta,k_{g}}(t_{g,r_{g}+1},s_{g,r_{g}+1})$

Moreover,

$\displaystyle
N^{*}_{(r_{1},k_{1}),\ldots,(r_{g},k_{g}),(1,k_{g+1})1}=\sum_{t_{1,1}=0}^{\lfloor\frac{k_{1}}{2}\rfloor}\sum_{s_{1,1}=0}^{k_{1}-2t_{1,1}}\ldots\sum_{t_{1,r_{1}}=0}^{\lfloor\frac{k_{1}}{2}\rfloor}\sum_{s_{1,r_{1}}=0}^{k_{1}-2t_{1,r_{1}}}\ldots\sum_{t_{g,1}=0}^{\lfloor\frac{k_{g}}{2}\rfloor}\sum_{s_{g,1}=0}^{k_{g}-2t_{g,1}}\ldots\sum_{t_{g,r_{g}}=0}^{\lfloor\frac{k_{g}}{2}\rfloor}\sum_{s_{g,r_{g}}=0}^{k_{g}-2t_{g,r_{g}}}$
$\displaystyle\sum_{t_{g+1,1}=0}^{\lfloor\frac{k_{g+1}}{2}\rfloor}\sum_{s_{g+1,1}=0}^{k_{g+1}-2t_{g+1,1}}N^{*}_{(r_{1},k_{1}),\ldots,(r_{g},k_{g}),(1,k_{g+1}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}},t_{g,r_{g}})),(s_{g+1,1},t_{g+1,1})$

where

$\displaystyle
N^{*}_{(r_{1},k_{1}),\ldots,(r_{g},k_{g}),(1,k_{g+1}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}},t_{g,r_{g}}),(s_{g+1,1},t_{g+1,1}))$
$\displaystyle=N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}},t_{g,r_{g}}))\frac{(lm-
lm\beta d-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})d)!}{(lm-
lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(2k_{i}-2t_{i,j}))!}$
$\displaystyle\frac{d^{\frac{lm}{d}-lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})}(\frac{lm}{d}-lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j}))!}{(lm-
lm\beta d-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})d)!}$
$\displaystyle\left[{m\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}t_{i,j}\choose
t_{g+1,1}}\frac{(t_{g+1,1}-1)!}{2!}[l(l-1)]^{t_{g+1,1}}{k_{g+1}-t_{g+1,1}-1\choose
t_{g+1,1}-1}\right]$
$\displaystyle\left[{m-m\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-t_{i,j})\choose
k_{g+1}-t_{g+1,1}}(k_{g+1}-t_{g+1,1})![l(l-1)]^{k_{g+1}-t_{g+1,1}}\right](d-1)^{k_{g+1}}(d-2)^{s_{g+1,1}}$
$\displaystyle{lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(2t_{i,j}+s_{i,j})-2t_{g+1,1}\choose
s_{g+1,1}}{k_{g+1}-2t_{g+1,1}\choose s_{g+1,1}}(s_{g+1,1})!$
$\displaystyle\frac{(lm-
lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(2k_{i}-2t_{i,j})-(2k_{g+1}-2t_{g+1,1}))!}{(dB)!}\frac{(dB)!}{d^{B}B!}$

with

$\displaystyle
B=\frac{lm}{d}-lm\beta-\sum_{i=1}^{g}\sum_{j=1}^{r_{i}}(k_{i}-2t_{i,j}-s_{i,j})-(k_{g+1}-2t_{g+1,1}-s_{g+1,1})$

Similarly we obtain that for any fixed $r_{1},k_{1},\ldots,r_{g},k_{g},d,l$
and let $m\rightarrow\infty$,

$\displaystyle
N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}((s_{1,1},t_{1,1}),\ldots,(s_{g,r_{g}},t_{g,r_{g}}))\frac{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}{(lm(1-\beta))!}\approx\prod_{i=1}^{g}\prod_{j=1}^{r_{i}}E_{\beta,k_{i}}(t_{i,j},s_{i,j})$

Therefore for any fixed $r_{1},k_{1},\ldots,r_{g},k_{g},d,l$ and let
$m\rightarrow\infty$, by (4.4) and Lemma 4.1 we obtain

$\displaystyle
N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}\frac{d^{\frac{lm}{d}\left(1-d\beta\right)}\left(\frac{lm}{d}(1-d\beta)\right)!}{(lm(1-\beta))!}$
$\displaystyle\approx$
$\displaystyle\prod_{i=1}^{g}\prod_{j=1}^{r_{i}}\left(\sum_{t_{i,j}=0}^{\lfloor\frac{k_{i}}{2}\rfloor}\sum_{s_{i,j}=1}^{k_{i}-2_{t_{i,j}}}E_{\beta,k_{i}}(t_{i,j},s_{i,j})\right)$
$\displaystyle\approx$
$\displaystyle\prod_{i=1}^{g}\left(\mu_{\beta,k_{i}}\right)^{r_{i}}$

Then the lemma follows. ∎

######  Lemma 4.3.

Let $g,k_{1},\ldots,k_{g},r_{1},\ldots,r_{g},\beta,M_{0}$ be given as in Lemma
4.2.

Let
$N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),2}$ be the number of
$(d,l)$-regular hypergraphs with $m$ hyperedges satisfying all the following
conditions:

  * •

$M_{0}$ is a matching; and

  * •

The hypergraph contains precisely $r_{i}$ $k_{i}$-cycles.

Then for any fixed $r_{1},k_{1},\ldots,r_{g},k_{g},d,l$ and let
$m\rightarrow\infty$, we have

$\displaystyle\lim_{m\rightarrow\infty}\frac{N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),2}}{N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}}=0.$

###### Proof.

Note that the total number of vertices in a $(d,l)$-regular hypergraph with
$m$ hyperedges is $\frac{lm}{d}$. It is straightforward to check that for any
fixed $r_{1},k_{1},\ldots,r_{g},k_{g},d,l$ and let $m\rightarrow\infty$,

$\displaystyle\frac{N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),2}}{N^{*}_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g}),1}}=O\left(\frac{d}{lm}\right).$

Then the lemma follows. ∎

######  Lemma 4.4.

  1. (1)

When $m\rightarrow\infty$, for fixed $b\in{\mathbb{N}}$, $C_{1},\ldots,C_{b}$
are independent Poisson random variables with means given by

(4.5)
$\displaystyle\mathbb{E}(C_{k})=\frac{(d-1)^{k}(l-1)^{k}}{2k}:=\lambda_{k},\
\forall k\in[b].$

  2. (2)

Let $M_{0}\subset E$ and $|M_{0}|=m\beta$. Conditional on $M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta}$, when $m\rightarrow\infty$, for fixed
$b\in{\mathbb{N}}$, $C_{1},\ldots,C_{b}$ are independent Poisson random
variables with means given by (4.3) for $k\in[b]$.

###### Proof.

Note that Part (1) of the Lemma when $l=2$ was given by Lemma 1 of [23]; see
also [25]. We only prove Part(2) here; Part (1) can be proved similarly.

Let $g,k_{1},\ldots,k_{g},r_{1},\ldots,r_{g},N_{M_{0}}$ be given as in Lemma
4.2. Let $N_{(r_{1},k_{1}),(r_{2},k_{2}),\ldots,(r_{g},k_{g})}$ be the number
of $(d,l)$-regular hypergraphs with $m$ hyperedges satisfying all the
following conditions:

  * •

$M_{0}$ is a matching; and

  * •

The hypergraph contains $r_{i}$ labeled $k_{i}$-cycles; and

  * •

at least two cycles among the $r_{1}$ $k_{1}$-cycles, $r_{2}$
$k_{2}$-cycles,…, $r_{g}$ $k_{g}$ cycles share a vertex.

Then by the inclusion-exclusion principle,

$\displaystyle\frac{1}{N_{M_{0}}}\left|N_{(r_{1},k_{1}),\ldots,(r_{g},k_{g})}-\sum_{s_{1}=r_{1}}^{u_{1}-1}\ldots\sum_{s_{g}=r_{g}}^{u_{g}-1}\left[\prod_{i=1}^{g}\frac{(-1)^{s_{i}-r_{i}}}{s_{i}!}{s_{i}\choose
r_{i}}\right]\left(N^{*}_{(s_{1},k_{1}),\ldots,(s_{g},k_{g}),1}+N^{*}_{(s_{1},k_{1}),\ldots,(s_{g},k_{g}),2}\right)\right|$
$\displaystyle\leq\frac{1}{N_{M_{0}}}\left[\prod_{i=1}^{g}\frac{(-1)^{s_{i}-t_{i}}}{u_{i}!}{u_{i}\choose
r_{i}}\right]\left(N^{*}_{(u_{1},k_{1}),\ldots,(u_{g},k_{g}),1}+N^{*}_{(u_{1},k_{1}),\ldots,(u_{g},k_{g}),2}\right).$

By Lemmas 4.2 and 4.3, for any fixed $r_{1},k_{1},\ldots,r_{g},k_{g},d,l$ and
let $m\rightarrow\infty$, by (4.4) we have

$\displaystyle\mathbb{P}(C_{k_{1}}=r_{1},\ldots,C_{k_{g}}=r_{g}|M_{0}\in
Q_{\mathcal{G}_{m,d,l},\beta})=\frac{N_{(r_{1},k_{1}),\ldots,(r_{g},k_{g})}}{N_{M_{0}}}\approx\prod_{i=1}^{g}\frac{e^{-\mu_{\beta,k_{i}}}\mu_{\beta,k_{i}}^{r_{i}}}{r_{i}!}$

Then the lemma follows. ∎

Let $\mathbf{c}=(c_{1},\ldots,c_{b})\in{\mathbb{Z}}^{b}$ be a $b$ tuple of
non-negative integers. Define

$\displaystyle p_{\mathbf{c}}:=\mathbb{P}((C_{1},\ldots,C_{b})=\mathbf{c});$

i.e., $p_{\mathbf{c}}$ is the probability that in a random $(d,l)$-regular
hypergraph with $m$ hyperedges, there are exactly $c_{k}$ $k$-cycles for all
$k\in[b]$. Then by Lemma 4.4(1), when $m\rightarrow\infty$,

$\displaystyle p_{\mathbf{c}}$ $\displaystyle\approx$
$\displaystyle\prod_{k=1}^{b}\frac{e^{-\lambda_{k}}(\lambda_{k})^{c_{k}}}{(c_{k})!}$

Then by Lemma 4.4, when $m$ is sufficiently large

(4.6) $\displaystyle E_{\beta,\mathbf{c}}$ $\displaystyle\approx$
$\displaystyle\left(\prod_{k=1}^{b}e^{\lambda_{k}-\mu_{\beta,k}}\left(\frac{\mu_{\beta,k}}{\lambda_{k}}\right)^{c_{k}}\right)\mathbb{E}Z_{m\beta}$

Recall the following lemma about Poisson distributions:

######  Lemma 4.5.

Let $X$ has Poisson distritubion with mean $\mu$. Then

$\displaystyle\mathbb{P}\left(X<\mu(1-\epsilon)\right)\leq
e^{-\frac{\mu\epsilon^{2}}{2}}$
$\displaystyle\mathbb{P}\left(X>\mu(1+\epsilon)\right)\leq\left[e^{\epsilon}(1+\epsilon)^{-(1+\epsilon)}\right]^{\mu}$

###### Proof.

See Theorem A.15 of [3]. ∎

######  Lemma 4.6.

Let $a>0$ be a positive constant. Then for any positive constant $W>2$,

(4.7)
$\displaystyle\left(\frac{e^{\frac{y}{a\lambda_{k}^{\frac{1}{2}}}}}{\left(1+\frac{y}{a\lambda_{k}^{\frac{1}{2}}}\right)^{1+\frac{y}{a\lambda_{k}^{\frac{1}{2}}}}}\right)^{\lambda_{k}}\leq
e^{-\frac{y^{2}}{4a^{2}}}+e^{-\left|\phi\left(\frac{1}{2}\right)\right|\frac{y^{2}}{a^{2}W^{2}}}+e^{-\left(\log\left(1+W\right)-1\right)\frac{y\lambda_{k}^{\frac{1}{2}}}{a}};$

where

$\displaystyle\phi(z):=z-(1+z)\log(1+z).$

###### Proof.

We use $L$ to denote the left hand side of (4.7). Note that

(4.8)
$\displaystyle\frac{e^{\frac{y}{a\lambda_{k}^{\frac{1}{2}}}}}{\left(1+\frac{y}{a\lambda_{k}^{\frac{1}{2}}}\right)^{1+\frac{y}{a\lambda_{k}^{\frac{1}{2}}}}}=e^{\frac{y}{a\lambda_{k}^{\frac{1}{2}}}-\left(1+\frac{y}{a\lambda_{k}^{\frac{1}{2}}}\right)\log\left(1+\frac{y}{a\lambda_{k}^{\frac{1}{2}}}\right)}.$

Consider the following cases:

  1. (1)

$\frac{y}{a\lambda_{k}^{\frac{1}{2}}}\in\left(0,\frac{1}{2}\right]$: note that

$\displaystyle\log\left(1+z\right)\geq z-\frac{z^{2}}{2},\forall
z\in\left(0,\frac{1}{2}\right)$

Let $z=\frac{y}{a\lambda_{k}^{\frac{1}{2}}}$, we obtain

$\displaystyle e^{z-(1+z)\log(1+z)}\leq
e^{-\left(\frac{z^{2}}{2}-\frac{z^{3}}{2}\right)}$

and therefore

$\displaystyle L\leq
e^{-\left(\frac{y^{2}}{2a^{2}}-\frac{y^{3}}{2a^{3}\lambda_{k}^{\frac{1}{2}}}\right)}\leq
e^{-\frac{y^{2}}{4a^{2}}}$

where the last inequality follows from the fact that
$\frac{y}{a\lambda_{k}^{\frac{1}{2}}}\in\left(0,\frac{1}{2}\right]$.

  2. (2)

$\frac{y}{a\lambda_{k}^{\frac{1}{2}}}\in\left(\frac{1}{2},W\right]$, where
$W>2$ is a positive constant: note that

$\displaystyle\phi^{\prime}(z)=-\log(z+1)<0,\ \forall z>0$

Therefore

$\displaystyle\sup_{z\in\left(\frac{1}{2},2\right]}\phi(z)=\phi\left(\frac{1}{2}\right)=\frac{1}{2}-\frac{3}{2}\log\left(\frac{3}{2}\right)<0$

Then by (4.8) we obtain

$\displaystyle L\leq
e^{-\left|\phi\left(\frac{1}{2}\right)\right|\frac{y^{2}}{a^{2}W^{2}}}$

  3. (3)

$\frac{y}{a\lambda_{k}^{\frac{1}{2}}}>W>2$: we have

$\displaystyle z-(1+z)\log(1+z)\leq-z(\log(1+z)-1)<0,\ \forall z>2$

Again by (4.8), we have

$\displaystyle L\leq
e^{-\left(\log\left(1+W\right)-1\right)\frac{y\lambda_{k}^{\frac{1}{2}}}{a}}$

∎

######  Lemma 4.7.

Assume $\beta\in\left(0,\frac{1}{d}\right)$, $l\leq d$ and $d\geq 3$ For
$y>0$, define

(4.9) $\displaystyle
S(y):=\\{\mathbf{c}\in{\mathbb{N}}^{b}:|c_{k}-\lambda_{k}|\leq
y\lambda_{k}^{\frac{1}{2}},\ \forall k\in[b]\\}.$

Then for all sufficiently large $y$, and any constant $W>2$

$\displaystyle\sum_{\mathbf{c}\in
S(y)}p_{\mathbf{c}}{E}_{\beta,\mathbf{c}}^{2}$ $\displaystyle\geq$
$\displaystyle\left[1-be^{-\left(\frac{d-2}{d-1}\right)^{2}\frac{y^{2}}{8}}-be^{-\frac{y^{2}}{16}\left(\frac{d-2}{d-1}\right)^{2}}-be^{-\frac{\left|\phi\left(\frac{1}{2}\right)\right|y^{2}}{4W^{2}}\left(\frac{d-2}{d-1}\right)^{2}}-be^{-\left(\log\left(1+W\right)-1\right)\frac{y}{2}\left(\frac{d-2}{d-1}\right)^{2}}\right]$
$\displaystyle\times\left(1-\left(\frac{(l-1)(d-1)\beta^{2}}{(1-\beta)^{2}}\right)^{b}\right)\frac{1-\beta}{\sqrt{1-2\beta-(dl-
d-l)\beta^{2}}}(\mathbb{E}Z_{m\beta})^{2}$

###### Proof.

Note that by (4.6),

(4.10) $\displaystyle\sum_{\mathbf{c}\in
S(y)}p_{\mathbf{c}}{E}_{\beta,\mathbf{c}}^{2}$ $\displaystyle\approx$
$\displaystyle\left(\mathbb{E}Z_{m\beta}\right)^{2}\sum_{\mathbf{c}\in
S(y)}\prod_{k=1}^{b}\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)^{c_{k}}\frac{e^{\lambda_{k}-2\mu_{\beta,k}}}{(c_{k})!}$
$\displaystyle=$
$\displaystyle\left(\mathbb{E}Z_{m\beta}\right)^{2}\prod_{k=1}^{b}\left[\sum_{c_{k}:|c_{k}-\lambda_{k}|\leq
y\lambda_{k}^{\frac{1}{2}}}\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)^{c_{k}}\frac{e^{\lambda_{k}-2\mu_{\beta,k}}}{(c_{k})!}\right]$
$\displaystyle=$
$\displaystyle\left(\mathbb{E}Z_{m\beta}\right)^{2}\prod_{k=1}^{b}e^{\frac{(\mu_{\beta,k}-\lambda_{k})^{2}}{\lambda_{k}}}\left[1-e^{-\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}}\sum_{c_{k}:|c_{k}-\lambda_{k}|>y\lambda_{k}^{\frac{1}{2}}}\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)^{c_{k}}\frac{1}{(c_{k})!}\right]$

From (4.3), (4.5) we see that

$\displaystyle\mu_{\beta,k}=\lambda_{k}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)$

Hence

(4.11)
$\displaystyle\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}=\lambda_{k}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)^{2}=\mu_{\beta,k}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)$

Let $X_{k}$ be a Poisson random variable with parameter
$\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}$. Assume

$\displaystyle\lambda_{k}-y\lambda_{k}^{\frac{1}{2}}=(1-u_{k})\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right);\qquad\lambda_{k}+y\lambda_{k}^{\frac{1}{2}}=(1+v_{k})\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right).$

Here

(4.12) $\displaystyle u_{k},v_{k}>\frac{y}{2\lambda_{k}^{1/2}}$

when $y$ is sufficiently large. Then by Lemma 4.5

$\displaystyle\sum_{c_{k}=0}^{(1-u_{k})\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)}\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)^{c_{k}}\frac{e^{-\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}}}{c_{k}!}$
$\displaystyle=$
$\displaystyle\mathbb{P}\left(X_{k}\leq(1-u_{k})\mathbb{E}X_{k}\right)\leq
e^{-\frac{u_{k}^{2}\mu_{\beta,k}^{2}}{2\lambda_{k}}}$

By (4.11) and (4.12) and $\beta\in\left(0,\frac{1}{d}\right)$ we obtain

$\displaystyle\sum_{c_{k}=0}^{(1-u_{k})\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)}\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)^{c_{k}}\frac{e^{-\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}}}{c_{k}!}\leq
e^{-\frac{y^{2}}{8}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)^{2}}\leq
e^{-\frac{y^{2}}{8}\left(\frac{d-2}{d-1}\right)^{2}}$

Similarly by Lemma 4.5,

$\displaystyle\sum_{c_{k}=(1+v_{k})\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)}^{\infty}\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)^{c_{k}}\frac{e^{-\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}}}{c_{k}!}=\mathbb{P}(X_{k}\geq(1+v_{k})\mathbb{E}X_{k})\leq\left(\frac{e^{v_{k}}}{(1+v_{k})^{1+v_{k}}}\right)^{\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}}$

When $v_{k}$ is sufficiently large,

$\displaystyle\frac{d}{dv_{k}}\frac{e^{v_{k}}}{(1+v_{k})^{v_{k}}}<0,\qquad\frac{e^{v_{k}}}{(1+v_{k})^{1+v_{k}}}<1.$

Again by (4.12) and (4.11) we have

(4.13)
$\displaystyle\sum_{c_{k}=(1+v_{k})\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)}^{\infty}\left(\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}\right)^{c_{k}}\frac{e^{-\frac{\mu_{\beta,k}^{2}}{\lambda_{k}}}}{c_{k}!}\leq\left(\frac{e^{\frac{y}{2\lambda_{k}^{\frac{1}{2}}}}}{\left(1+\frac{y}{2\lambda_{k}^{\frac{1}{2}}}\right)^{1+\frac{y}{2\lambda_{k}^{\frac{1}{2}}}}}\right)^{\lambda_{k}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)^{2}}$

We shall apply (4.7) with $a=2$.

By (4.10) we obtain

$\displaystyle\sum_{\mathbf{c}\in
S(y)}p_{\mathbf{c}}{E}_{\beta,\mathbf{c}}^{2}$ $\displaystyle\geq$
$\displaystyle\left[1-be^{-\left(\frac{d-2}{d-1}\right)^{2}\frac{y^{2}}{8}}-be^{-\frac{y^{2}}{16}\left(\frac{d-2}{d-1}\right)^{2}}-be^{-\frac{\left|\phi\left(\frac{1}{2}\right)\right|y^{2}}{4W^{2}}\left(\frac{d-2}{d-1}\right)^{2}}-be^{-\left(\log\left(1+W\right)-1\right)\frac{y}{2}\left(\frac{d-2}{d-1}\right)^{2}}\right]$
$\displaystyle\times\left(\mathbb{E}Z_{m\beta}\right)^{2}\prod_{k=1}^{b}e^{\frac{(\mu_{\beta,k}-\lambda_{k})^{2}}{\lambda_{k}}}$

Moreover, since $\beta\in\left(0,\frac{1}{d}\right)$, when $l\leq d$ we have

$\displaystyle\prod_{k=b+1}^{\infty}e^{\frac{(\mu_{\beta,k}-\lambda_{k})^{2}}{\lambda_{k}}}$
$\displaystyle=$ $\displaystyle
e^{\sum_{k=b+1}^{\infty}\frac{\beta^{2k}}{(1-\beta)^{2k}}\frac{(d-1)^{k}(l-1)^{k}}{2k}}\leq\left(1-\left(\frac{(l-1)(d-1)\beta^{2}}{(1-\beta)^{2}}\right)^{b}\right)^{-1}$

Let

$\displaystyle\Theta:=1-be^{-\left(\frac{d-2}{d-1}\right)^{2}\frac{y^{2}}{8}}-be^{-\frac{y^{2}}{16}\left(\frac{d-2}{d-1}\right)^{2}}-be^{-\frac{\left|\phi\left(\frac{1}{2}\right)\right|y^{2}}{4W^{2}}\left(\frac{d-2}{d-1}\right)^{2}}-be^{-\left(\log\left(1+W\right)-1\right)\frac{y}{2}\left(\frac{d-2}{d-1}\right)^{2}}$

Hence

$\displaystyle\sum_{\mathbf{c}\in
S(y)}p_{\mathbf{c}}{E}_{\beta,\mathbf{c}}^{2}$ $\displaystyle\geq$
$\displaystyle\left(\mathbb{E}Z_{m\beta}\right)^{2}\Theta\prod_{k=1}^{\infty}e^{\frac{(\mu_{\beta,k}-\lambda_{k})^{2}}{\lambda_{k}}}\left(\prod_{k=b+1}^{\infty}e^{\frac{(\mu_{\beta,k}-\lambda_{k})^{2}}{\lambda_{k}}}\right)^{-1}$
$\displaystyle\geq$
$\displaystyle\left(\mathbb{E}Z_{m\beta}\right)^{2}\Theta\left(1-\left(\frac{(l-1)(d-1)\beta^{2}}{(1-\beta)^{2}}\right)^{b}\right)e^{\sum_{k=1}^{\infty}\frac{\beta^{2k}(d-1)^{k}(l-1)^{k}}{2k(1-\beta)^{2k}}}$
$\displaystyle=$
$\displaystyle\left(\mathbb{E}Z_{m\beta}\right)^{2}\Theta\left(1-\left(\frac{(l-1)(d-1)\beta^{2}}{(1-\beta)^{2}}\right)^{b}\right)\frac{1-\beta}{\sqrt{1-2\beta-(dl-
d-l)\beta^{2}}}$

Then the lemma follows. ∎

######  Lemma 4.8.

Let $S(y)$ be defined as in (4.9); and $C_{1},\ldots,C_{b}$ be random
variables denoting the number of 1-cycles, …, $b$-cycles in a random
$(d,l)$-regular hypergraph with $m$ hyperedges. Let

$\displaystyle\overline{p}:=\mathbb{P}\left((C_{1},\ldots,C_{b})\notin
S(y)\right)$

Then there exists an absolute constant $\theta>0$, such that for all
sufficiently large $y\lambda_{k}^{-\frac{1}{2}}$ and $m$, and for any constant
$W>2$,

$\displaystyle\overline{p}\leq
be^{-\frac{y^{2}}{2}}+be^{-\frac{y^{2}}{4}}+be^{-\left|\phi\left(\frac{1}{2}\right)\right|\frac{y^{2}}{W^{2}}}+be^{-\left(\log\left(1+W\right)-1\right)y\lambda_{k}^{\frac{1}{2}}}$

###### Proof.

Recall that as $m\rightarrow\infty$, $C_{1},\ldots,C_{b}$ are independent
Poisson random variables with parameters $\lambda_{1},\ldots,\lambda_{b}$,
respectively. When $m$ is sufficiently large, by Lemma 4.5,

$\displaystyle\mathbb{P}\left(C_{k}<\lambda_{k}\left(1-\frac{y}{\lambda_{k}^{\frac{1}{2}}}\right)\right)\leq
e^{-\frac{y^{2}}{2}}$

Also by Lemma 4.5,

$\displaystyle\mathbb{P}\left(C_{k}>\lambda_{k}\left(1+\frac{y}{\lambda_{k}^{\frac{1}{2}}}\right)\right)\leq\left[\frac{e^{y\lambda_{k}^{-\frac{1}{2}}}}{(1+y\lambda_{k}^{-\frac{1}{2}})^{1+{y\lambda_{k}^{-\frac{1}{2}}}}}\right]^{\lambda_{k}}$

By (4.7) when $a=1$, we obtain

$\displaystyle\left[\frac{e^{y\lambda_{k}^{-\frac{1}{2}}}}{(1+y\lambda_{k}^{-\frac{1}{2}})^{1+{y\lambda_{k}^{-\frac{1}{2}}}}}\right]^{\lambda_{k}}\leq
e^{-\frac{y^{2}}{4}}+e^{-\left|\phi\left(\frac{1}{2}\right)\right|\frac{y^{2}}{W^{2}}}+e^{-\left(\log\left(1+W\right)-1\right)y\lambda_{k}^{\frac{1}{2}}}$

Then the lemma follows. ∎

######  Lemma 4.9.

Assume $\beta\in\left(0,\frac{1}{\sqrt{(d-1)(l-1)}+1}\right)$. There exist
constants $A,B>0$ independent of $y$, such that for each $\mathbf{c}\in S(y)$
and sufficiently large $y$,

$\displaystyle E_{\beta,\mathbf{c}}\geq e^{-(A+By)}\mathbb{E}(Z_{m\beta})$

###### Proof.

By (4.6), we obtain

$\displaystyle
E_{\beta,\mathbf{c}}\approx\left[\prod_{k=1}^{b}e^{\frac{(-1)^{k+1}\beta^{k}}{(1-\beta)^{k}}\frac{(d-1)^{k}(l-1)^{k}}{2k}}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)^{c_{k}}\right]\mathbb{E}Z_{m\beta}\geq\mathbb{E}Z_{m\beta}UV^{y}$

where

$\displaystyle U$ $\displaystyle=$
$\displaystyle\prod_{k=1}^{b}e^{\frac{(-1)^{k+1}\beta^{k}}{(1-\beta)^{k}}\frac{(d-1)^{k}(l-1)^{k}}{2k}}\left(1+\frac{(-1)^{k}\beta^{k}}{(1-\beta)^{k}}\right)^{\lambda_{k}}$
$\displaystyle V$ $\displaystyle=$ $\displaystyle\prod_{k\in[b],k\
odd}\left(1-\frac{\beta^{k}}{(1-\beta)^{k}}\right)^{\lambda_{k}^{\frac{1}{2}}}\prod_{k\in[b],k\
even}\left(1+\frac{\beta^{k}}{(1-\beta)^{k}}\right)^{-\lambda_{k}^{\frac{1}{2}}}$

Then

$\displaystyle U$ $\displaystyle=$
$\displaystyle\prod_{k=1}^{b}e^{\frac{(-1)^{k+1}\beta^{k}(d-1)^{k}(l-1)^{k}}{2k(1-\beta)^{k}}+\lambda_{k}\sum_{j=1}^{\infty}\frac{(-1)^{jk+j-1}\beta^{jk}}{j(1-\beta)^{jk}}}$
$\displaystyle\geq$ $\displaystyle
e^{-\sum_{k=1}^{\infty}\frac{\beta^{2k}(d-1)^{k}(l-1)^{k}}{4k(1-\beta)^{2k}}}=\left(\frac{1-2\beta-(dl-
d-l)\beta^{2}}{(1-\beta)^{2}}\right)^{\frac{1}{4}}:=e^{-A}$

and

$\displaystyle
V\geq\prod_{k=1}^{\infty}\left(1-\frac{\beta^{k}}{(1-\beta)^{k}}\right)^{\lambda_{k}^{\frac{1}{2}}}\geq
e^{-\sum_{k=1}^{\infty}\frac{\lambda_{k}^{\frac{1}{2}}}{\frac{(1-\beta)^{k}}{\beta^{k}}-1}}:=e^{-B}$

When $0<\beta<\frac{1}{\sqrt{(d-1)(l-1)}+1}$, we have

$\displaystyle\frac{\beta\sqrt{(d-1)(l-1)}}{(1-\beta)}<1,$

Hence
$\sum_{k=1}^{\infty}\frac{\lambda_{k}^{\frac{1}{2}}}{\frac{(1-\beta)^{k}}{\beta^{k}}-1}$
is convergent. Then the lemma follows. ∎

##  5\. Free Energy

In this section, we show the convergence in probability of the free energy to
an explicit limit when $(\mathbb{E}Z_{m\beta_{*}})^{2}$ and
$\mathbb{E}Z_{m\beta_{*}}^{2}$ have the same exponential growth rate, where
$\beta_{*}$ is the unique root of (1.2).

######  Lemma 5.1.

Let $\beta\in\left(0,\frac{1}{d}\right)$, $l\geq 2$, $d\geq 2$ such that one
of the following conditions holds

  1. (1)

$l=2$; or

  2. (2)

$l\geq 3$ and $\beta\leq L_{1}$.

Then as $m\rightarrow\infty$

$\displaystyle\frac{1}{m}\log Z_{m\beta}\longrightarrow\Phi_{d,l}(\beta)$

in probability.

###### Proof.

By (2.3), it suffices to show that

(5.1)
$\displaystyle\lim_{m\rightarrow\infty}\mathbb{P}\left(\frac{1}{m}\left|\log\frac{Z_{m\beta}}{\mathbb{E}Z_{m\beta}}\right|>\epsilon\right)=0.$

for all $\epsilon>0$.

Let

$\displaystyle\mathbf{C}=(C_{1},C_{2},\ldots,C_{b})$

be the random variable denoting the number of 1-cycles, 2-cycles, …,
$b$-cycles in a random $(d,l)$-regular hypergraph with $m$ hyperedges. Let
$E_{\beta,\mathbf{C}}$ be the conditional expectation given by

$\displaystyle E_{\beta,\mathbf{C}}:=\mathbb{E}(Z_{m\beta}|\mathbf{C})$

Then

$\displaystyle\frac{1}{m}\log\frac{Z_{m\beta}}{\mathbb{E}Z_{m\beta}}=\frac{1}{m}\log\frac{Z_{m\beta}}{E_{\beta,\mathbf{C}}}+\frac{1}{m}\log\frac{E_{\beta,\mathbf{C}}}{\mathbb{E}Z_{m\beta}}$

By Chebyshev’s inequality, for any $t>0$

(5.2) $\displaystyle\mathbb{P}(|Z_{m\beta}-E_{\beta,\mathbf{C}}|\geq
t)\leq\frac{\mathbb{E}\left(Z_{m\beta}-E_{\beta,\mathbf{C}}\right)^{2}}{t^{2}}$

By Lemmas 4.7 and 3.13, we obtain

(5.3)
$\displaystyle\mathbb{E}\left(Z_{m\beta}-E_{\beta,\mathbf{C}}\right)^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}Z_{m\beta}^{2}-\mathbb{E}E_{\beta,\mathbf{C}}^{2}$
$\displaystyle=$ $\displaystyle\mathbb{E}Z_{m\beta}^{2}-\sum_{\mathbf{c}\in
S(y)}p_{\mathbf{c}}E_{\beta,\mathbf{c}}^{2}-\sum_{\mathbf{c}\notin
S(y)}p_{\mathbf{c}}E_{\beta,\mathbf{c}}^{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}Z_{m\beta}^{2}\left(be^{-\left(\frac{d-2}{d-1}\right)^{2}\frac{y^{2}}{8}}+be^{-\frac{y\lambda_{k}^{\frac{1}{2}}}{4}\log\left(\frac{y}{2\lambda_{k}^{\frac{1}{2}}}\right)\left(\frac{d-2}{d-1}\right)^{2}}+\left(\frac{l-1}{d-1}\right)^{b}\right)$

Then by Lemma 4.8 we have for any constant $W>2$,

$\displaystyle\mathbb{P}\left(\frac{1}{m}\left|\log\frac{Z_{m\beta}}{E_{\beta,\mathbf{C}}}\right|>\epsilon\right)$
$\displaystyle\leq$ $\displaystyle\mathbb{P}(\mathbf{C}\notin
S(y))+\mathbb{P}\left(\frac{1}{m}\left|\log\frac{Z_{m\beta}}{E_{\beta,\mathbf{C}}}\right|>\epsilon\
\mathrm{and}\ \mathbf{C}\in S(y)\right)$ $\displaystyle\leq$ $\displaystyle
be^{-\frac{y^{2}}{2}}+be^{-\frac{y^{2}}{4}}+be^{-\left|\phi\left(\frac{1}{2}\right)\right|\frac{y^{2}}{W^{2}}}+be^{-\left(\log\left(1+W\right)-1\right)y\lambda_{k}^{\frac{1}{2}}}+P_{1}+P_{2}$

where

$\displaystyle P_{1}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(Z_{m\beta}<E_{\beta,\mathbf{C}}e^{-m\epsilon}\
\mathrm{and}\ \mathbf{C}\in S(y)\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\left(|Z_{m\beta}-E_{\beta,\mathbf{C}}|>(1-e^{-m\epsilon})E_{\beta,\mathbf{C}}\
\mathrm{and}\ \mathbf{C}\in S(y)\right):=P_{3}$ $\displaystyle P_{2}$
$\displaystyle=$
$\displaystyle\mathbb{P}\left(Z_{m\beta}>E_{\beta,\mathbf{C}}e^{m\epsilon}\
\mathrm{and}\ \mathbf{C}\in S(y)\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\left(|Z_{m\beta}-E_{\beta,\mathbf{C}}|>(e^{m\epsilon}-1)E_{\beta,\mathbf{C}}\
\mathrm{and}\ \ \mathbf{C}\in S(y)\right)$

Note that

$\displaystyle P_{2}\leq P_{3}$

when $m$ is sufficiently large. By Lemma 4.9, we have

$\displaystyle
P_{3}\leq\mathbb{P}\left(|Z_{m\beta}-E_{\beta,\mathbf{C}}|>(1-e^{-m\epsilon})e^{-(A+By)}\mathbb{E}Z_{m\beta}\
\mathrm{and}\ \mathbf{C}\in S(y)\right):=P_{4}$

Then by (5.2), (5.3) we obtain

(5.4) $\displaystyle
P_{4}\leq\frac{e^{2A+2By}\mathbb{E}Z_{m\beta}^{2}}{(\mathbb{E}Z_{m\beta})^{2}(1-e^{-m\epsilon})^{2}}\left(1-\Theta+\left(\frac{(l-1)(d-1)\beta^{2}}{(1-\beta)^{2}}\right)^{b}\right)$

where

$\displaystyle
1-\Theta=be^{-\left(\frac{d-2}{d-1}\right)^{2}\frac{y^{2}}{8}}+be^{-\frac{y^{2}}{16}\left(\frac{d-2}{d-1}\right)^{2}}+be^{-\frac{\left|\phi\left(\frac{1}{2}\right)\right|y^{2}}{4W^{2}}\left(\frac{d-2}{d-1}\right)^{2}}-be^{-\left(\log\left(1+W\right)-1\right)\frac{y}{2}\left(\frac{d-2}{d-1}\right)^{2}}$

Note that when $\beta\in\left(0,\frac{1}{d}\right)$, and $l\leq d$,

$\displaystyle\frac{(l-1)(d-1)\beta^{2}}{(1-\beta)^{2}}<1$

Let

$\displaystyle
b:=-\frac{3By}{\log\left(\frac{(l-1)(d-1)\beta^{2}}{(1-\beta)^{2}}\right)}$

and

$\displaystyle\left(\log\left(1+W\right)-1\right)\frac{1}{2}\left(\frac{d-2}{d-1}\right)^{2}\geq
3B$

By Lemma 3.13, as $y\rightarrow\infty$, the right hand side of (5.4) goes to
0. Moreover,

$\displaystyle\mathbb{P}\left(\frac{1}{m}\left|\log\frac{{E_{\beta,\mathbf{C}}}}{\mathbb{E}Z_{m\beta}}\right|>\epsilon\right)$
$\displaystyle\leq$ $\displaystyle P_{5}+P_{6};$

where

$\displaystyle
P_{5}=\mathbb{P}\left(\frac{{E_{\beta,\mathbf{C}}}}{\mathbb{E}Z_{m\beta}}>e^{m\epsilon}\right)\leq
e^{-m\epsilon}\rightarrow 0,$

as $m\rightarrow\infty$; and

$\displaystyle P_{6}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\frac{{E_{\beta,\mathbf{C}}}}{\mathbb{E}Z_{m\beta}}<e^{-m\epsilon}\right)\leq
P_{7}+P_{8}.$

where

$\displaystyle P_{7}$ $\displaystyle=$
$\displaystyle\mathbb{P}(\mathbf{C}\notin S(y));$ $\displaystyle P_{8}$
$\displaystyle=$ $\displaystyle\mathbb{P}(\mathbf{C}\in
S(y))\mathbb{P}(e^{-(A+By)}\leq e^{-m\epsilon}|\mathbf{C}\in S(y)).$

We obtain $P_{7}\rightarrow 0$ as $y\rightarrow\infty$ by Lemma 4.8 and
$P_{8}\rightarrow 0$ as $m\rightarrow 0$ by Lemma 4.9. Then the lemma follows.
∎

It is straightforward to check the following lemma.

######  Lemma 5.2.

Let $L_{1}$ be given by (3.36). If

$\displaystyle\Phi^{\prime}_{d,l}(L_{1})\leq 0;$

Then $\beta_{*}\leq L_{1}$.

Proof of Theorem 1.1(2). By Theorem 1.1(1), it suffices to show that

$\displaystyle\lim_{m\rightarrow\infty}\mathbb{P}\left(\frac{1}{m}\left|\log\frac{Z}{\mathbb{E}Z_{m\beta_{*}}}\right|>\epsilon\right)=0.$

for all $\epsilon>0$. Note that

$\displaystyle\mathbb{P}\left(\frac{1}{m}\left|\log\frac{Z}{\mathbb{E}Z_{m\beta_{*}}}\right|>\epsilon\right)\leq
R_{1}+R_{2}$

where

$\displaystyle R_{1}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\frac{Z}{\mathbb{E}Z_{m\beta_{*}}}>e^{m\epsilon}\right);\qquad
R_{2}=\mathbb{P}\left(\frac{Z}{\mathbb{E}Z_{m\beta_{*}}}<e^{-m\epsilon}\right)$

Note that

$\displaystyle
R_{1}=\mathbb{P}\left(\frac{\sum_{j=1}^{\frac{m}{d}}Z_{j}}{\mathbb{E}Z_{m\beta_{*}}}>e^{m\epsilon}\right)\leq\sum_{j=1}^{\frac{m}{d}}\mathbb{P}\left(\frac{Z_{j}}{\mathbb{E}Z_{m\beta_{*}}}>\frac{1}{m}e^{m\epsilon}\right)\leq\sum_{j=1}^{\frac{m}{d}}\frac{m}{e^{m\epsilon}}\frac{\mathbb{E}Z_{j}}{\mathbb{E}Z_{m\beta_{*}}}\rightarrow
0,$

as $m\rightarrow\infty$, where the limit follows from the fact that

$\displaystyle\lim_{m\rightarrow\infty}\frac{1}{m}\log\mathbb{E}Z_{m\beta_{*}}=\max\left\\{\beta\in\left(0,\frac{1}{d}\right):\lim_{m\rightarrow\infty}\frac{1}{m}\log\mathbb{E}Z_{m\beta}\right\\}.$

Moreover

$\displaystyle R_{2}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\frac{\sum_{j=1}^{\frac{m}{d}}Z_{j}}{\mathbb{E}Z_{m\beta_{*}}}<e^{-m\epsilon}\right)\leq\mathbb{P}\left(\frac{Z_{m\beta_{*}}}{\mathbb{E}Z_{m\beta_{*}}}<e^{-m\epsilon}\right)\rightarrow
0,$

as $m\rightarrow\infty$, where the last limit follows from (5.1). Then the
lemma follows. $\hfill\Box$

##  6\. Weighted Free Energy

In this section, we show the convergence in probability of the weighted energy
to an explicit limit when each hyperedge in the matching is given a
sufficiently small weight $x>0$.

Let $x>0$. Define the weighted partition $Z(x)$ function for matchings on a
$(d,l)$-regular graph as in (1.6). When $\beta\in\left(0,\frac{1}{d}\right)$,
we have

$\displaystyle Z_{m\beta}x^{m\beta}\asymp
m^{-\frac{1}{2}}e^{m\left(\Delta_{d,l}(\beta,x)\right)}$

where

$\displaystyle\Delta_{d,l}(\beta,x)=\Phi_{d,l}(\beta,x)+\beta\ln(x).$

Hence we have

$\displaystyle\frac{\partial\Delta_{d,l}(\beta,x)}{\partial\beta}=\Phi^{\prime}_{d,l}(\beta)+\ln(x)$

and

$\displaystyle\frac{\partial^{2}\Delta_{d,l}(\beta,x)}{\partial\beta^{2}}=\Phi^{\prime\prime}_{d,l}(\beta)<0$

Since

$\displaystyle\lim_{\beta\rightarrow
0+}\frac{\partial\Delta_{d,l}(\beta,x)}{\partial\beta}=\ln(x)+\lim_{\beta\rightarrow
0+}\Phi_{d,l}^{\prime}(\beta)=+\infty$
$\displaystyle\lim_{\beta\rightarrow\frac{1}{d}-}\frac{\partial\Delta_{d,l}(\beta,x)}{\partial\beta}=\ln(x)+\lim_{\beta\rightarrow\frac{1}{d}-}\Phi_{d,l}^{\prime}(\beta)=-\infty$

We obtain that there exists a unique
$\beta_{*}(x)\in\left(0,\frac{1}{d}\right)$, such that

$\displaystyle\left.\frac{\partial\Delta_{d,l}(\beta,x)}{\partial\beta}\right|_{\beta=\beta_{*}(x)}=0$

and

$\displaystyle\Delta_{d,l}(\beta_{*}(x),x)=\max_{\beta\in\left(0,\frac{1}{d}\right)}\Delta_{d,l}(\beta,x)$

and moreover $\beta_{*}(x)$ is the unique maximizer.

Proof of Theorem 1.1(3b). Note that

$\displaystyle\mathbb{P}\left(\frac{1}{m}\left|\log\frac{Z(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)}]}\right|>\epsilon\right)\leq
Q_{1}+Q_{2}$

where

$\displaystyle Q_{1}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\frac{Z(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)]}}>e^{m\epsilon}\right);\qquad
Q_{2}=\mathbb{P}\left(\frac{Z(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)]}}<e^{-m\epsilon}\right)$

Note that

$\displaystyle Q_{1}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\frac{\sum_{j=1}^{\frac{m}{d}}Z_{j}(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)}]}>e^{m\epsilon}\right)\leq\sum_{j=1}^{\frac{m}{d}}\mathbb{P}\left(\frac{Z_{j}(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)]}}>\frac{1}{m}e^{m\epsilon}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{\frac{m}{d}}\frac{m}{e^{m\epsilon}}\frac{\mathbb{E}Z_{j}(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)]}}\rightarrow
0,$

as $m\rightarrow\infty$, Where the limit follows from the fact that

$\displaystyle\lim_{m\rightarrow\infty}\frac{1}{m}\log\mathbb{E}Z_{m\beta_{*}(x)}(x)=\max\left\\{\beta\in\left(0,\frac{1}{d}\right):\lim_{m\rightarrow\infty}\frac{1}{m}\log\mathbb{E}Z_{m\beta}(x)\right\\}.$

If $\Phi^{\prime}_{d,l}(L_{1})+\ln(x)\leq 0$, then

(6.1) $\displaystyle\beta_{*}(x)\leq L_{1}.$

Moreover

$\displaystyle Q_{2}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\frac{\sum_{j=1}^{\frac{m}{d}}Z_{j}(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)]}}<e^{-m\epsilon}\right)\leq\mathbb{P}\left(\frac{Z_{m\beta_{*}(x)}(x)}{e^{m[\Phi_{d,l}(\beta_{*}(x))+\beta_{*}(x)\ln(x)]}}<e^{-m\epsilon}\right)$
$\displaystyle=$
$\displaystyle\mathbb{P}\left(\frac{Z_{m\beta_{*}(x)}}{e^{m[\Phi_{d,l}(\beta_{*}(x))]}}<e^{-m\epsilon}\right)\rightarrow
0,$

as $m\rightarrow\infty$, where the last limit follows from (5.1) and (6.1).
Then the lemma follows. $\hfill\Box$

##  7\. Another Criterion to Guarantee Global Maxima

######  Lemma 7.1.

Assume $d\geq 2$, $l\geq 3$ and $0<\beta d<1$. For any straight line in the
$(\rho,\eta)$-plane passing through $(\beta^{2},(d-1)\beta^{2})$ with slope in
$s\in(-\infty,-1]$, the second order directional derivative of $\Psi_{d,l}$
along the line is strictly negative when
$\rho\in\left(\beta^{2},\frac{(d-1-s)\beta^{2}}{-s}\right)$ and

(7.1) $\displaystyle\beta<\frac{dl+l^{2}-2l-d+1}{2dl^{2}-dl}$

###### Proof.

Let $s\in(-\infty,-1]$. It suffices to show that under the assumptions of the
lemma,

$\displaystyle
Y(s):=\frac{\partial^{2}\Psi_{d,l}}{\partial\rho^{2}}+s^{2}\frac{\partial^{2}\Psi_{d,l}}{\partial\eta^{2}}+2s\frac{\partial^{2}\Psi_{d,l}}{\partial\rho\partial\eta}<0$

By (3.11) (3.12) and the fact that $\theta=\eta l$ we obtain

$\displaystyle Y(s)$ $\displaystyle=$
$\displaystyle-\frac{1}{\rho}+\frac{l-1}{1-2\beta+\rho}+\frac{2(l-1)}{\beta-\rho}-\frac{s^{2}l}{\eta}$
$\displaystyle-(s+1)^{2}\left(\frac{2l}{\beta-\rho-\eta}+\frac{ld}{1-2\beta
d+\rho d+\eta d}\right)$

When $(\rho,\eta)$ is along the straight line passing through
$(\beta^{2},(d-1)\beta^{2})$ with slope $s$, they satisfy the following
equation

$\displaystyle\eta=s(\rho-\beta^{2})+(d-1)\beta^{2}$

When $\beta^{2}\leq\rho\leq\frac{(d-1-s)\beta^{2}}{-s}$ and
$s\in(-\infty,-1]$, we have

$\displaystyle 0\leq\eta\leq-\rho+d\beta^{2}.$

and therefore

$\displaystyle
Y(s)\leq-\frac{1}{\rho}+\frac{l-1}{1-2\beta+\rho}+\frac{2(l-1)}{\beta-\rho}-\frac{l}{d\beta^{2}-\rho}=Y(-1)$

Hence it suffices to show that $Y(-1)<0$ when $\rho\in(\beta^{2},d\beta^{2})$
and (7.1) holds.

Explicit computations show that

$\displaystyle
Y(-1)=-\frac{U(\rho)}{\rho(d\beta^{2}-\rho)(\beta-\rho)(\rho-2\beta+1)}$

where

$\displaystyle
U(\rho)=(l(1-d\beta^{2})-1)\rho^{2}+\beta[l-1+\beta(d-2l+2-2dl)+3\beta^{2}dl]\rho+d\beta^{3}(1-2\beta)$

Then $U(\rho)$ is a parabola opening upwards. The following cases might occur

  1. (1)

$U(\rho)=0$ has no real roots, then $U(\rho)>0$ for all $\rho\in{\mathbb{R}}$,
in particular this implies that $Y(-1)<0$.

  2. (2)

$U(\rho)=0$ has two real roots $\rho_{m}\leq\rho_{M}$. If
$\rho_{M}<\beta^{2}$, then $U(\rho)>0$ for $\rho\in(\beta^{2},d\beta^{2})$,
and therefore $Y(-1)<0$.

Let $T$ be the discriminant of $U(\rho)$. In case (1), $T<0$. In case (2), we
need $T\geq 0$ and

(7.2)
$\displaystyle\rho_{M}=\frac{\sqrt{T}-\beta[l-1+\beta(d-2l+2-2dl)+3\beta^{2}dl]}{2(l(1-d\beta^{2})-1)}<\beta^{2}$

Explicit computations show that (7.2) holds if and only if

(7.3)
$\displaystyle-d^{2}l^{2}\beta^{4}+2d^{2}l^{2}\beta^{3}-d^{2}l\beta^{2}+(-2dl^{2}+2dl)\beta+dl-2l-d+l^{2}+1>0$

It is straightforward to check that (7.3) holds whenever (7.1) holds, $d\geq
3$ and $l\geq 2$. ∎

######  Lemma 7.2.

Assume $d\geq 2$, $l\geq 3$ and $\beta d<1$. Then along the line segment
joining $(\beta^{2},(d-1)\beta^{2})$ and $(d\beta^{2},0)$ in the
$(\rho,\eta)$-plane, there exists $\rho_{8}\in[\beta^{2},d\beta^{2}]$, such
that

  * •

When $\rho\in(\beta^{2},\rho_{8})$, $\frac{\partial\Psi_{d,l}}{\partial\rho}$
is decreasing; and

  * •

When $\rho\in(\rho_{8},d\beta^{2})$, $\frac{\partial\Psi_{d,l}}{\partial\rho}$
is increasing.

###### Proof.

Let

$\displaystyle
X(\rho):=\frac{\partial^{2}\Psi_{d,l}}{\partial\rho^{2}}-\frac{\partial^{2}\Psi_{d,l}}{\partial\rho\partial\eta}$

It suffices to show that

  * •

$X(\rho)\leq 0$ when $\rho\in(\beta^{2},\rho_{8})$; and

  * •

$X(\rho)\geq 0$ when $\rho\in(\rho_{8},d\beta^{2})$.

By (3.11) (3.12) and the fact that $\theta=\eta l$ we obtain

$\displaystyle X(\rho)$ $\displaystyle=$
$\displaystyle-\frac{1}{\rho}+\frac{l-1}{1-2\beta+\rho}+\frac{2(l-1)}{\beta-\rho}$
$\displaystyle=$
$\displaystyle\frac{V(\rho)}{\rho(\beta-\rho)(\rho-2\beta+1)}$

where

$\displaystyle V(\rho)=\rho^{2}+(l-2\beta-\beta l)\rho+2\beta^{2}-\beta$

Note that $V(\rho)$ is a parabola opening upwards with exactly one positive
root and one negative root. Moreover,

$\displaystyle V(0)=-\beta(1-2\beta)<0.$

Then the lemma follows. ∎

######  Lemma 7.3.

Let $d\geq 3$, $l\geq 2$ and $\beta\in\left(0,\frac{1}{d}\right)$. Assume
(7.3) and (3.21) hold. If

(7.4)
$\displaystyle\left.\frac{\partial\Psi_{d,l}}{\partial\rho}(\beta,\rho,\theta)\right|_{(\rho,\theta)=(d\beta^{2},0)}\leq
0$

Then $(\rho,\theta)=(\beta^{2},(d-1)l\beta^{2})$ is the unique global maximum
for $\Psi_{d,l}(\beta,\rho,\theta)$ when $(\rho,\theta)\in R_{\beta}$.

###### Proof.

Let $z=(\rho,\eta)$ be a point along the line segment joining
$z_{0}:=(\beta^{2},(d-1)\beta^{2})$ and $z_{1}:=(d\beta^{2},0)$ in the
$(\rho,\eta)$-plane. By Lemma 7.2, we obtain

$\displaystyle\frac{\partial\Psi_{d,l}}{\partial\rho}(\beta,\rho,l\eta)<\max\left\\{\frac{\partial\Psi_{d,l}}{\partial\rho}(\beta,\beta^{2},(d-1)l\beta^{2}),\frac{\partial\Psi_{d,l}}{\partial\rho}(\beta,d\beta^{2},0)\right\\}\leq
0.$

By Lemma 3.3, if we consider the region $R_{\beta,2}\subset R_{\beta}$ in the
$(\rho,\eta)$-plane bounded by

  * •

$\eta=d\beta^{2}-\rho$; and

  * •

$\eta=\beta-\rho$; and

  * •

$\eta=0$; and

  * •

$\eta=(d-1)\beta^{2}$;

we have

$\displaystyle\frac{\partial\Psi_{d,l}}{\partial\rho}(\beta,\rho,l\eta)<0,\
\forall(\rho,\eta)\in R_{\beta,2}.$

Hence

$\displaystyle\max_{(\rho,\eta)\in
R_{\beta,2}}\Psi_{d,l}(\beta,\rho,l\eta)=\max_{(\rho,d\beta\rho^{2}):\beta^{2}\leq\rho\leq
d\beta^{2}}\Psi_{d,l}(\beta,\rho,l\eta)=\Psi_{d,l}(\beta,\beta^{2},l(d-1)\beta^{2});$

where the last identity follows from Lemma 7.1 and the fact that all the
derivatives at $\Psi_{d,l}(\beta,\rho,\theta)$ at
$(\rho,\theta)=(\beta^{2},(d-1)l\beta^{2})$ vanish. It is straightforward to
check that the maximizer in $R_{\beta,2}$ for $\Psi_{d,l}$ is unique by the
strict negativity of the derivatives.

Let $R_{\beta,1}\subset\mathcal{R}_{\beta}$ be the region in the
$(\rho,\eta)$-plane bounded by

  * •

$\rho=\beta^{2}$; and

  * •

$\eta=0$; and

  * •

$\eta=d\beta^{2}-\rho$; and

  * •

$\eta=2\beta-\rho-\frac{1}{d}$ if $2\beta-\frac{1}{d}>\beta^{2}$.

Then by Lemma 7.1 and the fact that all the derivatives at
$\Psi_{d,l}(\beta,\rho,\theta)$ at $(\rho,\theta)=(\beta^{2},(d-1)l\beta^{2})$
vanish, we obtain

$\displaystyle\max_{(\rho,\eta)\in
R_{\beta,1}}\Psi_{d,l}(\beta,\rho,l\eta)=\Psi_{d,l}(\beta,\beta^{2},l(d-1)\beta^{2});$

and that the maximizer in $R_{\beta,1}$ for $\Phi_{d,l}(\beta,\rho,l\eta)$ is
unique.

Let

$\displaystyle R_{\beta,3}$ $\displaystyle=$
$\displaystyle\left\\{\mathcal{R}_{\beta}\setminus[R_{\beta_{1}}\cup
R_{\beta,2}]\right\\}\cap\\{(\rho,\eta):\det H(\beta,\rho,\eta l)\geq 0\\}$
$\displaystyle R_{\beta,4}$ $\displaystyle=$
$\displaystyle\left\\{\mathcal{R}_{\beta}\setminus[R_{\beta_{1}}\cup
R_{\beta,2}]\right\\}\cap\\{(\rho,\eta):\det H(\beta,\rho,\eta l)<0\\}.$

For any point $(\rho,\eta)\in R_{\beta,3}$, there exists a line segment
joining $(\beta^{2},(d-1)\beta^{2})$ and $(\rho,\eta)$ such that every point
along the line segment is in $R_{\beta,3}$. Note that $\det H>0$ at each
interior point of the line segment, therefore the second order directional
derivative of $\Psi_{d,l}(\beta,\rho,l\eta)$ along the line segment is
strictly negative at each interior point. Since the first order derivatives of
$\Psi_{d,l}(\beta,\rho,l\eta)$ at $(\beta^{2},(d-1)\beta^{2})$ are 0, the
first order directional derivative of $\Psi_{d,l}(\beta,\rho,l\eta)$ along the
line segment is strictly negative at each interior point. Hence we have

$\displaystyle\Psi_{d,l}(\beta,\rho,l\eta)<\Psi_{d,l}(\beta,\beta^{2},l(d-1)\beta^{2}),\
\forall(\rho,\eta)\in R_{\beta,3}\setminus\\{\beta^{2},(d-1)\beta^{2}\\}.$

Now we consider $R_{\beta,4}$. When the Hessian determinant is negative,
$\Psi_{d,l}(\beta,\rho,\theta)$ as a function of $(\rho,\theta)$ cannot
achieve a local maximal value at an interior point; it cannot achieve the
global maximal value in $R_{\beta}$ along the boundary satisfying $\det H=0$
either, since this is also the boundary of the region $\det H>0$ where the
function is strictly concave, and the maximal value in $\det H\geq 0$ is
already achieved at the unique interior point $(\beta^{2},l(d-1)\beta^{2})$.
Therefore if a global maximal value of $\Psi_{d,l}(\beta,\rho,\theta)$ in
$R_{\beta}$ is achieved when $(\rho,\theta)\in R_{\beta}\cap\\{\det H<0\\}$,
then it must be achieved along the boundary $\theta=l(\beta-\rho)$; see Figure
3.1. More precisely, the only possible candidate for the global maximal value
when $\det H<0$ is

$\displaystyle\max_{\rho\in\left[\rho_{5},\beta-(d-1)\beta^{2}\right]}\Psi_{d,l}(\beta,\rho,l(\beta-\rho))$

Let $T_{d,l,\beta}(\rho)$ be defined as in (3). As in (3.38), we obtain that
$\rho\in[\rho_{5},\beta)$, $\frac{d^{2}T_{d,l\beta}(\rho)}{d\rho^{2}}\geq 0$,
and the identity holds if and only if $\rho=\rho_{5}$. Therefore
$\frac{dT_{d,l\beta}(\rho)}{d\rho}$ is monotone increasing when
$\rho\in[\rho_{5},\beta)$. Then

$\displaystyle\max_{\rho\in[\rho_{5},\beta-(d-1)\beta^{2}]}T_{d,l,\beta}(\rho)\leq\max\\{T_{d,l,\beta}(\rho_{5}),T_{d,l,\beta}(\beta)\\}.$

But $(\rho_{5},\beta-\rho_{5})\in R_{\beta,3}$, hence

$\displaystyle
T_{d,l,\beta}(\rho_{5})<\Psi_{d,l}(\beta,\beta^{2},l(d-1)\beta^{2}).$

Moreover, $(\beta,0)\in R_{\beta,2}$, hence

$\displaystyle
T_{d,l,\beta}(\rho_{5})<\Psi_{d,l}(\beta,\beta^{2},l(d-1)\beta^{2}).$

Then the lemma follows. ∎

######  Lemma 7.4.

Let $d\geq 3$, $l\geq 2$ and $\beta\in\left(0,\frac{1}{d}\right)$. Assume
(7.3) and (3.21) hold. If

(7.5)
$\displaystyle\beta\leq\frac{1}{d}\left(1-\sqrt{\frac{d-1}{d^{\frac{l}{l-1}}-1}}\right)$

Then $(\rho,\theta)=(\beta^{2},(d-1)l\beta^{2})$ is the unique global maximum
for $\Psi_{d,l}(\beta,\rho,\theta)$ when $(\rho,\theta)\in R_{\beta}$.

###### Proof.

It is straightforward to check that (7.5) implies (7.4). Then the lemma
follows from Lemma 7.3. ∎

Proof of Theorem 1.1(3c). Theorem 1.1(3c) follows from the similar arguments
as the proof of Theorem 1.1(3b). $\hfill\Box$

##  8\. Maximal Matching

In this section, we discuss the implications of our results on maximal
matchings.

######  Proposition 8.1.

Let $\beta\in\left(0,\frac{1}{d}\right)$. Assume
$f_{l}\left(\frac{1}{d}\right)<0$. Define

(8.1) $\displaystyle K_{m}:=m\beta_{0}+\frac{\ln
m}{2\Phi_{d,l}^{\prime}(\beta_{0})}$

Then

$\displaystyle\lim_{m\rightarrow\infty}\mathbb{E}Z_{K_{m}}=\frac{1}{\sqrt{2\pi\beta_{0}(1-d\beta_{0})}}$

###### Proof.

By (2.7), we obtain

$\displaystyle\mathbb{E}Z_{K}=\frac{1}{\sqrt{2\pi\beta_{0}(1-d\beta_{0})}\sqrt{m}}e^{m\Phi_{d,l}\left(\beta_{0}+\frac{\ln
m}{2m\Phi^{\prime}_{d,l}(\beta_{0})}\right)}\left(1+O\left(\frac{(\ln
m)^{2}}{m}\right)\right)$

Using Taylor expansion at $\beta_{0}$ to approximate
$\Phi_{d,l}\left(\beta_{0}+\frac{\ln
m}{2m\Phi^{\prime}_{d,l}(\beta_{0})}\right)$, the lemma follows. ∎

######  Proposition 8.2.

Let $\beta\in\left(0,\frac{1}{d}\right)$. Assume
$f_{l}\left(\frac{1}{d}\right)<0$. Let $K_{m}$ be given as in (8.1). Let
$Z_{\geq K_{m}+C}$ be the total number of matchings containing at least
$K_{m}+C$ hyperedges in a random regular graph
$\mathcal{G}_{m,d,l}\in\Omega_{m,d,l}$. Then

$\displaystyle\lim_{C\rightarrow\infty}\mathbb{E}Z_{\geq K_{m}+C}=0,$

where the convergence is uniform for all sufficiently large $m\geq C$.

###### Proof.

Let

$\displaystyle C_{m}:=-\frac{5\ln m}{2\Phi^{\prime}_{d,l}(\beta_{0})},$

Note that $C_{m}>0$ since $\Phi_{d,l}(\beta)$ is strictly decreasing in
$\left(\beta_{*},\frac{1}{d}\right)$, and
$\beta_{0}\in\left(\beta_{*},\frac{1}{d}\right)$. Then

$\displaystyle\mathbb{E}Z_{\geq K_{m}+C}=W_{1}+W_{2};$

where

$\displaystyle W_{1}=\sum_{C\leq\delta\leq
C_{m}-1}\mathbb{E}Z_{K_{m}+\delta};\qquad W_{2}=\sum_{\delta\geq
C_{m}}\mathbb{E}Z_{K_{m}+\delta}.$

By (2.7) we obtain

$\displaystyle\mathbb{E}Z_{K_{m}+\delta}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2\pi\beta_{0}(1-d\beta_{0})}\sqrt{m}}e^{m\Phi_{d,l}\left(\beta_{0}+\frac{\ln
m}{2m\Phi^{\prime}_{d,l}(\beta_{0})}+\frac{\delta}{m}\right)}\left(1+O\left(\frac{(\ln
m)^{2}}{m}\right)\right)$

When $\delta\geq C_{m}$, since $\Phi_{d,l}(\beta)$ is strictly decreasing when
$\beta\in\left(\beta_{*},\frac{1}{d}\right)$, we have

$\displaystyle\mathbb{E}Z_{K_{m}+\delta}$ $\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{2\pi\beta_{0}(1-d\beta_{0})}\sqrt{m}}e^{m\Phi_{d,l}\left(\beta_{0}-\frac{2\ln
m}{m\Phi^{\prime}_{d,l}(\beta_{0})}\right)}\left(1+O\left(\frac{(\ln
m)^{2}}{m}\right)\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{2\pi\beta_{0}(1-d\beta_{0})}m^{\frac{5}{2}}}\left(1+O\left(\frac{(\ln
m)^{2}}{m}\right)\right)\leq\frac{1}{m^{2}}$

Since there are at most $m$ summands in $W_{2}$, we obtain
$W_{2}\leq\frac{1}{m}\leq\frac{1}{C}$, since $m\geq C$.

Again using the Taylor expansion of $\Phi_{d,l}$ at $\beta_{0}$ to approximate
$\Phi_{d,l}(K_{m}+\delta)$ we obtain

$\displaystyle W_{1}$ $\displaystyle=$ $\displaystyle\sum_{C\leq\delta\leq
C_{m}-1}\frac{1}{\sqrt{2\pi\beta_{0}(1-d\beta_{0})}}e^{\Phi_{d,l}^{\prime}(\beta_{0})\delta}\left(1+O\left(\frac{(\ln
m)^{2}}{m}\right)\right)$ $\displaystyle\leq$
$\displaystyle\left(1+O\left(\frac{(\ln
m)^{2}}{m}\right)\right)\frac{1}{\sqrt{2\pi\beta_{0}(1-d\beta_{0})}}\frac{e^{\Phi^{\prime}_{d,l}(\beta_{0})C}}{1-e^{\Phi^{\prime}_{d,l}(\beta_{0})}}$

Then the lemma follows since $\Phi_{d,l}^{\prime}(\beta_{0})<0$. ∎

Acknowledgements.Z.L.’s research is supported by NSF grant DMS-1608896 and
Simons grant 683143.

## References

  * [1] D. Alberici and P. Contucci.  Solution of the monomer–dimer model on locally tree-like graphs. rigorous results.  Communications in Mathematical Physics, 331:975–1003, 2014.
  * [2] D. Aldous and J.M. Steele.  The objective method: probabilistic combinatorial optimization and local weak convergence.  Encycl. Math. Sci., 110:1–72, 2004.
  * [3] N. Alon and J.H. Spencer.  The Probabilistic Method.  Wiley, New York, 1992.
  * [4] C. Bordenave, M. Lelarge, and J. Salez.  Matchings on infinite graphs.  Probability Theory and Related Fields, 157:183–208, 2013.
  * [5] C. Cooper, A Frieze, M. Molloy, and B. Reed.  Perfect matchings in random r-regular, s-uniform hypergraphs.  Combinatorics, Probability and Computing, 5:1–14, 1996.
  * [6] A. Dembo and A. Montanari.  Ising models on locally tree-like graphs.  Ann. Appl. Probab., 20:565–592, 2010.
  * [7] J. Ding, A. Sly, and N. Sun.  Maximum independent sets on random regular graphs.  Acta Math., 217:263–340, 2016.
  * [8] G. Elek and G. Lippner.  Borel oracles. an analytical approach to constant-time algorithms.  Proc. Amer. Math. Soc., 138:2939–2947, 2010.
  * [9] P. Erdös and A. Rényi.  On the existence of a factor of degree one of a connected random graph.  Acta Math. Acad. Sci. Hung., 17:359–368, 1966.
  * [10] D. Gamarnik and D. Katz.  Sequential cavity method for computing free energy and surface pressure.  Journal of Statistical Physics, 137:205–232, 2009.
  * [11] G. Grimmett and Z. Li.  Critical surface of hexagonal polygon model.  Journal of Statistical Physics, 163:733–753, 2016.
  * [12] G. Grimmett and Z. Li.  The 1-2 model.  Contemporary Mathematics, 696:139–152, 2017.
  * [13] G. Grimmett and Z. Li.  Critical surface of the 1-2 model.  Int. Math. Res. Not. IMRN, 2018:6617–6672, 2018.
  * [14] G.R. Grimmett and C.J.H. McDiarmid.  On colouring random graphs.  Math. Proc. Cambridge Philos.Soc., 77:313–324, 1975.
  * [15] C. Grinstead and J. L. Snell.  Introduction to Probability.  American Mathematical Society, 1997.
  * [16] E.H. Heilmann, O.J.and Lieb.  Monomers and dimers.  Phys. Rev. Lett., 24:1412–1414, 1970.
  * [17] O.J. Heilmann and E.H. Lieb.  Theory of monomer–dimer systems.  Commun. Math. Phys., 25:190–232, 1972.
  * [18] M. Jerrum.  Two-dimensional monomer-dimer systems are computationally intractable.  Journal of Statistical Physics, 187:121–134, 1987.
  * [19] P.W. Kasteleyn.  The statistics of dimers on a lattice. i. the number of dimer arrangements on a quadratic lattice.  Physica, 27:1209–1225, 1961.
  * [20] C. Kenyon, D. Randall, and A. Sinclair.  Approximating the number of monomer-dimer coverings of a lattice.  Journal of Statistical Physics, 83:637–659, 1996.
  * [21] R. Kenyon.  Lectures on dimers.  In Statistical Mechanics, pages 191–230. American Mathematical Society, Providence, RI, 2009.
  * [22] Z. Li.  Local statistics of realizable vertex models.  Commun.Math.Phys., 304:723–763, 2011.
  * [23] R. W. Robinson and N. C. Warmald.  Almost all regular graphs are hamiltonian.  Random Structures and Algorithms, 5:363–374, 1994.
  * [24] W. Temperley and M. Fisher.  Dimer problem in statistical mechanics—an exact result.  Philos. Mag., 6:1061–1063, 1961.
  * [25] N. Wormald.  The asymptotic distribution of short cycles in random regular graphs.  Journal of Combinatorial Theory, Series B, 31:168–182, 1981.