Content-Type: multipart/mixed; boundary="-------------1710010918129"

This is a multi-part message in MIME format.

---------------1710010918129
Content-Type: text/plain; name="17-99.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="17-99.comments"

eight pages
---------------1710010918129
Content-Type: text/plain; name="17-99.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="17-99.keywords"

random graph, regular bipartite graph
---------------1710010918129
Content-Type: application/x-tex; name="yomkippur.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="yomkippur.tex"

\documentclass{article}
\usepackage{amsfonts,amsmath}
\mathchardef\mhyphen="2D % Define a "math hyphen"
\usepackage[a4paper]{geometry}
\usepackage{microtype}
\usepackage{relsize}
\def\Z{\mathbb Z}
\def\zo/{$0\mkern2mu\mhyphen1$}%0-1
\def\Ex{E_{\times}}
\def\nn/{$n \times n$}
\def\a{\alpha}
\newtheorem{conj}{Conjecture}
\DeclareMathOperator\perm{perm}
\title{A New Property of Random Regular Bipartite Graphs}
\date{\today} 
\author{Paul Federbush\\
Department of Mathematics\\
University of Michigan\\
Ann Arbor, MI, 48109-1043}

%%%% Added by T. Murayama
\usepackage{amsthm} % Needed for conj*
\newtheorem{thm}{Theorem}[section]
\newtheorem*{conj*}{Conjecture} % Defines non-numbered conjecture environment
\numberwithin{equation}{section} % Fixes equation labels to match manuscript
\DeclareMathOperator{\Prob}{Prob}
\DeclareMathOperator{\EE}{E}
\DeclareMathOperator{\OO}{\mathcal{O}}
\DeclareMathOperator{\PP}{P}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}} % For double slash
%%%%

\begin{document}

\maketitle
\begin{abstract}
  One deals with $r$-regular bipartite graphs with $2n$ vertices.
  In a previous paper Butera, Pernici, and the author have introduced a quantity
  $d(i)$, a function of the number of $i$-matchings, and conjectured that as $n$
  goes to infinity the fraction of graphs that satisfy $\Delta^k d(i) \ge 0$,
  for all $k$ and $i$, approaches $1$.
  Here $\Delta$ is the finite difference operator.
  In this paper it is proved that for each $r$, $i$, and $k \le 6$ that the
  probability that $\Delta^k d(i) \ge 0$ goes to $1$ with $n$ going to infinity.
  A formalism of Wanless as systematized by Pernici is central to the proof.
\end{abstract}

\section{Introduction}
We deal with $r$-regular bipartite graphs with $v = 2n$ vertices.
We let $m_i$ be the number of $i$-matchings.
In \cite{BFP}, Butera, Pernici, and I introduced the quantity $d(i)$, in eq.\
$(10)$ therein,
\begin{equation}\label{eq:1.1}
  d(i) \equiv \ln\biggl( \frac{m_i}{r^i} \biggr)
  - \ln\biggl( \frac{\overline{m}_i}{(v-1)^i} \biggr)
\end{equation}
where $\overline{m}_i$ is the number of $i$-matchings for the complete (not
bipartite complete) graph on the same vertices,
\begin{equation}\label{eq:1.2}
  \overline{m}_i = \frac{v!}{(v-2i)!\,i!\,2^i}
\end{equation}
We here have changed some of the notation from \cite{BFP} to agree with notation
in \cite{Per}.
We then considered $\Delta^k d(i)$ where $\Delta$ is the finite difference
operator, so
\begin{equation}\label{eq:1.3}
  \Delta d(i) = d(i+1) - d(i)
\end{equation}
A graph was defined to satisfy \textit{graph positivity} if all the meaningful
$\Delta^k d(i)$ were non-negative.
That is
\begin{equation}\label{eq:1.4}
  \Delta^k d(i) \ge 0
\end{equation}
for $k = 0,\ldots,v$ and $i = 0,\ldots,v-k$.
We made the conjecture, supported by some computer evidence,
\begin{conj*}
  As $n$ goes to infinity the fraction of graphs that satisfy graph positivity
  approaches one.
\end{conj*}
In this paper we prove a weaker result in the same direction.
\begin{thm}\label{thm:1.1}
  For each $r$, $i$, and $k \le 6$, one has
  \begin{equation*}
    \Prob\bigl(\Delta^k d(i) \ge 0\bigr) \xrightarrow[n \to \infty]{} 1
  \end{equation*}
\end{thm}
The paper relies heavily on the work of Wanless, \cite{Wan}, and Pernici,
\cite{Per}, that gives a nice representation of the $m_i$.
The restriction to $k \le 6$ is very disappointing.
Much of the theoretical development herein is for all $k$.
The current technique of proof certainly does not work for $k \ge 7$, and it is
possible that the statement in Theorem \ref{thm:1.1} is not true for $k \ge 7$.

The restriction to bipartite graphs is mainly because this restriction is made in \cite{BFP},
and is certainly ( it seems ) necessary for the conjecture above. In this paper the
bipartite nature appears used in two places. First, the number of vertices is assumed to be
even, and second, in eq.(3.6) the lower limit 4 is replaced by 3 if one does not assume
the graph is bipartite.

\section{Idea of the proof}
Suppose we want $\Prob(x > y)$ to be large.
We have
\begin{equation}\label{eq:2.1}
  \Prob(x < y) = \Prob(e^x < e^y)
\end{equation}
Set
\begin{equation}\label{eq:2.2}
  \EE(e^x - e^y) \equiv \alpha
\end{equation}
We will want $\alpha$ to be positive, and in the present work proving this
positivity will be a major component.
Let
\begin{equation}\label{eq:2.3}
  \EE\bigl( (e^x - e^y)^2\bigr) - \alpha^2 \equiv \beta
\end{equation}
Then, assuming $\alpha > 0$,
\begin{equation}\label{eq:2.4}
  \EE\bigl( (e^x - e^y - \alpha)^2\bigr) \ge \alpha^2 \, \PP(e^x - e^y < 0)
\end{equation}
And so
\begin{equation}\label{eq:2.5}
  \Prob(e^x < e^y) \le \frac{\beta}{\alpha^2}
\end{equation}
In our problem $\beta$ and $\alpha$ will be functions of $n$, and we'll want
probability to go to zero with $n$ as $n$ goes to infinity.
We will guarantee this by finding twice the highest power of $n$ in $\alpha$ to
be greater than the highest power of $n$ in $\beta$.
\par We turn to the object of study, and perform some simple manipulations,
working from eq.\ \eqref{eq:1.1}
\begin{align}
  &\Prob\bigl( \Delta^k d(i) > 0 \bigr) = \Prob\Biggl( (-1)^k
  \sum_{\ell=0}^k (-1)^\ell \binom{k}{\ell} \, \ln \biggl(
  \frac{m_{i+\ell}}{\overline{m}_{i+\ell}} \cdot \frac{(v-1)^{i+\ell}}{r^{i+\ell}}
  \biggr) > 0 \Biggr)\label{eq:2.6}\\
  &\qquad= \Prob\Biggl( \sum_{\ell \in \mathcal{L}^+} \binom{k}{\ell} \,
  \ln \biggl( \frac{m_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
  \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr) > \sum_{\ell \in \mathcal{L}^-}
  \binom{k}{\ell}\,\ln \biggl( \frac{m_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
  \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr) \Biggr)\label{eq:2.7}
\end{align}
where $\mathcal{L}^+$ is the set of odd $\ell$, $0 \le \ell \le k$, if $k$ is
odd and is the set of even $\ell$, $0 \le \ell \le k$, if $k$ is even, and
$\mathcal{L}^-$ is defined vice versa.
\par Returning to the language of \eqref{eq:2.1}--\eqref{eq:2.5}, we set
\begin{align}
  x &\equiv \sum_{\ell \in \mathcal{L}^+} \binom{k}{\ell}\,\ln \biggl(
  \frac{m_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
  \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr)\label{eq:2.8}\\
  y &\equiv \sum_{\ell \in \mathcal{L}^-} \binom{k}{\ell}\,\ln \biggl(
  \frac{m_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
  \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr)\label{eq:2.9}
  \intertext{and so}
  e^x &= \prod_{\ell \in \mathcal{L}^+} \biggl(
  \frac{m_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
  \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr)^{\binom{k}{\ell}}\label{eq:2.10}\\
  e^y &= \prod_{\ell \in \mathcal{L}^-} \biggl(
  \frac{m_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
  \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr)^{\binom{k}{\ell}}\label{eq:2.11}
\end{align}

\section{The Work of Wanless and Pernici}\label{sec:3}
In \cite{Wan} Wanless developed a formalism to compute the $m_i$ of any regular
graph.
We here only give a flavor of this formalism, but present those consequences we
will use in this paper.
For each $i$ there are defined a set of graphs
$g_{i1},g_{i2},\ldots,g_{i n(i)}$.
Given a regular graph $g$, one computes for each $j$ the number of subgraphs of
$g$ isomorphic to $g_{ij}$, call this $g \sslash g_{ij}$.
Then $m_i$ for $g$ is determined by the $n(i)$ values of $g \sslash g_{ij}$.
We define $M_i$ to be the value of $m_i$ assigned to a graph with all $n(i)$
values of $g \sslash g_{ij}$ zero.
$M_i = M_i(r,n)$ is an important object of study to us.
Most of the paper we will approximate $m_i$ by $M_i$.
We will use subscript $0$ as indicating $m_i$ as it appears in any expression is
replaced by $M_i$.
Thus from \eqref{eq:2.2}, \eqref{eq:2.10}, and \eqref{eq:2.11} we get
\begin{equation}\label{eq:3.1}
  \alpha_0 = \EE\Biggl(
    \prod_{\ell \in \mathcal{L}^+} \biggl(
    \frac{M_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
    \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr)^{\binom{k}{\ell}}
    - \prod_{\ell \in \mathcal{L}^-} \biggl(
    \frac{M_{i+\ell}}{\overline{m}_{i+\ell}} \cdot
    \frac{(v-1)^{i+\ell}}{r^{i+\ell}} \biggr)^{\binom{k}{\ell}}
  \Biggr)
\end{equation}
\par In \cite{Per} Pernici systematized the results of Wanless; we take a number
of formulae from this paper.
From eq.\ $(12)$ and eq.\ $(13)$ of \cite{Per} we write
\begin{align}
  M_j &= \frac{n^jr^j}{j!} (1+H_j) \label{eq:3.2}\\
  H_j &= \sum_{h=1}^{j-1} \frac{a_h(r,j)}{n^h} \label{eq:3.3}
\end{align}
$a_h$ is a polynomial of degree at most $2h$ in $j$.
We will use eq.\ $(16)$ and $(17)$ of \cite{Per}
\begin{align}
  [j^k n^{-h}]\,\ln \biggl( 1 + \sum_{s=1}^{j-1} \frac{a_s(r,j)}{n^s} \biggr) &=
  0, \qquad k \ge h+2 \label{eq:3.4}\\
  [j^{h+1} n^{-h}]\,\ln \biggl( 1 + \sum_{s=1}^{j-1} \frac{a_s(r,j)}{n^s} \biggr)
  &= \frac{1}{(h+1)h} \biggl( \frac{1}{r^h} - 2 \biggr) \label{eq:3.5}
\end{align}
where $[j^k n^{-h}]$ in front of an expression picks out the coefficient of the
$\frac{j^k}{n^h}$ term, $c(k,h)$, in an expression $\sum_{\alpha,\beta}
c(\alpha,\beta) \frac{j^\alpha}{n^\beta}$.
\par We set $M_0 = 1$ and $M_s = 0$ if $s < 0$.
Then $m_j$ is recovered from $M_j$ by the formula
\begin{equation}\label{eq:3.6}
  m_j = \exp \biggl( \sum_{s \ge 4} \frac{\varepsilon_s}{2s} (-\hat{x})^s \biggr)
  M_j
\end{equation}
eq.\ $(11)$ of \cite{Per}. Here
\begin{equation}\label{eq:3.7}
  \hat{x} M_j = M_{j-1}
\end{equation}
$\varepsilon_s$ for a graph $g$ is a linear function of a finite number of $g
\sslash \ell_i$, $\ell_i$ a set of given graphs.
All we need to know is that for any given product of $\varepsilon_s$'s, $\prod_i
\varepsilon_{s(i)}$, one has that
\begin{equation}\label{eq:3.8}
  \EE\biggl( \prod_i \varepsilon_{s(i)} \biggr) \le C
\end{equation}
i.e.\ it is a bounded function of $n$.
The main result one needs to see this is that the number of $s$-cycles are
independent Poisson random variables of finite means in the fixed $r$, $n$ goes
to infinity limit, \cite{Bol}.
One then uses the fact that the $\ell_i$ and $g_{ij}$ graphs discussed above all
are either single cycle or multicycle in nature.

\section{Some simple reorganization}
We define
\begin{equation}\label{eq:4.1}
  1 + K_i \equiv \frac{(v-1)^i}{r^i} \cdot \frac{(v-2i)!\,i!\,2^i}{v!} \cdot
  \frac{r^in^i}{i!}
\end{equation}
using notably eq.\ \eqref{eq:1.2}.
Then $\alpha_0$ becomes
\begin{equation}\label{eq:4.2}
  \alpha_0 = \EE\Biggl(
    \prod_{\ell \in \mathcal{L}^+} \bigl(
      (1+H_{i+\ell})(1+K_{i+\ell})
    \bigr)^{\binom{k}{\ell}}
    - \prod_{\ell \in \mathcal{L}^-} \bigl(
      (1+H_{i+\ell})(1+K_{i+\ell})
    \bigr)^{\binom{k}{\ell}}
  \Biggr)
\end{equation}
Further we set
\begin{equation}\label{eq:4.3}
  1 + K_i \equiv e^{G_i}
\end{equation}
where
\begin{align}
  G_i &\equiv G_{i,1} + G_{i,2} + G_{i,3} + G_{i,4} + G_{i,5} \label{eq:4.4}\\
  G_{i,1} &\equiv i\,\ln\Bigl( 1 - \frac{1}{2n} \Bigr) \label{eq:4.5}\\
  G_{i,2} &\equiv (2n-2i)\,\ln\Bigl( 1 - \frac{i}{n} \Bigr) \label{eq:4.6}\\
  G_{i,3} &\equiv 2i \label{eq:4.7}\\
  G_{i,4} &\equiv \frac{1}{2}\,\ln\Bigl( 1 - \frac{1}{n} \Bigr) \label{eq:4.8}\\
  G_{i,5} &\equiv \sum_{j\ \text{odd}} c_j \biggl( \frac{1}{n^j} -
  \frac{1}{(n-i)^j} \biggr) \label{eq:4.9}
\end{align}
We have used the Sterling series to expand $\ln n!$.
We also note $c_1 = -\frac{1}{24}$.
$H_i$ and $K_i$ are easily developed as a series in inverse powers of $n$.

\section{{$k = 1$} and {$k = 0$}} 
Not only is $k = 1$ the first case, but it is different from $k \ge 2$ in some
essential ways.
We proceed to compute $\alpha_0$ for $k = 1$.
From eq.\ \ref{eq:4.2} we have
\begin{equation}\label{eq:5.1}
  \alpha_0 = \EE\bigl(
    (1+H_{i+1})(1+K_{i+1}) - (1+H_{i})(1+K_{i})
  \bigr)
\end{equation}
From eq.\ $(18)$ of \cite{Per}, and eq.\ $(45)$ of \cite{Per} for $q_1$ therein,
one gets
\begin{equation}\label{eq:5.2}
  H_i = i(i-1)\Bigl( -1 + \frac{1}{2r} \Bigr) \frac{1}{n} + \OO\Bigl(
  \frac{1}{n^2} \Bigr)
\end{equation}
Using eq.\ \eqref{eq:4.3}--\eqref{eq:4.9} and the value of $c_1$ thereafter one
gets
\begin{equation}\label{eq:5.3}
  K_i = (i^2 - i)\frac{1}{n} + \OO\Bigl( \frac{1}{n^2} \Bigr)
\end{equation}
There follows
\begin{thm}\label{thm:5.1}
  For $k = 1$
  \begin{equation}\label{eq:5.4}
    \alpha_0 = \frac{i}{rn} + \OO\Bigl( \frac{1}{n^2} \Bigr)
  \end{equation}
\end{thm}
One easily gets
\begin{thm}\label{thm:5.2}
  For $k = 0$
  \begin{equation}\label{eq:5.4}
    \alpha_0 = 1 + \OO\Bigl( \frac{1}{n} \Bigr)
  \end{equation}
\end{thm}

\section{$k \ge 2$}
The goal of this section is proving the following theorem.
\begin{thm}\label{thm:6.1}
  For $k \ge 2$
  \begin{equation}\label{eq:6.1}
    \biggl[ \frac{1}{n^d} \biggr] \alpha_0 = \begin{cases}
      \hfil 0 & d < k-1\\
      \displaystyle\frac{(k-2)!}{r^{k-1}} & d = k-1
    \end{cases}
  \end{equation}
  where as elsewhere $[\frac{1}{n^d}]Q$ is the coefficient of the
  $\frac{1}{n^d}$ term in an expansion of $Q$ into inverse powers of $n$.
\end{thm}
From Section \ref{sec:8} using the Second Identity we have
\begin{equation}\label{eq:6.2}
  \alpha_0 = \EE \biggl( \Bigl( 1 + t_+ + \frac{1}{2}t_+^2 + \cdots\Bigr) -
  \Bigl( 1 + t_- + \frac{1}{2}t_-^2 + \cdots\Bigr) \biggr)
\end{equation}
where with
\begin{equation}\label{eq:6.3}
  1 + U_i = (1 + H_i)(1 + K_i)\\
\end{equation}
one defines
\begin{equation}
 t_+ = \sum_{\ell \in \mathcal{L}^+} \binom{k}{\ell}
  \Bigl( U_{i+\ell} - \frac{1}{2} (U_{i+\ell})^2 + \frac{1}{3} (U_{i+\ell})^3
  \cdots \Bigr)\label{eq:6.4}\\
\end{equation}
\begin{equation}
  t_- = \sum_{\ell \in \mathcal{L}^-} \binom{k}{\ell}
  \Bigl( U_{i+\ell} - \frac{1}{2} (U_{i+\ell})^2 + \frac{1}{3} (U_{i+\ell})^3
  \cdots \Bigr)\label{eq:6.5}
\end{equation}
We treat the terms written explicitly in \eqref{eq:6.2}; the induction to
higher powers of $t$ is trivial.
\begin{align}
  \biggl[ \frac{1}{n^d} \biggr] E(t_+ - t_-) &= \biggl[ \frac{1}{n^d} \biggr]
  \sum_\ell \binom{k}{\ell} (-1)^{k+\ell} \Bigl( U_{i+\ell} - \frac{1}{2}
  (U_{i+\ell})^2 + \frac{1}{3} (U_{i+\ell})^3 \cdots \Bigr)\label{eq:6.6}\\
  &= \begin{cases}
    \hfil 0 & d < k - 1\\
    \displaystyle\frac{(k-2)!}{r^{k-1}} & d = k-1
  \end{cases}\label{eq:6.7}
\end{align}
by the First Identity, Theorem \ref{thm:7.1}.
Thus we want to prove that the higher powers of $t$'s make no contribution in
\eqref{eq:6.2}!
This is amazing when one first sees it.
\par We want to show
\begin{equation}\label{eq:6.8}
  \biggl[ \frac{1}{n^d} \biggr] (t_+^2 - t_-^2) = 0 \quad \text{for} \quad d
  \le k - 1
\end{equation}
We proceed by looking at the powers of $\frac{1}{n}$.
\begin{equation}\label{eq:6.9}
  \biggl[ \frac{1}{n^d} \biggr] (t_+^2 - t_-^2) = \sum_{s=1}^{d-1} \Biggl[
    \biggl( \biggl[ \frac{1}{n^s} \biggr] t_+ \biggr)
    \biggl( \biggl[ \frac{1}{n^{d-s}} \biggr] t_+ \biggr)
  - \biggl( \biggl[ \frac{1}{n^s} \biggr] t_- \biggr)
    \biggl( \biggl[ \frac{1}{n^{d-s}} \biggr] t_- \biggr) \Biggr]
\end{equation}
All we need to complete a proof of \eqref{eq:6.8} is to show
\begin{equation}\label{eq:6.10}
  \biggl[ \frac{1}{n^s} \biggr] t_+ = \biggl[ \frac{1}{n^s} \biggr] t_- \qquad
  1 \le s \le d - 1
\end{equation}
But this follows from \eqref{eq:6.6},\eqref{eq:6.7} above.
Pretty neat.

\section{First Identity}
For convenience we introduce
\begin{equation}\label{eq:7.1}
  F_i \equiv (1 + H_i)(1 + K_i)
\end{equation}

\begin{thm}[First Identity]\label{thm:7.1}
  For all $r$, $i \ge 0$, and $k \ge 2$
  \begin{equation}\label{eq:7.2}
    \sum_{\ell=0}^k \binom{k}{\ell} (-1)^{\ell+k} \biggl[ \frac{1}{n^{k-1}}
    \biggr] \sum_{m=1}^{k-1} (-1)^{m+1} \frac{1}{m} \bigl( F_{(i+\ell)} - 1
    \bigr)^m = \frac{(k-2)!}{r^{k-1}}
  \end{equation}
\end{thm}
\begin{thm}\label{thm:7.2}
  For all $r$, and $k \ge 2$
  \begin{equation}\label{eq:7.3}
    \biggl[ \frac{1}{n^{k-1}} \biggr] \ln(F_i)
  \end{equation}
  has highest power of $i = i^k$, and this term is
  \begin{equation}\label{eq:7.4}
    \frac{(k-2)!}{k!}\frac{i^k}{r^{k-1}}
  \end{equation}
\end{thm}
For example for $k = 3$
\begin{equation}\label{eq:7.5}
  \biggl[\frac{1}{n^2}\biggr] \ln(F_s) = -\frac{1}{12} \frac{s\bigl(3r^2s - 3r^2
  - 12rs - 2s^2 + 12r + 9s - 7\bigr)}{r^2}
\end{equation}
\par We now note
\begin{equation}\label{eq:7.6}
  \sum_{\ell=0}^k \binom{k}{\ell} (-1)^{\ell+k} \ell^d = \begin{cases}
    \hfil 0 & d < k\\
    k! & d = k
  \end{cases}
\end{equation}
that follows from
\begin{equation}\label{eq:7.7}
  \sum_{\ell=0}^k \binom{k}{\ell} (-1)^{\ell+k} \ell^d = \Delta^k i^d
\end{equation}
which like $(\frac{d}{dx})^k x^d$ has values in \eqref{eq:7.6}.
From eq.\ \eqref{eq:7.6} one can deduce that Theorem \ref{thm:7.1} follows from
Theorem \ref{thm:7.2}, which we proceed to prove.
\begin{equation}\label{eq:7.8}
  \biggl[ \frac{1}{n^{k-1}} \biggr] \ln(F_i) = 
  \biggl[ \frac{1}{n^{k-1}} \biggr] \ln(1+H_i)
  + \biggl[ \frac{1}{n^{k-1}} \biggr] \ln(1+K_i)
\end{equation}
From eqs.\ \eqref{eq:3.4}--\eqref{eq:3.5} with $k \ge 2$ we see that the highest
power of $i$ in $[\frac{1}{n^{k-1}}]\ln(1+H_i)$ is $k$ and its coefficient is
\begin{equation}\label{eq:7.9}
  \frac{1}{k(k-1)} \biggl( \frac{1}{r^{k-1}} - 2 \biggr)
\end{equation}
To study $[\frac{1}{n^{k-1}}]\ln(1+K_i)$ we turn to equations
\eqref{eq:4.3}--\eqref{eq:4.9}.
We note the highest power of $i$ arises from the expansion of the term
$G_{i,2}$, eq.\ \eqref{eq:4.6}, and $[\frac{1}{n^{k-1}}]\ln(1+K_i)$ has highest
power $i$
\begin{equation*}
  \frac{2}{k(k-1)}
\end{equation*}
So
\begin{equation}\label{eq:7.10}
  \biggl[ \frac{1}{n^{k-1}} \biggr] \ln(F_i) = \frac{(k-2)!}{k!}
  \frac{1}{r^{k-1}} i^k
\end{equation}
Quod erat demonstrandum.

\section{Second Identity}\label{sec:8}
We start with some simple manipulations
\begin{equation}\label{eq:8.1}
  \prod_i (1+x_i)^{e_i} = e^{\sum e_i\ln(1+x_i)} = 1 + \Bigl( \sum e_i\ln(1+x_i)
  \Bigr) + \frac{1}{2!} \Bigl( \sum e_i\ln(1+x_i) \Bigr)^2 + \cdots
\end{equation}
We introduce a new notation
\begin{equation}\label{eq:8.2}
  (1 + H_i)(1 + K_i) \equiv 1 + U_i
\end{equation}
and substitute $U_i$ for $x_i$ and $\binom{k}{\ell}$ for $e_i$ in \eqref{eq:8.1}
\begin{equation}\label{eq:8.3}
  \prod_{\ell \in \mathcal{L}^+} (1 + U_{i+\ell})^{\binom{k}{\ell}} = 1 + t _+ +
  \frac{1}{2} t_+^2 + \frac{1}{3!} t_+^3 \cdots
\end{equation}
where
\begin{equation}\label{eq:8.4}
  t _+\equiv \sum_{\ell \in \mathcal{L}^+} \binom{k}{\ell} \biggl( U_{i+\ell} -
  \frac{1}{2} (U_{i+\ell})^2 + \frac{1}{3} (U_{i+\ell})^3 \cdots \biggr)
\end{equation}
The Second Identity consists of \eqref{eq:8.3} and \eqref{eq:8.4} and the same
expressions with $\mathcal{L}^+$, $t_+$ replaced by $\mathcal{L}^-$, $t_-$.

\section{Completion}
If there were no ``contributor'' contributions to $m_i$, see Section
\ref{sec:3}, we would be through since then $\beta$ would be zero, see eq.\
\eqref{eq:2.5}.
We note $\alpha$ would then be equal to $\alpha_0$ which is greater than zero,
except for $k = 1$, $i = 0$.
The single case $k = 1$, $i = 0$ need not be considered since in fact $\Delta
d(0) = 0$.
\par It is a straight forward, if fussy, computation to show that for $k \le 6$ the leading term in $\alpha$ 
in powers of $n$ does not depend on ``contributors.'' For $k = 7$ the
leading term does depend on $\varepsilon_4$, and the current line of proof fails
for $k \ge 7$.
\begin{thebibliography}{1}
	
  \bibitem{BFP}
    Butera, P., Federbush, P., and Pernici, M., \textit{A positivity property of
    the dimer entropy of graphs,} Physica A \textbf{421} (2015) 208.

  \bibitem{Per}
    Pernici, M., \textit{$1/n$ expansion for the number of matchings on regular
    graphs and monomer-dimer entropy,} J. Stat.\ Phys.\ \textbf{168} (2017) 666.

  \bibitem{Wan}
    Wanless, I. M., \textit{Counting Matchings and Tree-like Walks in Regular
    Graphs,} Combinatorics, Probability and Computing \textbf{19} (2010) 463.

  \bibitem{Bol}
    Bollobas, B., \textit{A probabilistic proof of an asymptotic formula for the
    number of labelled regular graphs,} Eur.\ J. Combin.\ \textbf{1} (1980)
    311.

\end{thebibliography}
\end{document}
---------------1710010918129--
