# Almost all 9-regular graphs have a 3-flow

Michelle Delcourt  Department of Mathematics, Toronto Metropolitan University
(formerly named Ryerson University), Toronto, Ontario M5B 2K3, Canada
<EMAIL_ADDRESS>,  Reaz Huq  Department of Mathematics, Toronto
Metropolitan University (formerly named Ryerson University), Toronto, Ontario
M5B 2K3, Canada<EMAIL_ADDRESS>and  Paweł Prałat  Department of
Mathematics, Toronto Metropolitan University (formerly named Ryerson
University), Toronto, Ontario M5B 2K3, Canada<EMAIL_ADDRESS>
###### Abstract.

In 1972 Tutte famously conjectured that every 4-edge-connected graph has a
nowhere zero 3-flow; this is known to be equivalent to every 5-regular,
4-edge-connected graph having an edge orientation in which every in-degree is
either 1 or 4. Jaeger conjectured a generalization of Tutte’s conjecture,
namely, that every $4p+1$-regular, $4p$-edge-connected graph has an edge
orientation in which every in-degree is either $p$ or $3p+1$. Inspired by the
work of Prałat and Wormald investigating $p=1$, for $p=2$ we show this holds
asymptotically almost surely for random 9-regular graphs. It follows that the
conjecture holds for almost all 9-regular, 8-edge–connected graphs. These
results make use of the technical small subgraph conditioning method.

Research supported by NSERC under Discovery Grant No. 2019-04269.

Research supported by NSERC under Discovery Grant No. 2022-03804. Part of this
work was done while the author was visiting the Simons Institute for the
Theory of Computing.

##  1\. Introduction

A _nowhere-zero 3-flow_ of an undirected graph $G=(V,E)$ is an orientation of
its edge-set together with a function $f:E\rightarrow\\{1,2\\}$ such that the
following is satisfied for each vertex $v\in V$:

$\sum\limits_{e\in D^{+}(v)}f(e)-\sum\limits_{e\in D^{-}(v)}f(e)=0,$

where $D^{+}(v)$ is the set of all edges $e$ such that $\textrm{init}(e)=v$
and $D^{-}(v)$ is the set of all edges $e$ such that $\textrm{ter}(e)=v$. In
1972 Tutte famously conjectured the following (see [4, Open Problem 48], [7,
6, Section 13.3]):

######  Conjecture 1.

(Tutte’s Conjecture) Every 4-edge-connected graph admits a nowhere zero
3-flow.

Though Tutte’s conjecture has attracted considerable attention, it has yet to
be proven. For a significant period of time it was not known whether or not
there are fixed $k$ such that every $k$-edge connected graph has a nowhere-
zero 3-flow (this is known as the weak 3-flow conjecture of Jaeger). It was
proved for $k\geq c\log_{2}n$ for $n$-vertex graphs by Alon, Linial, and
Meshulam [1], as well as by Lai and Zhang [8]. The weak $3$-flow conjecture
was first proved by Thomassen, who showed that every $8$-edge-connected graph
admits a nowhere-zero 3-flow [12]. This was improved to $k=6$ by Lovász,
Thomassen, Wu, and Zhang [9]. It has also been demonstrated by Seymour [11]
that a graph admits a nowhere-zero 3-flow if and only if it has a nowhere-zero
flow over $\mathbb{Z}_{3}$, which is an edge orientation in which the
difference between the out-degree and in-degree of any vertex is divisible by
3. It is well-known (see [4], [7]) that Tutte’s conjecture has the following
equivalent form:

######  Conjecture 2.

(Tutte’s Conjecture Reformulated) Every 5-regular, 4-edge-connected graph has
an edge orientation in which every in-degree is either 1 or 4.

More generally, Jaeger conjectured the following which can be seen as a
generalization of Tutte’s conjecture when $p=1$:

######  Conjecture 3.

(Jaeger’s Conjecture) For any integer $p\geq 1$, the edges of every
$4p+1$-regular, $4p$-edge-connected graph can be oriented so that every in-
degree is either $p$ or $3p+1$.

Jaeger’s conjecture was originally formulated for $4p-$edge-connected graphs
but it can be reduced to the $(4p+1)$-regular case [10]. In [10], Prałat and
Wormald used the small subgraph conditioning method to demonstrate that
Jaeger’s conjecture is asymptotically almost surely true for $p=1$. In [2],
Alon and Prałat used the expander mixing lemma to demonstrate Jaeger’s
conjecture for $p$ which are somewhat large (though still finite). A natural
question is: does this hold for the values of $p$ in between?

In this paper, we investigate the case where $p=2$ and study $9$-regular,
8-edge connected graphs by utilizing pairing model of Bollobàs (see [3]) which
a.a.s. produces 9-regular, 8-edge connected graphs. Our results are
asymptotic, that is, we are holding that the probability that a random graph
on $n$ vertices has a particular property tends to 1 as $n$ tends to infinity.

######  Theorem 1.1.

A random 9-regular graph $G_{n}$ on $n$ vertices a.a.s. admits a nowhere-zero
3-flow, that is, an orientation in which every in-degree is either 2 or 7.

###  1.1. Overview of Proof of Theorem 1.1

To prove Theorem 1.1 we utilize the pairing model; wherein we work with a
random graph $\mathcal{P}_{n,d}$, in which $dn$ points are arranged in $n$
groups of $d$ points each. Each of the $n$ groups is referred to as a _vertex_
while the $d$ points composing them continue to be referred to as _points_. A
perfect matching is then made amongst the points with each group of $d$ points
forming a vertex of degree $d$. The result is a $d$-regular multi-graph. The
convenience of the pairing model lies in the fact that if a given statement is
true in $\mathcal{P}_{n,d}$, it is true in the random $d-$regular graph on $n$
vertices (see Corollary 2.3 in [13]).

We are interested in orientations of the edge-set of 9-regular graphs in which
every vertex has an in-degree of either 2 or 7 (which implies an out-degree of
either 7 or 2, respectively); we call such orientations _valid_. Let $Y=Y(n)$
be the number of valid orientations of a random element of
$\mathcal{P}_{n,9}$. We will show that there are plenty of valid orientations
per pairing, on average. In order to show that pairings a.a.s. have at least
one valid orientation (that is, $\mathbb{P}(Y>0)\sim 1$ or, alternatively
$\mathbb{P}(Y=0)\sim 0$), a standard strategy is to estimate
$\mathbb{E}[Y(Y-1)]$ and show that it is asymptotic to $(\mathbb{E}[Y])^{2}$.
One might be tempted to say that the conclusion then follows immediately from
Chebyshev’s inequality:

$\mathbb{P}\left(Y=0\right)\leq\frac{\mathbb{E}[Y(Y-1)]}{(\mathbb{E}[Y])^{2}}-1.$

Unfortunately, this proof technique fails here as there is a constant factor
discrepancy in the asymptotic ratio giving us an upper bound of $2/7+o(1)$ for
the failure probability instead of $o(1)$.

We will utilize the small subgraph conditioning method (see [13]) to prove
Theorem 1.1. This involves ensuring that a random variable $Y$ and a sequence
of random variables $X_{i}$ (in our case, as usual for this method, we will
let $X_{i}$ be the number of cycles of length $i$) satisfy the following
properties:

  1. (a)

For each $k\geq 1$, $X_{i}$ ($i\in\\{1,2,\ldots,k\\}$) are asymptotically
independent Poisson random variables with $\mathbb{E}[X_{i}]\sim\lambda_{i}$;

  2. (b)

For every finite sequence $j_{1},j_{2},\ldots,j_{k}$ of non-negative integers,

$\frac{\mathbb{E}[Y[X_{1}]_{j_{1}}\ldots[X_{k}]_{j_{k}}]}{\mathbb{E}[Y]}\sim\prod\limits_{i=1}^{k}\mu_{i}^{j_{i}}=\prod\limits_{i=1}^{k}\left(\lambda_{i}(1+\delta_{i})\right)^{j_{i}}$

(note that $[x]_{k}=x(x-1)\cdots(x-k+1)$ is the falling factorial);

  3. (c)

$\sum_{i}\lambda_{i}\delta_{i}^{2}<\infty$;

  4. (d)

$\frac{\mathbb{E}[Y^{2}]}{(\mathbb{E}[Y])^{2}}\leq\exp\left(\sum\limits_{i}\lambda_{i}\delta_{i}^{2}\right)+o(1).$

If the above four properties hold, then

$\mathbb{P}(Y>0)=\exp\left(-\sum\limits_{\delta_{i}=-1}\lambda_{i}\right)+o(1).$

The small subgraph conditioning method was used by Prałat and Wormald to
demonstrate the truth of Jaeger’s conjecture for $p=1$ [10] and it has been
used to deal with similar problems, as in [6], where Delcourt and Postle use
it to demonstrate that a 4-regular graph $G$ a.a.s. admits an
$S_{3}$-decomposition, that is, $G$ can be shown to consist of copies of three
vertices which all make an edge with another vertex.

##  2\. Proof of Theorem 1.1

We introduce the random variable $Y=Y(n)$ to measure the number of valid
orientations of the pairs of a paring in $\mathcal{P}_{n,9}$. A vertex in a
valid orientation is called an in-vertex if it has an in-degree of 2 and is
called an out-vertex otherwise. Each point contained in an edge oriented
towards an in-vertex or away from an out-vertex is called special. A point is
referred to as an in-point if the edge containing it is pointing towards it
and is referred to as an out-point otherwise. The expected number of valid
orientations is computed as follows:

(1) $\mathbb{E}[Y]=\frac{{n\choose n/2}{9\choose 2}^{n}(9n/2)!}{M(9n)},$

where

$M(9n)=\frac{(9n)!}{(9n/2)!2^{9n/2}}$

is the number of perfect matchings on $9n$ points. Indeed, since the number of
in-vertices must match the number of out-vertices, there are ${n\choose n/2}$
ways to choose in-vertices. There are ${9\choose 2}^{n}$ different ways to
pick special points. Finally, there are $(9n/2)!$ different ways to pair in-
points with out-points. After expanding the expression and using Stirling’s
formula ($x!\sim\sqrt{2\pi x}(x/e)^{x}$) we get that

$\mathbb{E}[Y]=\frac{n!\,(9\cdot
4)^{n}\,(9n/2)!^{2}\,2^{9n/2}}{(n/2)!^{2}\,(9n)!}\sim
3\left(\frac{81}{8}\right)^{n/2}.$

Let us now turn our attention to estimating $\mathbb{E}[Y(Y-1)]$. Given two
orientations of the same graph, two vertices $v$ and $w$ can be related in one
of three ways:

  1. (i)

$v$ and $w$ are in-vertices in both orientations;

  2. (ii)

$v$ and $w$ are out-vertices in both orientations;

  3. (iii)

One of $v$ or $w$ is an in-vertex in one orientation and the other is an out-
vertex in the other orientation.

Observe that if exactly $k$ vertices are in-vertices in both orientations,
since there are in total $n/2$ in-vertices in the first orientation, $n/2-k$
vertices are in-vertices in the first orientation and out-vertices in the
second orientation. Since there are $n/2-k$ vertices which are out-vertices in
the second orientation but not in the first and there are $n/2$ total out-
vertices in the second orientation, $k$ vertices are out-vertices in both
orientations. The remaining $n/2-k$ vertices are out-vertices in the second
orientation and in-vertices in the second.

We use the term $k_{211}$ to denote the number of vertices which are in-
vertices in both orientations and which have two special points in common. We
use the term $k_{111}$ to denote the number of vertices which are in-vertices
in both orientations but which only have one special point in common. Note
that $k_{211}\leq k$ and $k_{111}\leq k$ since $k_{211}+k_{111}\leq k$. It
follows that there are $k-k_{211}-k_{111}$ vertices which are in-vertices in
both orientations but which have no special points in common.

Similarly, we use the term $k_{200}$ to denote the number of vertices which
are out-vertices in both orientations and have two special points in common.
$k_{100}$ is defined as the number of vertices which are out-vertices in both
orientations but which only have one special point in common. Note that
$k_{200}\leq k$ and $k_{100}\leq k$ since $k_{200}+k_{100}\leq k$. It follows
that there are $k-k_{200}-k_{100}$ vertices which are out-vertices in both
orientations but which have no special points in common.

The term $k_{210}$ is used to denote the number of vertices which are in-
vertices in the first orientation but out-vertices in the second and which
have both special points in common. $k_{110}$ denotes the number of points
which are in-vertices in the first orientation and out-vertices in the second
but which have only one special point in common. Note that $k_{210}\leq n/2-k$
and $k_{110}\leq n/2-k$ since $k_{210}+k_{110}\leq n/2-k$. It follows that
there are $n/2-k-k_{210}-k_{110}$ vertices which are in-vertices in the first
orientation and out-vertices in the second orientation while have no special
points in common.

The term $k_{201}$ is used to denote the number of vertices which are out-
vertices in the first orientation but in-vertices in the second and which have
both special points in common. $k_{101}$ denotes the number of vertices which
are out-vertices in the first orientation and in-vertices in the second but
which have only one special point in common. Note that $k_{201}\leq n/2-k$ and
$k_{101}\leq n/2-k$ since $k_{201}+k_{101}\leq n/2-k$. It follows that there
are $n/2-k-k_{201}-k_{101}$ vertices which are out-vertices in the first
orientation and in-vertices in the second orientation while having no special
points in common. To approximate the second moment we will need to define a
region that contains every possible configuration of two orientations. Let

$\displaystyle I:=I(n)=\\{$
$\displaystyle(k,k_{211},k_{111},k_{210},k_{110},k_{201},k_{101},k_{200},k_{100})\in\mathbb{N}_{0}^{9}\bigm{|}k\leq
n/2,k_{211}+k_{111}\leq k,$ $\displaystyle k_{200}+k_{100}\leq
k,k_{210}+k_{110}\leq n/2-k,k_{201}+k_{101}\leq n/2-k\\},$

where $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$. Fixing
$\textbf{k}=(k,k_{211},k_{111},k_{210},k_{110},k_{201},k_{101},k_{200},k_{100})$,
we can calculate the number of configurations corresponding to this vector.
Letting $k_{011}=k-k_{211}-k_{111}$, $k_{000}=k-k_{200}-k_{100}$,
$k_{010}=n/2-k-k_{210}-k_{110}$, and $k_{001}=n/2-k-k_{201}-k_{101}$, there
are

(2) $\frac{n!}{\displaystyle
k_{211}!k_{111}!k_{011}!k_{200}!k_{100}!k_{000}!k_{210}!k_{110}!k_{010}!k_{201}!k_{101}!k_{001}!}$

different ways to partition $n$ vertices into twelve groups. Given a
particular partition of the $n$ vertices, there are

(3) ${9\choose 2}^{k_{211}+k_{210}+k_{201}+k_{200}}\cdot\left(9\cdot 8\cdot
7\right)^{k_{111}+k_{110}+k_{101}+k_{100}}\cdot\left({9\choose 2}{7\choose
2}\right)^{k_{011}+k_{010}+k_{001}+k_{000}}$

different ways to assign special points. Indeed, consider a $k_{000}$ vertex.
This vertex will consist of two out-points and seven in-points. Since two of
the in-points in the first orientation are out-points in the other and because
two of its out-points are in-points in the other orientation, the remaining
five in-points that it consists of are in-points in both orientations. Similar
reasoning is applied to the other eleven groups of vertices.

Next we will note that an (in,in)-point naturally pairs with an
(out,out)-point. (Whenever we refer to say, (in,in)-points, the first “in”
refers to the first orientation and the second “in” refers to the second
orientation.) The number of (in,in)-points is

$\displaystyle
2k_{211}+7k_{200}+k_{111}+k_{110}+k_{101}+6k_{100}+5k_{000}+2k_{010}+2k_{001}$
$\displaystyle=2k_{211}+2k_{200}+k_{111}-k_{110}-k_{101}+k_{100}+2n+k-2k_{210}-2k_{201}.$

Likewise, the number of (out,out)-points is

(4)
$2k_{211}+2k_{200}+k_{111}-k_{110}-k_{101}+k_{100}+2n+k-2k_{210}-2k_{201}.$

The remaining points will be (in,out)-points and (out,in)-points. The number
of (in,out)-points is:

$\displaystyle\frac{\displaystyle
9n-2(2k_{211}+2k_{200}+k_{111}-k_{110}-k_{101}+k_{100}+2n+k-2k_{210}-2k_{201})}{2}$
(5)
$\displaystyle=7n/2-(2k_{211}+2k_{200}+k_{111}-k_{110}-k_{101}+k_{100}+k-2k_{210}-2k_{201})$

which also happens to be the number of (out,in)-points.

The set of (in,in)-points needs to be paired with the set of (out,out)-points.
Similarly, (in,out)-points need to be paired with (out,in)-points. Hence, the
product of (2), (3), and the factorials of both (4) and (2) reflect the number
of configurations. Dividing this product by the total number of matchings
provides an estimate of the second-moment, which is the expected number of
pairs of valid orientations.

The second-moment is estimated as follows:

(6) $\mathbb{E}[Y(Y-1)]=\sum\limits_{k\in
I}r(\textbf{z})g(\textbf{z})\exp(nf(\textbf{z}))$

where $\textbf{z}=\textbf{z}(\textbf{k})=\textbf{k}/n$. The product within the
sum is merely the result of applying Stirling’s approximation
$(s!\sim\sqrt{2\pi n}(s/e)^{s})$. Note that $r=O(1)$ for all z and $r\sim 1$
if z is bounded away from the boundary of

$\displaystyle J:=\\{$
$\displaystyle(z,z_{211},z_{111},z_{210},z_{110},z_{201},z_{101},z_{200},z_{100})\in\mathbb{R}_{0}^{9}\bigm{|}z\leq
1/2,z_{211}+z_{111}\leq z,z_{200}$ $\displaystyle+z_{100}\leq
z,z_{210}+z_{110}\leq 1/2-z,z_{201}+z_{101}\leq 1/2-z\\}.$

By letting
$b:=2z_{211}+2z_{200}+z_{111}-z_{110}-z_{101}+z_{100}+2+z-2z_{210}-2z_{201}$
and letting $h(x):=x\log x$ with the stipulation that $h(0)=0$ we get

$\displaystyle g=$
$\displaystyle\left(b(9-2b)^{1/2}\right)/\bigm{(}\sqrt{128(\pi
n)^{9}}(z_{211}z_{111}(z-z_{211}-z_{111})z_{200}z_{100}(z-z_{200}-z_{100})z_{210}z_{110}$
$\displaystyle(1-2z-2z_{210}-2z_{110})z_{201}z_{101}(1-2z-2z_{201}-2z_{101}))^{1/2}\bigm{)}.$

The exponential contribution from [2] is

$\displaystyle f_{1}$ $\displaystyle=\log n-\log e$ $\displaystyle f_{2}$
$\displaystyle=-h(z_{211})-h(z_{111})-h(z-z_{211}-z_{111})-h(z_{200})-h(z_{100})-h(z-z_{200}-z_{100})$
$\displaystyle-h(z_{210})-h(z_{110})-h(1/2-z-z_{210}-z_{110})-h(z_{201})-h(z_{101})$
$\displaystyle-h(1/2-z-z_{201}-z_{101})-\log n+\log e$

which correspond to the numerator and denominator, respectively. The
exponential contribution from [3] is

$\displaystyle f_{3}=$ $\displaystyle\log
9+(z_{111}+z_{100}+z_{110}+z_{101})\log
8+(1-z_{211}-z_{200}-z_{210}-z_{201})\log 7$
$\displaystyle+(1-z_{111}-z_{100}-z_{110}-z_{101})\log 4$
$\displaystyle+(1-z_{211}-z_{200}-z_{210}-z_{201}-z_{111}-z_{100}-z_{110}-z_{101})\log
3.$

The exponential contribution from the factorials of [4] and [2] is:

$f_{4}=h(9/2-b)+h(b)+9/2(\log n-\log e).$

The exponential contribution from dividing by the total number of matchings is

$f_{5}=-h(9)+9/2\log 2+h(9/2)-9/2\log n+9/2\log e.$

Summing $f=f_{1}+f_{2}+f_{3}+f_{4}+f_{5}$ together we get

$\displaystyle f=$ $\displaystyle h(b)+h(9/2-b)+\log(9\cdot 4\cdot 7\cdot
3)-9/2\log 9-(z_{211}+z_{200}+z_{210}+z_{201})\log 7$
$\displaystyle-(z_{211}+z_{200}+z_{210}+z_{200}+z_{111}+z_{100}+z_{110}+z_{101})\log
3$ $\displaystyle+(z_{111}+z_{100}+z_{110}+z_{101})\log
2-h(z_{211})-h(z_{111})$
$\displaystyle-h(z-z_{211}-z_{111})-h(z_{200})-h(z_{100})-h(z-z_{200}-z_{100})-h(z_{210})-h(z_{110})$
$\displaystyle-h(1/2-z-z_{210}-z_{110})-h(z_{201})-h(z_{101})-h(1/2-z-z_{201}-z_{101}).$

Since $h(0)=0$, $f$ is continuous towards the boundary of $J$, which allows us
to explore the question of whether or not $f$ has a maximum. We calculate the
partial derivatives of $f$ using Maple to the end of identifying stationary
points in the interior of $J$.

We find that

$\displaystyle\frac{\delta f}{\delta z_{211}}$
$\displaystyle=\log\Bigm{(}\frac{\displaystyle
b^{2}\cdot(z-z_{211}-z_{111})}{\displaystyle 7\cdot 3\cdot(9/2-b)^{2}\cdot
z_{211}}\Bigm{)},$ $\displaystyle\frac{\delta f}{\delta z_{111}}$
$\displaystyle=\log\Bigm{(}\frac{\displaystyle 2\cdot
b\cdot(z-z_{211}-z_{111})}{\displaystyle 3\cdot(9/2-b)\cdot z_{111}}\Bigm{)}.$

Setting these two partial derivatives equal to one another and re-arranging
gives us

$\frac{z_{111}}{z_{211}}=14\left(\frac{9/2-b}{b}\right).$

Likewise, the partial derivatives for $z_{200}$ and $z_{100}$ are

$\displaystyle\frac{\delta f}{\delta z_{200}}$
$\displaystyle=\log\Bigm{(}\frac{\displaystyle
b^{2}\cdot(z-z_{200}-z_{100})}{\displaystyle 7\cdot 3\cdot(9/2-b)^{2}\cdot
z_{200}}\Bigm{)},$ $\displaystyle\frac{\delta f}{\delta z_{100}}$
$\displaystyle=\log\Bigm{(}\frac{\displaystyle 2\cdot
b\cdot(z-z_{200}-z_{100})}{\displaystyle 3\cdot(9/2-b)\cdot z_{100}}\Bigm{)}.$

Setting these two partial derivatives equal to one another and re-arranging
gives us

$\frac{z_{100}}{z_{200}}=14\left(\frac{9/2-b}{b}\right).$

Since
$14\left(\frac{9/2-b}{b}\right)=\frac{z_{111}}{z_{211}}=\frac{z_{100}}{z_{200}}$,
it follows that $z_{211}z_{100}=z_{200}z_{111}$.

The partial derivatives of $f$ with respect to $z_{210}$ and $z_{110}$ are

$\displaystyle\frac{\delta f}{\delta z_{210}}$
$\displaystyle=\log\Bigm{(}\frac{\displaystyle(9/2-b)^{2}\cdot(1/2-z-z_{210}-z_{110})}{\displaystyle
7\cdot 3\cdot b^{2}\cdot z_{210}}\Bigm{)},$ $\displaystyle\frac{\delta
f}{\delta z_{110}}$ $\displaystyle=\log\Bigm{(}\frac{\displaystyle
2\cdot(9/2-b)\cdot(1/2-z-z_{210}-z_{110})}{\displaystyle 7\cdot 3\cdot b\cdot
z_{110}}\Bigm{)}.$

The partial derivatives of $f$ with respect to $z_{201}$ and $z_{101}$ are

$\displaystyle\frac{\delta f}{\delta z_{201}}$
$\displaystyle=\log\Bigm{(}\frac{\displaystyle(9/2-b)^{2}\cdot(1/2-z-z_{201}-z_{101})}{\displaystyle
7\cdot 3\cdot b^{2}\cdot z_{201}}\Bigm{)},$ $\displaystyle\frac{\delta
f}{\delta z_{101}}$ $\displaystyle=\log\Bigm{(}\frac{\displaystyle
2\cdot(9/2-b)\cdot(1/2-z-z_{201}-z_{101})}{\displaystyle 7\cdot 3\cdot b\cdot
z_{101}}\Bigm{)}.$

Repeating the same procedure with regards to $\frac{\delta f}{\delta
z_{210}}$,$\frac{\delta f}{\delta z_{110}}$,$\frac{\delta f}{\delta z_{201}}$,
and $\frac{\delta f}{\delta z_{101}}$ tells us that

$z_{210}z_{101}=z_{201}z_{110}.$

Setting $\frac{\delta f}{\delta z_{211}}=0$ gives $P_{211}=0$, where

$P_{211}=b^{2}\cdot(z-z_{211}-z_{111})-7\cdot 3\cdot(9/2-b)^{2}\cdot z_{211}.$

If we define $P_{111}$, $P_{200}$, etc. similarly, and obtain $P$ from
$\frac{\delta f}{\delta z}$, we obtain nine polynomials such that any local
maximum must be a common zero of all polynomials. We denote the resultant of
two polynomials $X$ and $Y$ with respect to a variable $x$ as
$\mathcal{R}(X,Y,x)$. When $X=Y=0$ it is necessary that
$\mathcal{R}(X,Y,x)=0$. Taking the resultant of $P_{211}$ and $P_{200}$ with
respect to $z_{101}$ gives us

$\displaystyle\mathcal{R}(P_{211},P_{200},z_{101})$
$\displaystyle=46294416(zz_{200}-zz_{211}+z_{211}z_{100}-z_{200}z_{111})^{2}$
$\displaystyle=46294416((z-z_{111})z_{200}-(z-z_{100})z_{211})^{2}.$

We can use the fact that $z_{211}z_{100}=z_{200}z_{111}$ and
$\mathcal{R}(P_{211},P_{200},z_{101})$ to demonstrate that $z_{211}=z_{200}$,
which then implies $z_{111}=z_{100}$.

Calculating the resultant of $P_{201}$ and $P_{210}$ with respect to $z_{100}$
gives us

$\displaystyle\mathcal{R}(P_{210},P_{201},z_{100})$
$\displaystyle=185177664(2zz_{201}-2zz_{210}-2z_{210}z_{101}+2z_{201}z_{110}-z_{201}+z_{210}),$
$\displaystyle=740710656((-1/2+z+z_{110})z_{201}-(-1/2+z+z_{101})z_{210})^{2}.$

We can use the fact that $z_{210}z_{101}=z_{201}z_{110}$ and
$\mathcal{R}(P_{210},P_{201},z_{100})$ to demonstrate that $z_{210}=z_{201}$,
which then implies $z_{110}=z_{101}$.

We will now consider the nature of possible critical points. Let
$z_{111}=z_{100}=c_{1}$, $z_{211}=z_{200}=c_{2}$, $z_{110}=z_{101}=c_{3}$, and
$z_{210}=z_{201}=c_{4}$. Setting $\frac{\delta f}{\delta z_{211}}=\frac{\delta
f}{\delta z_{200}}=0$ implies that

$\left(\frac{9/2-b}{b}\right)^{2}=\frac{z-c_{1}-c_{2}}{21c_{2}}.$

After squaring $\frac{\delta f}{\delta z_{100}}=\frac{\delta f}{\delta
z_{111}}=0$, it follows that

$\left(\frac{9/2-b}{b}\right)^{2}=\left(\frac{2(z-c_{1}-c_{2})}{3c_{1}}\right)^{2}.$

Since

$\left(\frac{9/2-b}{b}\right)^{2}=\frac{z-c_{1}-c_{2}}{21c_{2}}=\left(\frac{2(z-c_{1}-c_{2})}{3c_{1}}\right)^{2},$

we have $z=\frac{3c_{1}^{2}}{28c_{2}}+c_{1}+c_{2}$.

From setting $\frac{\delta f}{\delta z_{210}}=\frac{\delta f}{\delta z_{110}}$
we get

$\frac{9/2-b}{b}=\frac{14c_{4}}{c_{3}}.$

After setting $\frac{\delta f}{\delta z_{110}}=\frac{\delta f}{\delta
z_{101}}=0$ we get

$\frac{9/2-b}{b}=\frac{3c_{3}}{2(1/2-z-c_{4}-c_{3})}.$

Together these imply that

$\left(\frac{9/2-b}{b}\right)^{2}=\frac{21c_{4}}{(1/2-z-c_{3}-c_{4})}.$

After squaring $\frac{\delta f}{\delta z_{110}}=\frac{\delta f}{\delta
z_{101}}$, it follows that

$\left(\frac{9/2-b}{b}\right)^{2}=\left(\frac{3c_{3}}{2(1/2-z-c_{3}-c_{4})}\right)^{2}.$

Since

$\left(\frac{9/2-b}{b}\right)^{2}=\left(\frac{3c_{3}}{2(1/2-z-c_{3}-c_{4})}\right)^{2}=\frac{21c_{4}}{(1/2-z-c_{3}-c_{4})},$

it follows that $1/2-z=\frac{3c_{3}^{2}}{28c_{4}}+c_{3}+c_{4}$.

We now consider another paramaterization of our variables that will hold when
we are at a critical point. This parameterization is invaluable for finding
the specific values of $b$ and z that form a critical point for $f$. When
$\frac{\delta f}{\delta z_{111}}=\frac{\delta f}{\delta z_{100}}=0$, it
follows that

$c_{1}=14\left(\frac{9/2-b}{b}\right)c_{2}.$

Likewise when $\frac{\delta f}{\delta z_{211}}=\frac{\delta f}{\delta
z_{200}}=0$, it follows that

$b^{2}(z-c_{1}-c_{2})=21\left(\frac{9}{2}-b\right)^{2}c_{2},$

which implies that

$z=\left(\left(\frac{9/2-b}{b}\right)^{2}+14\left(\frac{9/2-b}{b}\right)+1\right)c_{2}.$

When $\frac{\delta f}{\delta z_{110}}=\frac{\delta f}{\delta z_{101}}=0$,

$c_{3}=14\left(\frac{b}{9/2-b}\right)c_{4}.$

Setting $\frac{\delta f}{\delta z_{210}}=\frac{\delta f}{\delta z_{201}}=0$
implies that

$\left(9/2-b\right)^{2}\left(\frac{1}{2}-z-c_{3}-c_{4}\right)=21b^{2}c_{4}$

which in turn implies that

$\frac{1}{2}-z=\left(21\left(\frac{b}{9/2-b}\right)^{2}+14\left(\frac{b}{9/2-b}\right)+1\right)c_{4}.$

Since

$z=\left(\left(\frac{9/2-b}{b}\right)^{2}+14\left(\frac{9/2-b}{b}\right)+1\right)c_{2},$

it follows that

$c_{4}=\frac{1/2-\left(\left(\frac{9/2-b}{b}\right)^{2}+14\left(\frac{9/2-b}{b}\right)+1\right)c_{2}}{21\left(\frac{b}{9/2-b}\right)^{2}+14\left(\frac{b}{9/2-b}\right)+1}.$

$c_{3}$ can be stated as

$c_{3}=14\left(\frac{b}{9/2-b}\right)\frac{1/2-\left(\left(\frac{9/2-b}{b}\right)^{2}+14\left(\frac{9/2-b}{b}\right)+1\right)c_{2}}{21\left(\frac{b}{9/2-b}\right)^{2}+14\left(\frac{b}{9/2-b}\right)+1}.$

After substituting these values for $c_{1}$, $c_{2}$, $c_{3}$, and $c_{4}$
into our partials, the solve function of Maple was used to discover when our
partials equal one another. It was found that for $\frac{\delta f}{\delta
z_{211}}=\frac{\delta f}{\delta z_{200}}=\frac{\delta f}{\delta
z_{111}}=\frac{\delta f}{\delta z_{100}}$,

$c_{2}^{*}(b)=-\frac{4b^{3}(32b^{2}+104b-171)}{5120b^{4}-46080b^{3}+285120b^{2}-816480b-688905}$

when $0<b<9/2$.

After substituting our values for $c_{1}$, $c_{2}$, $c_{3}$, and $c_{4}$ into
$\frac{\delta f}{\delta z}$, we attain an expression for $\frac{\delta
f}{\delta z}$ which is a function of $b$ and $c_{2}$. We can substitute
$c_{2}^{*}(b)$ for $c_{2}$ into our re-parameterized $\frac{\delta f}{\delta
z}$ and then check which, if any, values of $b$ satisfy $\frac{\delta
f}{\delta z}=0$. Maple’s solve function returns the following values for $b$:
$b=0.8065779289$, $b=9/4$, and $b=3.693422071$.

It now remains to see whether these values of $b$ satisfy

$0<c_{2}=c_{2}^{*}(b)<\frac{1/2}{\left(\left(\frac{9/2-b}{b}\right)^{2}+14\left(\frac{9/2-b}{b}\right)+1\right)}.$

Since $c_{2}^{*}(b=0.8065779289)=-0.0001175309606$,
$c_{2}^{*}(b=0.8065779289)$ is not within the feasible region of $J$.

The associated upper-bound

$c<\frac{1/2}{\left(\left(\frac{9/2-b}{b}\right)^{2}+14\left(\frac{9/2-b}{b}\right)+1\right)}$

for $b=3.693422071$ is 0.09883651395. Since
$c_{2}^{*}(b=3.693422071)=0.1105793451$, $c_{2}^{*}(b=3.693422071)$ is also
not within the feasible region $J$.

We are now left with considering to $b=9/4$, which corresponds to
$c_{2}=1/144$. The upper-bound for this value is $1/72$, meaning that it is
within the feasible region of $f$. This value and the corresponding values for
$c_{1},c_{3},c_{4}$, and $z$ imply that

$\hat{\textbf{z}}=(1/4,1/144,7/72,1/144,7/72,1/144,7/72,1/144,7/72)$

is the sole critical point of $f$ in the interior of $J$.

##  3\. Analyzing the Boundary Points

We will now consider points on the boundary of $J$ and see whether any of them
can be global maximums. We will first consider any point on the boundary at
which $0<z<1/2$. In this case, $0\leq z_{211}+z_{111}\leq z$, $0\leq
z_{200}+z_{100}\leq z$, $0\leq z_{110}+z_{210}\leq 1/2-z$, and $0\leq
z_{101}+z_{201}\leq 1/2-z$.

When $z_{111}\rightarrow 0$, $\frac{\delta f}{\delta z_{111}}$ is dominated by
the $z_{111}$ term on its denominator, which tends to $-\infty$. Likewise,
when $z_{211}\rightarrow 0$, $\frac{\delta f}{\delta z_{211}}$ is dominated by
the $z_{211}$ term on its denominator, which also tends to $-\infty$.

When $z_{211}+z_{111}\rightarrow z$, the $z-z_{211}-z_{111}$ term in the
numerator of $\frac{\delta f}{\delta z_{111}}$ will tend to $\infty$.
Likewise, the $z-z_{211}-z_{111}$ term in the numerator of $\frac{\delta
f}{\delta z_{211}}$ will also tend to $\infty$. Thus, there is no global
maximum at these particular points.

The same arguments also apply for $z_{200}$ and $z_{100}$, ensuring that no
global maximum is reached at the points where either or both of them approach
0 and where their sum approaches $z$.

When $z_{110}\rightarrow 0$, $\frac{\delta f}{\delta z_{110}}$ is dominated by
the $z_{110}$ term in its denominator, which tends to $-\infty$. Likewise,
when $z_{210}\rightarrow 0$, $\frac{\delta f}{\delta z_{210}}$ is dominated by
a $z_{210}$ term in its denominator, which also tends to $-\infty$.

When $z_{210}+z_{110}\rightarrow 1/2-z$, the $1/2-z-z_{210}-z_{110}$ term in
the numerator of $\frac{\delta f}{\delta z_{110}}$ will tend to $\infty$.
Likewise, the $z-z_{210}-z_{110}$ term in the numerator of $\frac{\delta
f}{\delta z_{210}}$ will also tend to $\infty$. Thus, there is no global
maximum at these particular points.

The same arguments also apply for $z_{201}$ and $z_{101}$, ensuring that no
global maximum is reached at the points where either or both of them approach
0 and where their sum approaches $1/2-z$.

It now remains to consider the points where $z=0$ and $z=1/2$. We first
consider $z=0$.

Case 1: $z=0$

When $z=0$, $z_{211}=z_{111}=z_{200}=z_{100}=0$ as well. We can thus state $f$
solely in terms of the remaining variables. Substituting
$z=z_{211}=z_{111}=z_{200}=z_{100}=0$ gives the function
$\bar{f}(z_{210},z_{110},z_{201},z_{101})$ with domain $[0,1/2]^{4}$.

Setting $\frac{\delta\bar{f}}{\delta z_{210}}=\frac{\delta\bar{f}}{\delta
z_{110}}$ gives us

$\frac{z_{210}}{z_{110}}=-\frac{(5+2z_{110}+2z_{101}+4z_{210}+4z_{201})}{28(2-z_{110}-z_{101}-2z_{210}-2z_{201})}.$

Likewise, setting $\frac{\delta\bar{f}}{\delta
z_{201}}=\frac{\delta\bar{f}}{\delta z_{101}}$ gives us

$\frac{z_{201}}{z_{101}}=-\frac{(5+2z_{110}+2z_{101}+4z_{210}+4z_{201})}{28(2-z_{110}-z_{101}-2z_{210}-2z_{201})}.$

Together these imply that $z_{210}z_{101}=z_{201}z_{110}$.

Setting $\frac{\delta f}{\delta z_{110}}=\frac{\delta f}{\delta z_{101}}$
implies

$\frac{z_{110}}{1-2z_{210}-2z_{110}}=\frac{z_{101}}{1-2z_{201}-2z_{101}}$

which implies that $z_{110}=z_{101}$.

Setting $\frac{\delta f}{\delta z_{210}}=\frac{\delta f}{\delta z_{201}}$
implies

$\frac{z_{210}}{1-2z_{210}-2z_{110}}=\frac{z_{201}}{1-2z_{201}-2z_{101}}$

which implies that $z_{210}=z_{201}$. We are thus well-justified in
considering $\bar{f}(z_{110},z_{210},z_{110},z_{210})$ in our search for
critical points on this particular part of the boundary.

We now consider the segment $0\leq z_{110}+z_{210}\leq 1/2$. The derivative of
$\bar{f}(z_{110},z_{210},z_{110},z_{210})$ with respect to $z_{110}$ is

$\frac{\delta\bar{f}(z_{110},z_{210},z_{110},z_{210})}{\delta
z_{110}}=\frac{(5+4z_{110}+8z_{210})(-1+2z_{210}+2z_{110})}{12(-1+z_{110}+2z_{210})z_{110}}$

which is not $0$ on the interior of the segment. It is only $0$ when
$z_{110}+z_{210}=1/2$.

$\frac{\delta\bar{f}(z_{110},z_{210},z_{110},z_{210})}{\delta
z_{210}}=-\frac{(5+4z_{110}+8z_{210})^{2}(-1+2z_{210}+2z_{110})}{168(-1+z_{110}+2z_{210})^{2}z_{210}}$

is also only $0$ when $z_{110}+z_{210}=1/2$. Differentiating
$\bar{f}(z_{110},1/2-z_{110},z_{110},1/2-z_{110})$ with respect to $z_{110}$
produces

$\displaystyle\frac{\bar{f}(z_{110},1/2-z_{110},z_{110},1/2-z_{110})}{\delta
z_{110}}=$ $\displaystyle 2\log(2z_{110})-2\log(9-4z_{110})+4\log 2+2\log 7$
$\displaystyle-2\log z_{110}+2\log(1/2-z_{110})$

which is $0$ when $z_{110}=19/52$. Since

$\displaystyle
f(0,0,0,1/2-19/52,19/52,1/2-19/52,19/52,0,0)=\log\frac{(\frac{133}{26})^{19/26}\frac{98}{13}^{49/13}}{3^{7}\cdot\frac{19}{52}^{19/26}\cdot
2^{27/26}\frac{7}{52}^{7/26}}$ $\displaystyle\qquad\simeq
1.672261141<f(\hat{\textbf{z}})=\log\frac{756\cdot\frac{9}{4}^{9/2}\cdot
2^{7/18}\cdot 12^{1/18}}{3^{113/12}\cdot
7^{1/36}\cdot\frac{7}{72}^{7/18}\cdot\frac{7}{48}^{7/12}}\simeq 2.315007612,$

this point cannot be a maximum.

Case 2: $z=1/2$

What follows for $z=0$ is very similar to what was argued for $z=0$. When
$z=1/2$, $z_{210}=z_{110}=z_{201}=z_{101}=0$ as well. We can thus state $f$
solely in terms of the remaining variables. Substituting
$z_{210}=z_{110}=z_{201}=z_{101}=0$ and $z=1/2$ gives the function
$\bar{f}(z_{211},z_{111},z_{200},z_{100})$ with domain $[0,1/2]^{4}$.

Setting $\frac{\delta\bar{f}}{\delta z_{211}}=\frac{\delta\bar{f}}{\delta
z_{111}}$ gives us

$\frac{z_{211}}{z_{111}}=-\frac{(5+2z_{111}+2z_{100}+4z_{200}+4z_{211})}{28(2-z_{111}-z_{100}-2z_{211}-2z_{200})}.$

Likewise, setting $\frac{\delta\bar{f}}{\delta
z_{200}}=\frac{\delta\bar{f}}{\delta z_{100}}$ gives us

$\frac{z_{200}}{z_{100}}=-\frac{(5+2z_{111}+2z_{100}+4z_{200}+4z_{211})}{28(2-z_{111}-z_{100}-2z_{211}-2z_{200})}.$

Together these imply that $z_{211}z_{100}=z_{200}z_{111}$. Setting
$\frac{\delta f}{\delta z_{111}}=\frac{\delta f}{\delta z_{100}}$ implies

$\frac{z_{111}}{1-2z_{211}-2z_{111}}=\frac{z_{100}}{1-2z_{200}-2z_{100}},$

which in turn implies that $z_{111}=z_{100}$. Setting $\frac{\delta f}{\delta
z_{211}}=\frac{\delta f}{\delta z_{200}}$ implies

$\frac{z_{211}}{1-2z_{211}-2z_{111}}=\frac{z_{200}}{1-2z_{200}-2z_{100}},$

which in turn implies that $z_{211}=z_{200}$.

We are thus well-justified in considering
$\bar{f}(z_{111},z_{211},z_{111},z_{211})$ in our search for critical points
on this particular part of the boundary. We now consider the segment $0\leq
z_{111}+z_{211}\leq 1/2$. The derivative of
$\bar{f}(z_{111},z_{211},z_{111},z_{211})$ with respect to $z_{111}$ is

$\frac{\delta\bar{f}(z_{111},z_{211},z_{111},z_{211})}{\delta
z_{111}}=\frac{(5+4z_{111}+8z_{211})(-1+2z_{211}+2z_{111})}{12(-1+z_{111}+2z_{211})z_{111}}$

which is only zero when $z_{211}=z_{111}=1/2$.

Differentiating $\bar{f}(z_{111},1/2-z_{111},z_{111},1/2-z_{111})$ with
respect to $z_{111}$ produces

$\displaystyle\frac{\bar{f}(z_{111},1/2-z_{111},z_{111},1/2-z_{111})}{\delta
z_{111}}=$ $\displaystyle 2\log(2z_{111})-2\log(9-4z_{111})+4\log 2+2\log 7$
$\displaystyle-2\log z_{111}+2\log(1/2-z_{111})$

which is $0$ when $z_{111}=19/52$. Since

$\displaystyle
f(1/2,1/2-19/52,19/52,0,0,0,0,1/2-19/52,19/52)=\log\frac{(\frac{133}{26})^{19/26}\frac{98}{13}^{49/13}}{3^{7}\cdot\frac{19}{52}^{19/26}\cdot
2^{27/26}\frac{7}{52}^{7/26}}$ $\displaystyle\qquad\simeq
1.672261141<f(\hat{\textbf{z}})=\log\frac{756\cdot\frac{9}{4}^{9/2}\cdot
2^{7/18}\cdot 12^{1/18}}{3^{113/12}\cdot
7^{1/36}\cdot\frac{7}{72}^{7/18}\cdot\frac{7}{48}^{7/12}}\simeq 2.315007612,$

this point cannot be a maximum.

The Hessian matrix of $f(\hat{\textbf{z}})$ is

$B=\frac{1}{63}\left[\begin{array}[]{ccccccccc}-1672&544&488&544&488&-544&-488&-544&-488\\\
544&-9280&-320&224&112&-224&-112&-224&-112\\\
488&-320&-1024&112&56&-112&-56&-112&-56\\\
544&224&112&-9280&-320&-224&-112&-224&-112\\\
488&112&56&-320&-1024&-112&-56&-112&-56\\\
-544&-224&-112&-224&-112&-9280&-320&224&112\\\
-488&-112&-56&-112&-56&-320&-1024&112&56\\\
-544&-224&-112&-224&-112&224&112&-9280&-320\\\
-488&-112&-56&-112&-56&112&56&-320&-1024\\\ \end{array}\right].$

To calculate the signs of the eigenvalues of $B$, we can calculate the
eigenvalues of $B^{*}:=63B$. The characteristic polynomial of $B^{*}$ is

$(x^{2}+10584x+10077696)^{3}(x^{3}+11136x^{2}+21055680x+3072577536).$

The eigenvalues of $B^{*}$ are

$\displaystyle\lambda_{1}$
$\displaystyle=\lambda_{2}=\lambda_{3}=-108\sqrt{1537}-5292\simeq-9526.09588932514,$
$\displaystyle\lambda_{4}$
$\displaystyle=\lambda_{5}=\lambda_{6}=108\sqrt{1537}-5292\simeq-1057.90411067487,$
$\displaystyle\lambda_{7}$
$\displaystyle=-8\sqrt{3}\sqrt{105631}\sin((\pi-\arctan((9\sqrt{5834559781407})/26571068))/3)$
$\displaystyle-8\sqrt{105631}\cos((\pi-\arctan((9\sqrt{5834559781407})/26571068))/3)-3712\simeq-8776.89694570535,$
$\displaystyle\lambda_{8}$
$\displaystyle=8\sqrt{3}\sqrt{105631}\sin((\pi-\arctan((9\sqrt{5834559781407})/26571068))/3)$
$\displaystyle-8\sqrt{105631}\cos((\pi-\arctan((9\sqrt{5834559781407})/26571068))/3)-3712\simeq-2199.97604519778,$
$\displaystyle\lambda_{9}$
$\displaystyle=16\sqrt{105631}\cos((\pi-\arctan((9\sqrt{5834559781407})/26571068))/3)-3712\simeq-159.127009096879.$

Since all of these values are negative the Hessian matrix at
$\hat{\textbf{z}}$ is negative definite, implying that $\hat{\textbf{z}}$ is a
local maximum. The determinant of $B$ is found to be
$\frac{-23665185138564661248}{117649}$.

We will now approximate $\mathbb{E}[Y^{2}]$. To this end, we will set
$z=1/4+y$, $z_{2jk}=1/144+y_{2jk}$, and $z_{1jk}=7/72+y_{1jk}$. Setting
$\textbf{y}=(y,y_{211},y_{111},y_{200},y_{100},y_{210},y_{110},y_{201},y_{101})$
and using Taylor’s Theorem to expand around $\hat{\textbf{z}}$ gives us

$f=\log(81/8)+\frac{\textbf{y}B\textbf{y}^{T}}{2}+O(x^{3}).$

Let $x=x(\textbf{z})=||\textbf{y}||$ with $||\cdot||$ denoting the $L^{2}$
norm. Let $J_{0}=\\{\textbf{z}:x\leq n^{-2/5}\\}$. For $\textbf{z}\in J_{0}$
we have $r(\textbf{z})g(\textbf{z})\sim g(\hat{\textbf{z}})$ and
$x^{3}=O(n^{-6/5})$ since $J_{0}$ is bounded away from the boundary of $J$ and
$\textbf{z}\in J_{0}$ are close to $\hat{\textbf{z}}$.

Taking all of this together gives us

$\displaystyle\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}r(\textbf{z})g(\textbf{z})\exp(nf(\textbf{z}))$
$\displaystyle=\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}r(\textbf{z})g(\textbf{z})\exp(nf(\hat{\textbf{z}}+n\textbf{y}B\textbf{y}^{T}+O(x^{-3}))),$
$\displaystyle\sim\left(\frac{81}{8}\right)^{n}g(\hat{\textbf{z}})e^{O(n^{-1/5})}\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}e^{n\textbf{y}\frac{B}{2}\textbf{y}^{T}},$ (7)
$\displaystyle\sim\left(\frac{81}{8}\right)^{n}g(\hat{\textbf{z}})\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}e^{n\textbf{y}\frac{B}{2}\textbf{y}^{T}}.$

Dividing $\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}e^{n\textbf{y}\frac{B}{2}\textbf{y}^{T}}$ by $n^{9}$ gives us a Riemann
sum as $n\to\infty$. By changing k to $\textbf{z}=\textbf{k}/n$ and defining
$\textbf{w}=\sqrt{n}\textbf{y}$ to rescale the region of integration we get

$\frac{1}{n^{9}}\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}e^{n\textbf{y}\frac{B}{2}\textbf{y}^{T}}=\frac{1}{n^{9}}\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}e^{\textbf{w}\frac{B}{2}\textbf{w}^{T}}=\int_{J_{0}}e^{\textbf{w}\frac{B}{2}\textbf{w}^{T}}d^{9}\textbf{w}.$

Since the side-length of the scaled region is $\sqrt{n}\cdot
n^{-2/5}=n^{1/10}$ which goes to $\infty$ as $n\to\infty$ we have

$\int_{J_{0}}e^{\textbf{w}\frac{B}{2}\textbf{w}^{T}}d^{9}\textbf{w}\sim\int_{\mathbb{R}^{9}}e^{\textbf{w}\frac{B}{2}\textbf{w}^{T}}d^{9}\textbf{w}=\int_{\mathbb{R}^{9}}e^{n\textbf{y}\frac{B}{2}\textbf{y}^{T}}d^{9}\textbf{y}.$

After diagonalizing and using the Gaussian integral
$\int_{-\infty}^{\infty}e^{-x^{2}}=\sqrt{\pi}$ we get

$\int_{\mathbb{R}^{9}}e^{n\textbf{y}\frac{B}{2}\textbf{y}^{T}}d^{9}\textbf{y}=\frac{1}{n^{9}}\cdot\sqrt{\frac{n^{9}\cdot\pi^{9}}{|\det\frac{B}{2}|}}=\frac{1}{n^{9}}\cdot\sqrt{\frac{n^{9}\cdot
2^{9}\cdot\pi^{9}}{|\det B|}}=\frac{2^{9/2}\pi^{9/2}}{n^{9/2}\sqrt{|\det B|}}$

which leaves us with

(8)
$\left(\frac{81}{8}\right)^{n}g(\hat{\textbf{z}})\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}e^{n\textbf{y}\frac{B}{2}\textbf{y}^{T}}=\left(\frac{81}{8}\right)^{n}g(\hat{\textbf{z}})\frac{(2\pi
n)^{9/2}}{\sqrt{|\det B|}}.$

It now remains to consider points in $J\backslash J_{0}$.

On the boundary of $J_{0}$ the value of $f$ is
$f(\hat{\textbf{z}})-\Omega(n^{-4/5})$. Recall that $B$ is negative definite
(meaning $\textbf{y}B\textbf{y}^{T}<0$ for all $\textbf{y}\in\mathbb{R}^{9}$).
Furthermore, $f$ is a fixed function that is independent of $n$ and has a
single global maximum at $\hat{\textbf{z}}$. This implies that

$\max\limits_{\textbf{z}\in J\backslash
J_{0}}f(\textbf{z})=f(\hat{\textbf{z}})-\Omega(n^{-4/5})=\log(81/8)-\Omega(n^{-4/5}).$

Since $r$ and $g$ are polynomially bounded it follows that the terms in the
summation (6) for which $\textbf{k}/n\in J/J_{0}$ are bounded by
$(81/8)^{n}e^{-\Omega(n^{1/5})}$. Since there are polynomially many such terms
their sum is $(81/8)^{n}e^{-\Omega(n/5)}$.

It follows, then, that

$\displaystyle\mathbb{E}[Y(Y-1)]$
$\displaystyle=\sum\limits_{\textbf{k}:\textbf{k}/n\in
J}r(\textbf{z})g(\textbf{z})\exp(nf(\textbf{z})),$
$\displaystyle=\sum\limits_{\textbf{k}:\textbf{k}/n\in
J_{0}}r(\textbf{z})g(\textbf{z})\exp(nf(\textbf{z}))+\sum\limits_{\textbf{k}:\textbf{k}/n\in
J\backslash J_{0}}r(\textbf{z})g(\textbf{z})\exp(nf(\textbf{z})),$
$\displaystyle\sim\left(\frac{81}{8}\right)^{n}g(\hat{\textbf{z}})\frac{2^{9/2}\pi^{9/2}}{n^{9/2}\sqrt{|\det
B|}}+(81/8)^{n}e^{-\Omega(n^{1/5})},$
$\displaystyle\sim\left(\frac{81}{8}\right)^{n}g(\hat{\textbf{z}})\frac{2^{9/2}\pi^{9/2}}{n^{9/2}\sqrt{|\det
B|}},$ (9) $\displaystyle\sim\left(\frac{81}{8}\right)^{n}\frac{81}{7}.$

Thus we have

$\frac{\mathbb{E}[Y(Y-1)]}{\mathbb{E}[Y]^{2}}=\frac{\left(\frac{81}{8}\right)^{n}\frac{81}{7}}{9\left(\frac{81}{8}\right)^{n}}=\frac{9}{7}.$

To complete our proof of Theorem 1.1 we introduce random variables
$X_{1},X_{2},\ldots,X_{k}$ for $k\geq 1$ which represent the number of cycles
of length $k$ in $\mathcal{P}(n,9)$. A well known result by Bollobás (see
Corollary 2.19 in [5]) stipulates that $X_{1},X_{2},\ldots,X_{k}$ are
asymptotically independent Poisson distributions with mean

$\mathbb{E}[X_{k}]\longrightarrow\lambda_{k}:=\frac{8^{k}}{2k}.$

To satisfy the condition (b) for the small subgraph conditioning method and
thereby prove Theorem 1.1, we will need to show that there is a constant
$\mu_{k}$ for each $k\geq 1$ such that

$\frac{\mathbb{E}[YX_{k}]}{\mathbb{E}Y}\longrightarrow\mu_{k}$

and that the joint factorial moments satisfy

$\frac{\mathbb{E}[Y[X_{1}]_{j_{1}}[X_{2}]_{j_{2}}\ldots[X_{k}]_{j_{k}}]}{\mathbb{E}Y}\longrightarrow\prod\limits_{i=1}^{k}\mu_{i}^{j_{i}}$

for any fixed $j_{1},j_{2},\ldots,j_{n}$, where $[x]_{k}$ is the falling
factorial $x!/(x-k)!$. To estimate $\mathbb{E}[YX_{k}]$ we will count the mean
number of triples $(P,C,O)$, where $P$ represents a pairing, $C$ represents a
$k-$cycle, and $O$ represents an orientation by dividing the number of such
pairings by the total number of matchings $|\mathcal{P}(9,n)|=M(9n)$.

There are $\frac{(9\cdot 8)^{k}}{2k}\cdot\frac{n!}{(n-k)!}$ different ways to
choose vertices that make up the cycle. There are $i$ vertices with in-degree
2, $b$ of which are in-vertices. Since the sum of in-degrees in the cycle must
equal the number of out-degrees in the cycle, there are $i$ vertices in the
cycle with out-degree 2, $c$ of which are out-vertices. This implies that
$k-2i$ vertices in the cycle have an in-degree and out-degree of 1 in the
context of the cycle. We let $a_{i}=2{k\choose 2i}$ refer to the number of
orientations. The number of choices of in-vertices among $i-$vertices with in-
degree 2 is ${i\choose b}$. Likewise, there are ${i\choose c}$ possible
choices of out-vertices among $i$ vertices with out-degree 2. Turning our
attention to the vertices outside of the cycle, we see that there are
${n-2i\choose n/2-i-b+c}$ ways to pair the in- and out-vertices that are not
in $C$.

We now consider the distribution of special points between our orientations.
There are ${7\choose 2}^{i-b}$ ways to select special points in vertices that
have an in-degree of 2 in the cycle and are out-vertices in the graph.
Likewise, there are ${7\choose 2}^{i-c}$ ways to select special points in
vertices that have an out-degree of 2 in the cycle and which are in-vertices
in the graph. The special points for vertices with in-degree 2 in $C$ and
which are in-vertices and for vertices with out-degree 2 in $C$ and which are
out-vertices do not need to be identified. There are $7^{k-2i}$ ways to select
special points among vertices in $C$ which have an in-degree of 1 and an out-
degree of 1. There are ${9\choose 2}^{n-k}$ ways to select special points for
vertices outside of $C$. Given that $9n/2-k$ must be in-vertices there are
$(9n/2-k)!$ different ways to pair in-vertices with out-vertices.

We calculate $\frac{\mathbb{E}[X_{k}Y]}{\mathbb{E}[Y]}$ as follows:

$\displaystyle\frac{\mathbb{E}[YX_{k}]}{\mathbb{E}[Y]}$ $\displaystyle\sim$
$\displaystyle\frac{\sum\limits_{i=0}^{\lfloor k/2\rfloor}\frac{[n]_{k}(9\cdot
8)^{k}}{2k}a_{i}{9\choose
2}^{n-k}(9n/2-k)!7^{k-2i}\sum\limits_{b=0}^{i}\sum\limits_{c=0}^{i}{i\choose
b}{i\choose c}{n-2i\choose n/2-i-b+c}{7\choose 2}^{i-b}{7\choose
2}^{i-c}}{{n\choose n/2}{9\choose 2}^{n}(9n/2)!},$ $\displaystyle\sim$
$\displaystyle\frac{\sum\limits_{i=0}^{\lfloor k/2\rfloor}\frac{[n]_{k}(9\cdot
8)^{k}}{2k}a_{i}7^{k-2i}\sum\limits_{b=0}^{i}\sum\limits_{c=0}^{i}{i\choose
b}{i\choose c}{n-2i\choose n/2-i-b+c}{7\choose 2}^{i-b}{7\choose
2}^{i-c}}{{n\choose n/2}(9\cdot 4)^{k}(9n/2)^{k}},$ $\displaystyle\sim$
$\displaystyle\frac{\sum\limits_{i=0}^{\lfloor
k/2\rfloor}\frac{n^{k}}{2k}a_{i}2^{k}7^{k-2i}\frac{(n-2i)!}{n!}\sum\limits_{b=0}^{i}{i\choose
b}(7\cdot 3)^{b}\sum\limits_{c=0}^{i}{i\choose c}(7\cdot
3)^{c}\frac{n/2!}{(n/2-i+b-c)!}\frac{n/2!}{(n/2-i-b+c)!}}{(\frac{9n}{2})^{k}}.$

Since $n\to\infty$ and $k$ is finite Sterling’s formula implies that
$\frac{(n-2i)!}{n!}\sim\left(\frac{n}{e}\right)^{-2i}$ and
$\frac{n/2!}{(n/2-i+b-c)!}\frac{n/2!}{(n/2-i-b+c)!}\sim\left(\frac{n}{2e}\right)^{2i}$.
We therefore get

$\displaystyle\frac{\mathbb{E}[YX_{k}]}{\mathbb{E}[Y]}$ $\displaystyle\sim$
$\displaystyle\frac{\sum\limits_{i=0}^{\lfloor
k/2\rfloor}\frac{n^{k}}{2k}a_{i}2^{k}7^{k-2i}\frac{(n-2i)!}{n!}\sum\limits_{b=0}^{i}{i\choose
b}(7\cdot 3)^{b}\sum\limits_{c=0}^{i}{i\choose c}(7\cdot
3)^{c}\frac{n/2!}{(n/2-i+b-c)!}\frac{n/2!}{(n/2-i-b+c)!}}{(\frac{9n}{2})^{k}},$
$\displaystyle\sim$ $\displaystyle\sum\limits_{i=0}^{\lfloor
k/2\rfloor}\left(\frac{28}{9}\right)^{k}\frac{a_{i}}{2k}\sum\limits_{b=0}^{i}{i\choose
b}21^{b}\sum\limits_{c=0}^{i}{i\choose
c}21^{c}\left(\frac{n}{e}\right)^{-2i}\left(\frac{n}{2e}\right)^{2i}.$

Since $\sum\limits_{b=0}^{i}{i\choose b}21^{b}=\sum\limits_{c=0}^{i}{i\choose
c}21^{c}=(1+21)^{i}$ we get the following:

$\displaystyle\frac{\mathbb{E}[YX_{k}]}{\mathbb{E}Y}$ $\displaystyle\sim$
$\displaystyle\sum\limits_{i=0}^{\lfloor
k/2\rfloor}\frac{1}{2k}\left(\frac{28}{9}\right)^{k}a_{i}\left(\frac{1}{7}\right)^{2i}22^{2i}\left(\frac{1}{2}\right)^{2i},$
$\displaystyle\sim$
$\displaystyle\frac{1}{2k}\left(\frac{28}{9}\right)^{k}\sum\limits_{i=0}^{\lfloor
k/2\rfloor}2{k\choose 2i}\left(\frac{11}{7}\right)^{2i}.$

This can be completed by defining
$q(x):=2(1+x)^{k}=\sum\limits_{i=0}^{k}2{k\choose i}\cdot i$. We can consider
our particular sum to be the even terms of the summation
$\sum\limits_{i=0}^{\lfloor k/2\rfloor}2{k\choose
2i}\left(\frac{11}{7}\right)^{2i}$. Since the exponential term will be
negative for odd $i$ we can simplify our expression as follows:

$\displaystyle\sum\limits_{i=0}^{\lfloor k/2\rfloor}2{k\choose
2i}\left(\frac{11}{7}\right)^{2i}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(q\left(\frac{11}{7}\right)+q\left(-\frac{11}{7}\right)\right).$

Returning to our calculation of $\frac{\mathbb{E}[X_{k}Y]}{\mathbb{E}Y}$ gives
us

$\displaystyle\frac{\mathbb{E}[YX_{k}]}{\mathbb{E}Y}$ $\displaystyle=$
$\displaystyle\frac{1}{2k}\left(\frac{28}{9}\right)^{k}\left(\left(\frac{18}{7}\right)^{k}+\left(\frac{-4}{7}\right)^{k}\right),$
$\displaystyle=$
$\displaystyle\frac{1}{2k}\left(8^{k}+\left(-\frac{16}{9}\right)^{k}\right).$

We conclude that
$\mu_{k}=\frac{1}{2k}\left(8^{k}+\left(-\frac{16}{9}\right)^{k}\right)$. Since
Corollary 2.19 from [5] stipulates that the cycles are asymptotically
independent, we are justified in further concluding that, for every finite
sequence $j_{1},j_{2},\ldots,j_{k}$ of non-negative integers, the following
holds:

$\frac{\mathbb{E}(Y[X_{1}]_{j_{1}}\cdots[X_{k}]_{j_{k}})}{\mathbb{E}Y}\sim\prod\limits_{i=1}^{k}\mu_{i}^{j_{i}}=\prod\limits_{i=1}^{k}\left(\lambda_{i}(1+\delta_{i})\right)^{j_{i}}$

where $\delta_{i}=\frac{\mu_{i}}{\lambda_{i}}-1$ to satisfy condition (c). For
the $k$ that we concerned ourselves with above
$\delta_{k}=\left(-\frac{2}{9}\right)^{k}$.

We now need to show that $\sum_{i}\lambda_{i}\delta_{i}^{2}<\infty$. Using the
fact that $-\log(1-x)=\sum_{k\geq 1}x_{k}/k!$,

$\exp\left(\sum\limits_{k\geq
1}\lambda_{k}\delta_{k}^{2}\right)=\sum\limits_{k\geq
1}\frac{8^{k}}{2k}\left(\frac{4}{81}\right)^{k}=\exp\left(\frac{1}{2}-\log\left(1-\frac{2^{5}}{3^{4}}\right)\right)=\frac{9}{7}.$

Since $\exp\left(\sum\limits_{k\geq
1}\lambda_{k}\delta_{k}^{2}\right)\sim\frac{\mathbb{E}(Y^{2})}{\mathbb{E}[Y]^{2}}\sim
9/7$, all four conditions of the small subgraph conditioning method are
satisfied. We can conclude that $\mathbb{P}(Y>0)\sim 1$.

## References

  * [1] N. Alon, N. Linial, and R. Meshulam, Additive bases of vector spaces over prime fields, J. Combinatorial Theory, Ser A 57 (1991), 203-210.
  * [2] N. Alon, P. Prałat, Modular orientations of random and quasi-random graphs, Combinatorics, Probability and Computing 20 (2011), 321-329.
  * [3] B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal of Combinatorics, 1, (1980), 311-316.
  * [4] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications Macmillan, London, 1976.
  * [5] B. Bollobás, Random Graphs, 2nd edn, Cambridge, United Kingdom (2001).
  * [6] M. Delcourt, L. Postle, Random 4-regular graphs have 3-star-decompositions asymptotically almost surely, European Journal of Combinatorics 72C (2018), 97-111.
  * [7] T.R. Jensen, B. Toft, Graph Coloring Problems. Wiley-Intersci. Ser. Discrete Math. Optim., 1995.
  * [8] H-J. Lai and C.Q. Zhang, Nowhere-zero 3-flows of highly connected graphs, Discrete Math. 110 (1992) 179-183.
  * [9] L.M. Lovász, C. Thomassen, Y.Wu, C.Q. Zhang, Nowhere-zero 3-flows and modulo $k-$orientations, Journal of Combinatorial Theory, Series B 103 857-598
  * [10] P. Prałat, N.Wormald, Almost all 5-regular graphs have a 3-flow, Journal of Graph Theory, 93 (2019) 147-156.
  * [11] P.D. Seymour, Nowhere-zero flows, in ”Handbook of Combinatorics,” 299, North-Holland, Amsterdam, 1995.
  * [12] C. Thomassen, The weak 3-flow conjecture and the weak circular flow conjecture, Journal of Combinatorial Theory, Series B 102 (2012) 521-529
  * [13] N.C. Wormald, Models of random regular graphs, Surveys in Combinatorics, 1999, J.D. Lamb and D.A. Preece, eds. London Mathematical Society Lecture Note Series, vol 276, pp. 236-298, Cambridge University Press, Cambridge, 1999.