Content-Type: multipart/mixed; boundary="-------------1607030815429"
This is a multi-part message in MIME format.
---------------1607030815429
Content-Type: text/plain; name="16-45.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="16-45.comments"
5 pages
---------------1607030815429
Content-Type: text/plain; name="16-45.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="16-45.keywords"
cluster expansion, 0-1 matrices
---------------1607030815429
Content-Type: application/x-tex; name="permclusexp.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="permclusexp.tex"
\documentclass{article}
\usepackage{amsfonts,amsmath}
\mathchardef\mhyphen="2D % Define a "math hyphen"
\usepackage[a4paper]{geometry}
\usepackage{microtype}
\def\Z{\mathbb Z}
\def\zo/{$0\mkern2mu\mhyphen1$}
\def\Ex{E_{\times}}
\def\nn/{$n \times n$}
\def\a{\alpha}
\newtheorem{conj}{Conjecture}
\DeclareMathOperator\perm{perm}
\title{A Mysterious Cluster Expansion Associated to the Expectation Value of the Permanent of 0-1 Matrices}
\date{\today}
\author{Paul Federbush\\
Department of Mathematics\\
University of Michigan\\
Ann Arbor, MI, 48109-1043}
\begin{document}
\maketitle
\begin{abstract}
We consider two ensembles of \zo/ $n\times n$ matrices.
The first is the set of all $n\times n$ matrices with entries zeroes and ones such that all column sums and all row sums equal $r$, uniformly weighted.
The second is the set of $n \times n$ matrices with zero and one entries where the probability that any given entry is one is $r/n$, the probabilities of the set of individual entries being i.i.d.'s.
Calling the two expectation values $E$ and $E_B$ respectively, we develop a formal relation
\begin{equation}
\label{A1}
\tag{A1}
E(\perm(A)) = E_B(\perm (A)) e^{\sum_2 T_i}.
\end{equation}
We use two well-known approximating ensembles to $E$, $E_1$ and $E_2$. Replacing $E$ by either $E_1$ or $E_2$ we can evaluate all terms in \eqref{A1}.
The equality of \eqref{A1} holds for either $E_1$ or $E_2$, and the terms $T_i$ have amazing properties. We conjecture \eqref{A1} is true for $E$, and all these properties hold also for $E$.
\end{abstract}
We happily inform the reader that no knowledge of cluster expansions is necessary to read and understand this paper, but for those interested a general exposition is given in \cite{b}.
The development of this paper is a short sequence of computational steps.
We will clearly state which steps are rigorous and which are formal.
There will be no theorems, but the formalism has intrinsic beauty.
Our results will be computer computations (in integer arithmetic) of a large number of terms in the developed expansion, that again have a beauty and compelling force for theorems to be proved.
We begin with the definitions of the objects we will deal with. For an $n\times n$ matrix $A$, in addition to the permanent of $A$, $\perm(A)$, we will need information about the permanents of submatrices of $A$. Given a set of $i$ of the rows of $A$, and a set of $i$ of the columns of $A$, an $i\times i$ submatrix is determined. The sum of the permanents of all such $i\times i$ submatrices of $A$ we denote by $\perm_i(A)$.
We will consider a number of ensembles of $n\times n$ matrices, each with an associated expectation:
The first ensemble is the set of all \zo/ \nn/ matrices with all row and column sums equal to~$r$.
We let $E$ denote the expectation determined by a uniform weighting in this ensemble.
The second is the Bernoulli random matrix ensemble where each entry independently has a probability $p=r/n$ of being one, and is zero otherwise.
We denote the associated expectation by~$E_B$.
The third ensemble is the set of nonnegative integer matrices determined by the first measure in Section~4 of \cite{fkm}.
It is in fact determined as a uniformly weighted sum of $r$ independent random permutation matrices.
Note that this is not necessarily a set of \zo/ matrices, but all row and column sums equal $r$. We denote the expectation here by $E_1$.
The fourth ensemble is again a set of nonnegative integer matrices determined by the second measure in Section~4 of \cite{fkm}.
We denote the associated expectation by $E_2$.
We will later work with a matrix $A$ from the first ensemble and $B$ from the second and then use a product expectation
\begin{equation}
\label{1}
\Ex (f(A,B)) = EE_B(f(A,B)).
\end{equation}
Our initial object of study is the expectation of the permanent in our first ensemble
\begin{equation}
\label{2}
E(\perm(A)).
\end{equation}
We write $A$ as a sum
\begin{equation}
\label{3}
A = B + ( A - B )
\end{equation}
where $B$ lies in our second ensemble, and we get
\begin{equation}
\label{4}
E(\perm(A))=\Ex (\perm(B+(A-B))).
\end{equation}
We write
\begin{equation}
\label{5}
A-B\equiv C
\end{equation}
and note that
\begin{equation}
\label{6}
\Ex (\perm(B+C))=\sum_\a E_B(\perm(B_{\bar\a})) \Ex (\perm(C_\a))
\end{equation}
where $C_\a$ denotes some submatrix of $C$ (obtained by a selection of a set of the columns and an equal-sized set of the rows) and $B_{\bar\a}$ is the dual submatrix of $B$ (obtained using the complementary set of rows and columns).
The sum over $\a$ is over all such submatrices.
Equation~\eqref{6} follows from the definition of the permanent, and a little thinking
We now use the very special properties here that the random variables in $B_{\bar \a}$ and $C_\a$ are statistically independent, and that the expectations on the right side of \eqref{6} each depend only on the size of the respective submatrices. It follows, from these two very special features, that from \eqref{6} one gets
\begin{equation}
\label{7}
E(\perm(A)) = \sum_{i=0}^n f_i\, E_B(\perm_{n-i}(B)) \Ex (\perm_i(C)).
\end{equation}
Here we have set $\perm_n(A)=\perm(A)$ (for \nn/ matrices) and $\perm_0(A)=1$. $f_i$ is 1 over the number of distinct $i\times i$ submatrices:
\begin{equation}
\label{8}
f_i = \frac{1}{\binom n i ^2}.
\end{equation}
One should check that \eqref{6} and \eqref{7} trivially are equal, using the special properties above.
We now study $\Ex (\perm_i(C))$. Here we get
\begin{equation}
\label{9}
\Ex (\perm_i(C)) = \sum_{k=0}^i f(i,k)\, E(\perm_{i-k}(A))(-1)^k E_B(\perm_k(B))
\end{equation}
where
\begin{equation}
\label{10}
f(i,k) = \frac{\binom n i ^2 \binom i k^2}{\binom n k ^2 \binom n {i-k}^2}.
\end{equation}
We note
\begin{equation}
\label{11}
f_i = f(n,i).
\end{equation}
The development of equation~\eqref{9} is as the development of~\eqref{7}, but requiring more careful attention to the nitty-gritty.
We do a little calculation from the easy formula
\begin{equation}
\label{12}
E_B(\perm_i(B)) = \binom n i^2 i!\, (r/n)^i
\end{equation}
to get
\begin{equation}
\label{13}
\frac{E_B(\perm_{n-i}(B))}{E_B(\perm (B))} = \frac{1}{r^i} \frac{n^i (n-i)!}{n!} \cdot \frac1{f_i}.
\end{equation}
We put together the above formulas to get our expression for $E(\perm(A))$:
\begin{equation}
\label{14}
E(\perm(A)) = E_B(\perm(B)) \cdot \biggl(1 + \sum_{i=2}^n C_i\biggr)
\end{equation}
with
\begin{equation}
\label{15}
C_i=
\biggl(
\frac{1}{r^i} \frac{n^i (n-i)!}{n!}
\biggr)
\cdot \sum _{k=0}^ i f(i,k)\, E(\perm_{i-k}(A)) (-1)^k E_B(\perm_k(B)).
\end{equation}
We have used the fact that $C_1 =0$ (and $C_0=1$). We emphasize so far that everything is ``rigorous'', formulae~\eqref{14} and~\eqref{15} give a neat expression for $E(\perm(A))$.
And also note that all the expectations involving $B$ are easily known by~\eqref{12}.
We now construct our cluster expansion
\begin{equation}
\label{16}
\biggl(
1 + \sum_{i=2}^n C_i
\biggr)
\,\,
\textrm{``}\!=\!\textrm{''}
\,\,
e^{\sum_{i=2}^\infty T_i}.
\end{equation}
This is our first ``formal'' step.
The $T_i$ are selected so that if one expands the two sides in powers of the matrix entries, the two sides are equal power by power. We present the first few $T_i$ so that one may see the pattern:
\begin{subequations}
\begin{align}
\label{17a}
T_2 &= C_2
\\
\label{17b}
T_3 &= C_3
\\
\label{17c}
T_4 &= C_4 - \tfrac12 T_2^2
\\
\label{17d}
T_5 &= C_5 - T_3 T_2
\\
\label{17e}
T_6 &= C_6 - T_4 T_2 - \tfrac16 T_2^3 - \tfrac12 T_3^2.
\end{align}
\end{subequations}
I hope we have not insulted your intelligence by listing so many of the terms.
As we mentioned, the terms in \eqref{14}, \eqref{15} in the $E_B$ expectations are all known by \eqref{12}.
Of those in the $E$ expectations the only term we know exactly is ( a well known result )
\begin{equation}
\label{18}
E(\perm_2(A)) = \tfrac12 nr(rn-2r+1).
\end{equation}
We are thus motivated to consider the formulas of \eqref{14}, \eqref{15} as developed using $E_1$ or $E_2$ instead of $E$. The formal procedure we followed would have given the same form for \eqref{14}, \eqref{15} with $E$ replaced by either $E_1$ or $E_2$. All the expectations using $E_1$ or $E_2$ are known from Section~4 of \cite{fkm} as follows
\begin{align}
E_1(\perm_m(A)) &= \frac{1}{(n!)^r} \binom n m ^2 \sum _{m_1,\dots,m_r\in \Z_+,\, m_1+\dots+m_r = m} \frac{m!(n-m_1)!\cdots (n-m_r)!}{m_1! \cdots m_r !}
\\
E_2(\perm_m(A)) &= \binom n m ^2 \frac{r^{2m} m! (rn-m)!}{(rn)!}
\end{align}
We callect the information we have obtained from computer computations as support for a few amazing conjectures.
\begin{conj}
\label{c1}
Using $E$, $E_1$, or $E_2$ we have that the following limit exists:
\begin{equation}
\label{21}
\lim_{n\to\infty} \frac1n T_i(n).
\end{equation}
\end{conj}
For $E$ we can only test this for $T_2$, where it is true.
For $E_1$ and $E_2$ we have verified this for $i \leq 25$. (It would be easy to test this for much higher $i$. Someone should prove this theorem for $E_1$ or $E_2$.)
One will realize that the existence of the limit in \eqref{21} is amazing if one considers that the $C_i(n)$ may behave proportional to $n^{i/2}$ for large $n$ (by computer computation), so much cancellation must take place for the limit in \eqref{21} to exist.
\begin{conj}
Using $E$, $E_1$, or $E_2$
\begin{equation}
\label{22}
\lim_{n\to \infty} \frac 1 n T_i (n) = \frac{a_i}{r^{h(i)}} + \frac{b_i}{r^{h(i) + 1}}
\end{equation}
where $h(i) = i/2$ if $i$ is even and $=(i+1)/2$ if $i $ is odd.
\end{conj}
This has been verified for the same cases as discussed under Conjecture~\ref{c1}.
Again someone should prove it for $E_1$ or $E_2$.
It appears that $E_1$ and $E_2$ have the same values of $a_i$ and $b_i$. We collect the first few values of $a_i$ and $b_i$ for the different expectations.
For $E$ one has
\begin{equation}
a_2=\tfrac12, \quad b_2 =0 .
\end{equation}
For $E_1$ and $E_2$ one has
\begin{subequations}
\begin{align}
\label{24a}
a_2 &=\tfrac12 , & b _ 2 &=0 \\
a_3 &=\tfrac23 , & b _ 3 &= 0 \\
a_4 &=-\tfrac12 , & b _ 4 &=\tfrac54 \\
a_5 &=-2 , & b _ 5 &=\tfrac{14}5 \\
a_6 &=\tfrac56 , & b _ 6 &=-\tfrac{42}6 \\
a_7 &=6 , & b _ 7 &=-\tfrac{168}7 \\
a_8 &=-\tfrac{14}8 , & b _ 8 &=\tfrac{252}8.
\label{24g}
\end{align}
\end{subequations}
If we assume
\begin{equation}
\frac1n \lim \sum T_i = \sum \lim \frac1n T_i,
\end{equation}
our second formal step, one has for either $E_1$ or $E_2$ (using \eqref{22} and \eqref{24a}--\eqref{24g})
\begin{equation}
\label{26}
\frac1n \lim \sum T_i =
\frac{1}{2} \,\frac{1}{r} +
\frac{1}{6}\, \frac{1}{r^2} +
\frac{1}{12} \,\frac{1}{r^3} +
\frac{1}{20}\, \frac{1}{r^4}....
\end{equation}
As is usual in studying cluster expansions one studies the $\lim_{n\to \infty} \frac 1 n ( \, \ )$.
It is easy to show for $s = 1,2$ that
\begin{equation}
\lim_{n\to \infty}
\frac1n E_s (\perm(A)) =
\lim_{n\to \infty} \frac1n E_B(\perm(A)) + 1 + (r-1)\ln\biggl(1-\frac1r\biggr)
\end{equation}
and this by \eqref{26} is the same as
\begin{equation}
\label{28}
\lim_{n\to \infty} \frac1n E_s(\perm(A)) \simeq \lim_{n\to \infty}E_B(\perm(A)) + \frac1n \lim \sum T_i
\end{equation}
where the two sides are asymptotically equal to as high a power of $1/r$ as determined by the 25 first terms in the sum of $T_i$. One certainly has equality of the two sides of \eqref{28}.
Our most daring conjecture is that
\begin{equation}
\lim_{n\to\infty} \frac1n E(\perm(A)) = \lim_{n\to \infty} \frac1n E_s(\perm(A)), \quad s =1,2
\end{equation}
but in fact this is pretty broadly believed!?
At the bottom there is a mystery. What theoretical mechanism gives rise to the structure of this cluster expansion?
\begin{thebibliography}{1}
\bibitem{b}
Brydges, D.,
A short course on cluster expansions,
{\em Ph\'enom\`enes critiques, syst\`emes al\'eatoires, th\'eories de gauge}, {P}arts {I}, {II} ({L}es {H}ouches, 1984),
North-Holland, Amsterdam, 1986,
pp.~129--183,
\bibitem{fkm}
Friedland, S. and Krop, E. and Markstr{\"o}m, K.,
{\em On the number of matchings in regular graphs},
Electron. J. Combin., {\bf 15} (2008), pp.~1--28.
\end{thebibliography}
\end{document}
---------------1607030815429--