Content-Type: multipart/mixed; boundary="-------------1408031005927"
This is a multi-part message in MIME format.
---------------1408031005927
Content-Type: text/plain; name="14-63.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="14-63.comments"
20 pages, 1 figure
---------------1408031005927
Content-Type: text/plain; name="14-63.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="14-63.keywords"
dimer, graph, positivity
---------------1408031005927
Content-Type: application/x-tex; name="graph_posprelim.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="graph_posprelim.tex"
\documentclass[prb,aps,floats,amssymb,showkeys,showpacs,preprint,
superscriptaddress]{revtex4}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{amsmath}
\usepackage{epsfig,bm}
\usepackage{rotating}
\maxdeadcycles=1000
\begin{document}
\title{Dimer entropy of a graph and a positivity property, preliminary version}
\author{P. Butera}
\email{paolo.butera@mib.infn.it}
\affiliation
{Dipartimento di Fisica Universita' di Milano-Bicocca\\
and\\
Istituto Nazionale di Fisica Nucleare \\
Sezione di Milano-Bicocca\\
3 Piazza della Scienza, 20126 Milano, Italy}
\author{P. Federbush}
\email{pfed@umich.edu}
\affiliation
{Department of Mathematics\\
University of Michigan \\
Ann Arbor, MI 48109-1043, USA\\}
\author{M. Pernici}
\email{mario.pernici@mi.infn.it}
\affiliation
{Istituto Nazionale di Fisica Nucleare \\
Sezione di Milano\\
16 Via Celoria, 20133 Milano, Italy}
\date{\today}
\begin{abstract}
The entropy of a monomer-dimer system on an infinite bipartite
lattice can be written as a mean-field part plus a series expansion
in the dimer density. In a previous paper it has been conjectured
that all coefficients of this series are positive. Analogously on a
connected regular graph with $v$ vertices, the ``entropy'' of the
graph ${\rm ln} N(i)/v$, where $N(i)$ is the number of ways of
setting down $i$ dimers on the graph, can be written as a part
depending only on the count of the dimer configuration over the
completed graph plus a Newton series in the dimer density on the
graph. In this paper, we investigate for which connected regular
graphs all the coefficients of the Newton series are positive (for
short, these graphs will be called positive). In the class of
connected regular bipartite graphs, up to $v=20$, all the non
positive graphs have vertices of degree $3$. From $v=14$ to $v=28$,
and degree $3$, a few violations of the positivity occur, but their
frequency decreases with increasing $v$. We conjecture that
for each degree $r$ the frequency of violations, in the class of the
$r-$regular bipartite graphs, goes to zero as $v$ tends to
infinity.
This graph-positivity property can be extended to non-regular or
non-bipartite graphs.
We have examined a large number of rectangular grids of size $N_x
\times N_y $ both with open and periodic boundary conditions. We
have observed positivity violations only for $min(N_x, N_y) = 3$ or
$4$.
\end{abstract}
\pacs{ 05.50.+q, 64.60.De, 75.10.Hk, 64.70.F-, 64.10.+h}
\keywords{Dimer problem }
\maketitle
\section{ Introduction}
For periodic cubical $d$-dimensional lattices with even length
sides, the number of dimer configurations covering a fraction $p$ of
the vertices (called ``matchings'' of the lattice graph in the
language of graph theory) has long been studied. As the number of
vertices $v$ tends to infinity, the number of distinct dimer
configurations grows\cite{hamm} as $\exp(v\lambda_d(p))$, where
$\lambda_d(p)$ is called the dimer entropy and $p$ is the dimer density.
In Ref.[\onlinecite{FF}],
the entropy has been written as the sum of a mean field term and of a
series expansion in the dimer density, computed through order $6$; in
Refs.[\onlinecite{bpyl,bfp}] this series has been extended at least
through the order $20$.
More precisely, for lattices of dimension $2
\le d \le 4$ the first $24$ coefficients were derived\cite{bpyl,bfp},
while 20 coefficients have been obtained for all $ d> 4$
(in $d=5, 6$ respectively $22, 21$ coefficients have been computed).
In the case of
$d=1$, all coefficients are positive and have long been known. It is
striking that, for any integer $d$, all the series coefficients that
we could compute, are positive. This led us to conjecture\cite{bfp}
that: {\it for all (hyper)-cubical lattices the series coefficients
are all positive.} Moreover, after examining the series coefficients
for various non-square bipartite lattices, we were led to extend the
conjecture to all bipartite lattices (i.e. to the lattices in which
the sites can be divided into even and odd, such that no edge connects
two vertices with the same parity).
We observe that, in analogy with the case of infinite bipartite
lattices, on a connected simple undirected regular bipartite graph $G$
with set of vertices $V$ and set of edges $E$, the ``graph dimer
entropy'' ${\rm ln} N(i)/v$ - where $N(i)$ is the number of ways of
setting down $i$ dimers on the graph and $v=|V|$ is the number of
vertices of the graph - can be written as a part depending on the
dimer configurations counting over the completion of the graph and a
Newton expansion in the dimer density on the graph. If all the
coefficients of the Newton series are positive, we shall say that the
graph satisfies the {\it graph-positivity} property. For not too
large number of vertices $v$, we have generated {\it all} regular
(bi)connected bipartite graphs (RBB graphs from now on) using the {\it
Nauty} program\cite{nauty} via the {\it Sage} interface\cite{Sage}.
In examining all RBB graphs with vertices of degree $3$ for $v \le
28$, we have observed no violations of the graph positivity for $v <
14$ vertices. A single violation is observed for $v=14$. For $v \ge
14$, as the number $v$ of vertices increases, the frequency of
violations decreases. No positivity violation occurs in
all RBB graphs with vertices of degree greater than $3$, up to $v=20$.
For $v=22$ and degree $4$ there are two violations.
For
$r-$regular graphs with $r>4$ the absence of violations could be checked up
to $v=20$. Although we found no positivity violation for RBB graphs
with vertex degree larger than $4$ in the large sample studied, we can point
out examples of positivity violation occurring for larger values of
$v$, in some $r-$regular graphs with $r=5,6,7,8$, which were defined
in Ref.[\onlinecite{Wanless}]. We conjecture that, for RBB graphs
of any degree {\it the
frequency of positivity violations becomes vanishingly small as $v$
becomes large}.
An interesting observation emerging from the systematic study of RBB
graphs with $v \le 28$ and degree $3$, is that the average order of
the automorphism group of the graphs not satisfying the
graph-positivity property is larger by an order of magnitude than the average
order of the automorphism group for all RBB graphs.
In addition to this systematic survey of RBB graphs, we have focused
the attention on the class of square and hexagonal lattices with
periodic boundary conditions, which are also RBB graphs. In the case
of rectangular grids of sizes $N_x \times N_y$ with periodic boundary
conditions, we examined the cases $N_x=N_y$ up to sizes $N_y=12$. For
$N_x \ge N_y$ we found positivity violations only for $N_y=4$ and $N_x
\ge 432$.
For periodic hexagonal lattices of
sizes $N_x \times N_y$ in the brick-wall representation, positivity is valid
when $N_x \ge N_y$, apart from the case $N_x=N_y=4$,
while violations occur for $N_x < N_y$. We have tested
this class of grids up to the size $14 \times 14$.
This positivity property can also be studied for graphs which are not RBB.
Since we originally proposed the positivity conjecture for infinite
square lattices, it is natural to consider also rectangular grids with
open boundary conditions.
In the case of rectangular grids $N_x \times N_y$ with open boundary
conditions, in the cases $N_x = N_y$ we considered up to the case $N_y=19$;
the graph positivity holds except for the case of $N_x \times 3$ graphs.
We have also examined the case of rectangular grids $N_x \times N_y$
with boundary conditions periodic only in the $y$ direction. Again, we
found positivity violations only for narrow grids, as in the case of
rectangular grids with periodic and with open boundary conditions.
We considered also several cubic grids of sizes $N_x\times N_y\times N_z$
with open boundary conditions, up to the $5\times 5\times 4$ case:
no positivity violation was observed, apart from the $N_x\times 2\times 2$
case, which is isomorphic to the $N_y=4$ rectangular grid case periodic
in the $y$-direction.
In the case of non-bipartite graphs, the positivity property is not
common. However there are exceptions for specific classes of graphs:
for example, we have singled out a sequence of ``nanotubes'' $C_{40+20
N}$, with $N$ the number of hexagonal strips, and have tested graph
positivity for $1 \le N \le 300$. All the nanotubes with $N > 7$ are
graph-positive.
To perform our study of graphs, it was necessary to compute the graph
matching generating polynomial
\begin{equation}
M(t) = \sum_{i=0}^{[v/2]} N(i)t^i
\end{equation}
where $N(i)$ is the number of configurations of $i$ dimers on the graph.
We used the algorithm discussed in [{\onlinecite{bpalg}] to perform the
computation.
The paper is organized as follows. In the second Section, we formulate
the graph positivity property. The third Section summarizes the
results of the graph tests for a variety of graphs and lattices. The
fourth Section contains our conclusions. In Appendix A, the graph
positivity is proven for polygons, for complete bipartite graphs and
for an approximate average distribution of graphs. In Appendix B the
positivity property is examined for a sequence of nanotubes.
\section{The positivity property for graphs}
To formulate the graph-positivity properly, let us turn now to a cubic
lattice graph $G$ with $v$ vertices of degree $2d$, and let $N(i)$ be
the number of ways of setting down $i$ dimers on the edges of $G$
(with no overlap). If we consider the sequence of larger and larger
periodic lattices used to compute the entropy $\lambda_d(p)$ on the
infinite lattice, one must have
\begin{equation}
\hat{\lambda_d}(\hat{p_i}) = \frac {1}{v} {\rm ln}N(i) \to
\lim_{v \to \infty} \frac {1}{v} {\rm ln}(\exp v\lambda_d)
=\lambda_d(p)
\label{ln}
\end{equation}
where the arrow indicates convergence as $v \to \infty$.
Here $i$ is related to $p$ by
\begin{equation}
\hat{p_i} = \frac{2i}{v} \approx p
\label{ip}
\end{equation}
where the integer $i$ is chosen to make this approximation best. We refer now
to the notation in Ref.[\onlinecite{FF}] observing from Eq.(5.9) of this Ref.
that
\begin{equation}
\lambda_d(p)=\frac{p}{2} {\rm ln}(2d) +\lim_{v \to \infty} \frac {1}{v}{\rm ln}Z
\label{ip2}
\end{equation}
Observe now that $Z$ can be factored into a ``mean field'' term $Z_0$
times the rest $Z^*$ as in Eq.(5.12) of Ref.[\onlinecite{FF}]
\begin{equation}
\lambda_d(p)=\frac{p}{2} {\rm ln}(2d)
+\lim_{v\to \infty} \frac {1}{v}{\rm ln}(Z_0)
+\lim_{v \to \infty} \frac {1}{v}{\rm ln}(Z^*) .
\label{ip3}
\end{equation}
\noindent
From Eq.(\ref{ln}) and from Eq.(5.11)
and (7.1) of Ref.[\onlinecite{FF}], we have
\begin{equation}
\frac {1}{v} {\rm ln}(\frac{N(i)}{(2d)^i} ) - \lim_{v \to \infty} \frac
{1}{v}{\rm ln}(Z_0) \to \sum_{k=2}a_k(d)p^k
\label{ip6}
\end{equation}
\noindent
with
\begin{equation}
\lim_{v \to \infty} \frac {1}{v}{\rm ln}(Z_0)= -\frac{p}{2} {\rm
ln}(p)- (1-p){\rm ln}(1-p) - \frac{p}{2}.
\label{ip7}
\end{equation}
It is an easy computation to show that for the graph $\bar G$, defined
as the completion of $G$ (namely the non-bipartite graph constructed
by connecting the vertices of $G$ in all possible ways), if we set
$\bar N(i)$ as the number of ways of setting down $i$ dimers on $\bar
G$ (without overlap),
\begin{equation}
\bar N(i) = \frac{v!}{(v-2i)!i!2^i}
\label{nbar}
\end{equation}
then
\begin{equation}
\frac {1}{v} {\rm ln}\frac{\bar N(i)}{(v-1)^i} \to \lim_{v \to \infty} \frac {1}{v}{\rm ln}(Z_0)
\label{ip8}
\end{equation}
\noindent
in the limit as $v \to \infty$ and with $i$ chosen as before in Eq.(\ref{ip}).
If one studies the definition of $Z_0$ in Ref.[\onlinecite{FF}], the
expression on the lhs of (\ref{ip8}) is seen to arise naturally. But
we get no theoretical understanding of why the completion of a graph,
rather than the bipartite completion, is taken. Indeed, one could have
in (\ref{ip8}) used a similar expression with the bipartite
completion, but one would have then ended with a less fruitful
definition of graph positivity. We now define
\begin{equation}
d(i)
\equiv {\rm ln}\frac{ N(i)}{(2d)^i} - {\rm ln}\frac{\bar N(i)}{(v-1)^i}
\label{ip9}
\end{equation}
\noindent
and see that
\begin{equation}
\frac{1}{v} d(i) \to \sum_{k=2}a_k(d)p^k
\label{ip10}
\end{equation}
\noindent
The rhs of Eq.(\ref{ip10}) is
the series part of the dimer entropy in Eq.(6) in [\onlinecite{bfp}],
where it is conjectured that the $a_k$ are all positive.
We now observe that as $v \to
\infty$, the finite difference derivatives at $i=0$ on the lhs of
Eq. (\ref{ip10}) become the derivatives on the rhs.
We write $\Delta$
for the finite difference derivative with respect to $i$. One has
\begin{equation}
\frac{v}{2}\Delta \approx \frac {d}{dp}
\label{ip11}
\end{equation}
\noindent
so differentiating Eq.(\ref{ip10}) once, one gets
\begin{equation}
\frac{1}{2}( d(i+1)-d(i)) \to \frac {d}{dp} \sum_{k=2}a_k(d)p^k.
\label{ip12}
\end{equation}
\noindent
%Continuing to differentiate we see that all finite difference
%derivatives of $d(i)$ are $\geq 0$.
Writing $d(i) = \hat{d}(\hat{p})$ with $\hat{p} = \frac{2 i}{v}$
and $h=\frac{2}{v}$,
one has the Newton expansion
\begin{equation}
\hat{d}(\hat{p}) = \sum_{k=0}^{v/2} \frac{\Delta_h^k[\hat{d}](0)}{k!} (\hat{p})_k
\end{equation}
where
$(\hat{p})_k = \hat{p}(\hat{p}-h)...(\hat{p}-(k-1)h) = (\frac{2}{v})^k (i)_k$,
$(i)_k$ is the falling factorial and $\Delta_h$ is the finite difference
with step $h$,
$\Delta_h \hat{d}(\hat{p}) = \frac{\hat{d}(\hat{p} + h) - \hat{d}(\hat{p})}{h}$.
We can now state the definition of graph positivity in greater
generality. Let $G$ be a simple regular connected bipartite (hence
``biconnected'') graph (RBB graph), with degree $q$ and with $v$
vertices. Let $\bar G$ be the completion (not the bipartite
completion) of $G$. Let $N(i)$ be the number of ways of laying down
$i$ dimers on $G$ (without overlap) and $\bar N(i)$ the same quantity
for $\bar G$. Define
\begin{equation}
\hat{d}(\hat{p}) = d(i)
= {\rm ln}\frac{N(i)}{q^i} - {\rm ln}\frac{\bar N(i) }{(v-1)^i} .
\label{ip13}
\end{equation}
and
\begin{equation}
\hat{\lambda}(\hat{p_i}) = R(i) +
\frac{h}{2} \sum_{k=0}^{v/2} \frac{\Delta_h^k[\hat{d}](0)}{k!} (\hat{p})_k
\label{entropy}
\end{equation}
where
\begin{equation}
R(i) =\frac{ 1}{v} {\rm ln}(\frac{q^i}{(v-1)^i}\bar N(i))
\end{equation}
Using the Stirling formula for large $v$
\begin{equation}
R(i) \approx \frac{1}{2}(p{\rm ln}(q) - p{\rm ln}(p) -2(1-p){\rm ln}(1-p) - p)
\end{equation}
Then $G$ satisfies graph positivity, if all the $d(i)$ are
non-negative, as are all terms derived by any number of non-trivial
finite difference derivatives i.e. if all terms in the sequence
$d(0), d(1),d(2),d(3),...$ are non-negative as are all terms in the sequence
$d(1) - d(0), d(2)-d(1), d(3)-d(2),....$, and the sequence
$d(2)-2d(1)+d(0), d(3)-2d(2)+d(1), d(4)-2d(3)+d(2),...$ etc.
In fact, it is sufficient that the first term $\Delta^k d(0)$
in each of these sequences is non-negative, non-negativity of the
other terms would then follow ($\Delta^k d(0) = 0$ for $k=0,1$ since
$d(0) = d(1) = 0$).
Equivalently, positivity means that all
the coefficients in the Newton series of $\hat{d}(\hat{p})$ are
non-negative.
It is natural to consider
the series Eq.(\ref{entropy}) also in the case of non-bipartite
regular graphs.
Notice that using $N(1) = \frac{v q}{2}$ one can rewrite
$d(i)$ in Eq.(\ref{ip13}) with no explicit dependence on degree of the vertices
\begin{equation}
d(i) = {\rm ln}(\frac{N(i)}{N(1)^i})
- {\rm ln}(\frac{\bar{N}(i)}{\bar{N}(1)^i})
\label{di}
\end{equation}
\noindent
for $i=1,..,r$, where $r$ is the maximum value of $i$ with $N(i)$ not
zero, and $\bar{N}(i)$ is the number of dimers on a complete
graph with $\bar{v}=2r$ vertices (if $\bar{v}$ = $v$ the graph has
perfect matchings). This suggests that it is worthwhile to
investigate also when the graph-positivity holds for non-regular graphs
or non-bipartite graphs.
\section{Tests of graph positivity}
As a first step, we have tested systematically the validity of the
positivity property on RBB graphs, exploring them in ascending number
of vertices, namely we have counted the configurations of $i$ dimers
on these graphs and checked the inequalites for the higher finite
differences. To generate systematically the RBB graphs, we have used
the {\it geng} program in the { \it Nauty} package\cite{nauty}, via
the {\it Sage} interface\cite{Sage}.
The first result of this extensive graph survey is that, while most RBB
graphs share the graph-positivity property, a few of them do not, see
Table \ref{tabdeg3} for the graphs with degree $3$.
There are no violations for $v < 14$.
\begin{table}[ht]
\caption{For RBB graphs with $14 \le v \le 28$ vertices of degree 3,
we have listed
the number of graphs in this class, the number of violations of the
graph positivity, the average order of the automorphism group of
graphs $ng$, the average order of this group $ngv$ for graphs
violating the positivity property.}
\begin{tabular}{|c|c|c|c|c|}
\hline
$v$ & number of graphs & violations & $ng$ & $ngv$\\
\hline
14& 13& 1 & 44.5 & 336.\\
16& 38& 2& 18.6 & 112.\\
18& 149& 2 & 15.1 & 176.\\
20& 703& 8 & 8.7 & 118.\\
22& 4132& 17 & 4.5 & 72.\\
24& 29579& 49 & 3.3 & 92.\\
26& 245627& 115 & 2.3 & 66.\\
28& 2291589& 514 & 1.9 & 55.\\
\hline
\end{tabular}
\label{tabdeg3}
\end{table}
{\bf to be changed:}
For $v=30$ and degree $3$ Nauty did not finish enumerating the graphs
in $...$ days.
Among the $23466000$ graphs produced, there are $3948$ violations.
For $3$-regular graphs, the frequency of violations decreases
with $v$, for $v \ge 14$.
It is interesting to observe that, in the cases considered in
Table \ref{tabdeg3}, the average order of the automorphism group of
the positivity-violating graphs is roughly an order of magnitude
greater than the average order of the automorphism group of all the
RBB graphs with the same degree, and that the ratio between these two
numbers increases with $v$.
In particular,
the positivity violating graph with $v=14$ is the most symmetrical of all
$v=14$ RBB graphs with degree $3$.
For degrees greater than $3$, there is no violation of positivity for
RBB graphs with number of vertices up to $v=20$. For $v=22$, there
are $2806490$ RBB graphs with vertices of degree $4$, and two violations.
The average order of the automorphism group of the positivity-violating graphs
is $1080.$, the average order of the automorphism group of all the
RBB graphs with $v=22$ and degree equal to $4$ is $1.5$.
Although in this systematic examination of graphs with low order we
found no positivity-violating graphs with degree greater than $4$, we
can exhibit cases of positivity-violating graphs with degree up to $8$,
belonging to the class of $k$-regular graphs $G_{k, f}$ considered in
Example $1$ of Ref.[\onlinecite{Wanless}]. The $G_{k,f}$ graphs, with
$f \ge 2$ and $k \ge 3$ are RBB graphs with degree $k$ and $v=2n$
vertices where $n=(k^2f+1)$. The vertex classes of $G_{k,f}$ are
\begin{equation}
U = \{s\} \cup \{u_{a,b,c} : 1 \le a \le k; 1 \le b \le k; 1 \le c \le f\}
\end{equation}
and
\begin{equation}
V = \{t\} \cup \{v_{a,b,c} : 1 \le a \le k; 1 \le b \le k; 1 \le c \le f\}
\end{equation}
The edges are $E = E_1 \cup E_2 \cup E_3$ with
\begin{eqnarray}
E_1 &=& \{(u_{a,b,c},v_{a,\beta,c}) : 1 \le a,b,\beta \le k; (b,\beta) \neq (1,1);
1 \le c \le f\} \nonumber \\
E_2 &=& \{(u_{a,1,c},v_{a,1,c+1}) : 1 \le a \le k; 1 \le c \le f-1\}
\nonumber \\
E_3 &=& \{(s,v_{a,1,1}) : 1 \le a \le k\}) \cup \{(u_{a,1,f},t) : 1 \le a \le k\}
\nonumber \\
\end{eqnarray}
\noindent
and dimer countings for almost complete and complete matching
\begin{equation}
\begin{split}
N(n-1) &= \frac{((k-1)!)^{kf}}{(k-2)^2}((k+2)^2(k-1)^{kf+2} + \\
&((k-2)^2kf - 3k^2 + 4)k^2 (k-1)^{(k-1)f} + \\
&2k^3(k-1)^{(k-2)f+1})
\label{n1wan}
\end{split}
\end{equation}
\begin{equation}
N(n) = k((k-1)!)^{kf}(k-1)^{(k-1)f}
\label{nwan}
\end{equation}
The graph
$G_{5, 2}$ with $102$ vertices of degree $5$ and the graph $G_{6, 2}$
with $146$ vertices of degree $6$ show a first violation in the case
of $\Delta^2 d(i)$ for some $i > 0$. In the derivatives at $i=0$, a first
violation occurs for $\Delta^{13} d(0)$.
The graphs $G_{7, 2}$ and $G_{8, 2}$ have $\Delta^{12} d(0) < 0$.
The symmetry groups of the graphs $G_{k, 2}$ with $k=5,..,8$
are larger than $10^{29}$.
While all the examples of violations $\Delta^j d(i) < 0$ mentioned so
far have $j \ge 2$, there are violations for $j=1$. $\Delta d(i) \ge 0$
is equivalent to
\begin{equation}
\frac{N(i)}{N(i+1)} \le \frac{(2n-1)(i+1)}{r(n-i)(2n-2i-1)}
\label{ineq2}
\end{equation}
where $v=2n$ and $r$ is the degree.
This implies $N(n-1)/N(n) \le n(2n-1)/r$. From
Eqs.(\ref{n1wan}, \ref{nwan}) it follows that the graph $G_{3, 6}$
with $110$ vertices fails to satisfy this inequality.
The $0$th order inequality $d(i) \ge 0$ gives
\begin{equation}
N(i) \ge \frac{v! r^i}{(v-2i)!2^ii!(v-1)^i}
\label{ineq1}
\end{equation}
where $r$ is the degree of the vertices. This inequality should be compared to
the ``Lower Matching Conjecture''\cite{fkm}
\begin{equation}
N(i) \ge \binom{n}{i}^2 (\frac{nr-i}{nr})^{nr-i}(\frac{ir}{n})^i.
\end{equation}
recently proven in [\onlinecite{csi}]. In fact Csikvari proves a stronger
bound with the right side of (27) divided by $\binom{n}{i}(i/n)^i(1-i/n)^{(n-i)}$.
Preliminary numerical study suggests this new inequality supports the
truth of (26).
Gurvits has proved the following slightly weaker lower bound,
see Eq.(51) of [\onlinecite{G}].
\begin{equation*}
N(i) \ge\frac{((r-i/n)/r)^{nr-i})(1-1/n)^{(1-1/n)(2n^2)(1-i/n)}}
{((i/(nr))^{i})n^{-2n(1-i/n)}((n(1-i/n))!)^2}
\end{equation*}
We do not know whether there are violations of the inequality
Eq.(\ref{ineq1}).
Let us now consider the case of a sequence of increasingly larger
finite rectangular lattices with b.c. periodic in the
$x$ and $y$ directions, as
are used in the limiting procedure to extract $\lambda_d(p)$ for
$d=2$. For this class of graphs, we have found no violation of
graph-positivity for grids of sizes $(N_x \times N_y)$, with $N_x$
even, such that
$4 \le N_x \le 430, N_y=4$
$6 \le N_x \le 800, N_y=6$
$8 \le N_x \le 100, N_y=8$
and for the grids of sizes $N_x \times N_y= 10 \times 10, 12 \times 10,
12 \times 12$.
However the graphs are all not positive for
%through the maximum number of vertices that we could
%check in a reasonably long personal-computer time. We have considered
%the periodical rectangular grids $(M, N)$
$430 < N_x \le 5000, N_y=4$.
\noindent
We have examined also the hexagonal lattices of size $N_x \times N_y$
in the brick-wall representation.
We have examined the following cases with $N_x \le N_y$, with $N_x$ even,
$4 \le N_x \le 800, N_y=4$
$6 \le N_x \le 270, N_y=6$
$8 \le N_x \le 90, N_y=8$
$10 \le N_x \le 14, N_y=10$
and $(N_x,N_y) = (12,12), (14,12), (14,14)$.
The only violation occurs in the case
$(N_x,N_y)=(4,4)$, which represents one of the two
non positive 3-regular RBB graphs with $16$ vertices.
For $N_x < N_y$, we have considered the cases
$N_x=4, 6 \le N_y \le 100$, with all the graphs non positive.
$N_x=6, 8 \le N_y \le 100$, with all the graphs $N_y \ge 26$ non positive.
The lattice $4 \times 6 $, a graph with $24$ vertices, is one of the $49$
cases of violations observed in the systematic survey of the 3-regular RBB
graphs with $24$ vertices.
Let us now consider what happens in the case of non-RBB graphs, as
mentioned at the end of Section II. In the case of disconnected
graphs, the matching generating polynomial is the product of the
matching generating polynomials of the connected components. Many
violations of the graph positivity property are observed. For instance,
the graph formed by $n$ hexagons, with $n \le 100$, violates
positivity for $n \ge 3$.
For non-regular bipartite biconnected graphs there are in general many
violations; for instance enumerating the bipartite biconnected graphs
with minimum vertex degree $2$ and maximum degree $3$, the frequency of
violations increases with $v$ for $v=10,...,18$.
Bipartite biconnected graphs with minimum degree $3$ and maximum
degree $4$ have a similar pattern as RBB graphs, see Table
\ref{tabdeg34}: the frequency of violations decreases with $v$ and, on
the average, the non-positive graphs have significanty larger
symmetries.
\begin{table}[ht]
\caption{For connected bipartite graphs with $v$ vertices of degree $3$ or $4$, we have listed
the number of graphs, the number of violations of the
graph positivity, the average order of the automorphism group of
graphs $ng$, the average order of this group $ngv$ for graphs
violating the positivity property.}
\begin{tabular}{|c|c|c|c|c|}
\hline
$v$ & number of graphs & violations & $ng$ & $ngv$\\
\hline
12& 240& 1 & 14.1 & 192.\\
14& 5183& 10& 4.3 & 143.\\
16& 190378& 134 & 2.1 & 41.6\\
18& 9816658& 6291 & 1.5 & 14.8\\
\hline
\end{tabular}
\label{tabdeg34}
\end{table}
Let us now consider some non-regular bipartite lattice graphs.
In the case of rectangular grids of size $N_x \times N_y$,
we found few violations, occurring in the case of narrow grids.
In the case of rectangular grids with b.c.
periodic only in the $y$ direction, we considered the cases
in table \ref{tabny};
\begin{table}[ht]
\caption{Sizes of the rectangular grids with b.c. periodic only in
the $y$ direction tested.
We have tested the positivity of the grids for all values of $N_x$
in the range indicated in the first row.}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
$N_x$& 2-5600 & 2-2500& 2-1500 & 2-1000 & 2-300 & 2-120 & 2-50 & 2-23 \\
$N_y$& 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 \\
\hline
\end{tabular}
\label{tabny}
\end{table}
The only positivity violations found occur for $N_x \ge 421, N_y=4$
and $N_x=3, N_y=18$.
In the case of rectangular grids with open boundary conditions
we have considered the cases listed in the table \ref{tabsqnp}.
\begin{table}[ht]
\caption{Tested rectangular grids $N_x\times N_y$ with open boundary
conditions. }
\begin{tabular}{|c|c|}
\hline
$N_x \le 5000, N_y=2$ & $N_x \le 500, N_y=11$\\
$N_x \le 1800, N_y=3$ & $N_x \le 500, N_y=12$\\
$N_x \le 3700, N_y=4$ & $N_x \le 180, N_y=13$\\
$N_x \le 3800, N_y=5$ & $N_x \le 100, N_y=14$\\
$N_x \le 2700, N_y=6$ & $N_x \le 70, N_y=15$\\
$N_x \le 2700, N_y=7$ & $N_x \le 45, N_y=16$\\
$N_x \le 1700, N_y=8$ & $N_x \le 50, N_x=17$\\
$N_x \le 1400, N_y=9$ & $N_x \le 35, N_y=18$\\
$N_x \le 700, N_y=10$ & $N_x \le 23, N_y=19$\\
\hline
\end{tabular}
\label{tabsqnp}
\end{table}
We have found positivity violations only for $N_y=3$.
Summarizing, in the case of rectangular grids with any boundary conditions,
we have found no positivity violations for $N_y > 4$, $y$ being the shortest
direction.
In the case of cubic grids of sizes $N_x \times N_y \times N_z$
with open b.c., we have tested the positivity
in the cases listed in the table \ref{tabcub}; there are no positivity
violations except in the case $N_x \ge 421, N_y=2, N_z=2$ which is isomorphic
to the rectangular grid $N_x \times 4$ periodic in the $y$-direction
considered in table \ref{tabny}.
\begin{table}[ht]
\caption{Sizes of the cubic grids tested.
We have tested the positivity of the grids for all values of $N_x$
in the range indicated in the first row.}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
$N_x$& 2-5600 & 3-3500& 4-2000 & 5-800 & 3-1600 & 4-500 & 5-150 & 4-85 & 5-13 \\
$N_y$& 2 & 3 & 4 & 5 & 3 & 4 & 5 & 4 & 5 \\
$N_z$& 2 & 2 & 2 & 2 & 3 & 3 & 3 & 4 & 4 \\
\hline
\end{tabular}
\label{tabcub}
\end{table}
As a final comment concerning
biconnected non-bipartite graphs, it appears that the majority of these
graphs do not have the graph-positivity property.
We have checked that this this is true for even $v$, $v \le 8$.
For odd $v$, $v \le 9$ the frequency of violations increases fast and
it is roughly $1/3$ for $v=9$.
This is in agreement with the fact that infinite non-bipartite lattices
have been found to be not graph-positive.
It would be interesting to investigate whether graphs which are not
bipartite due to a few defects have the tendency to be positive.
We have examined the positivity of a sequence of nanotubes,
$C_{40+20N}$ in Appendix B for $1 \le N \le 300$.
All these graphs are positive for $N > 7$.
These graphs are formed by a nanotube composed of hexagons, and
by two caps containing $6$ pentagons each, and some more hexagons.
Roughly speaking, the nanotube's hexagon lattice tube tends to make the
graph positive,
the pentagons negative, so if the nanotube is sufficiently long,
one can expect the graph to be positive.
However it does not seem to be generally true that a graph formed
by a subgraph which is positive and a small non-bipartite part
is positive. For instance consider a $(N_x, N_y)$ rectangular grid
with open boundary conditions, with $N_y=5$. We saw that these
graphs are positive (checked up to $N_y=3800$).
Let us create defects in the third and fourth vertical strip, by adding
$SW-NE$ diagonals to its squares. We have considered these graphs up
to $N_x=4000$: for $N_x \ge 10$, all these graphs violate positivity.
\section{Conclusions}
In a previous paper\cite{bfp} we noticed that the dimer entropy of
infinite bipartite lattices seem to satisfy a positivity property. We
have shown that this positivity property can be generalized to finite
graphs, as the positivity of the coefficients of the Newton expansion
for the "dimer entropy" of graphs.
We considered two natural classes of finite graphs related to infinite
bipartite lattices: the connected regular bipartite (RBB) graphs and finite
lattices with various boundary conditions.
In the first class, we have tested exhaustively a very large sample of
RBB graphs.
The results of our survey lead us to conjecture that for all degrees $r$
in $r-$regular graphs, the frequency of the positivity violations tends to zero
as $v \to \infty$. Finally, we have also observed that the graphs
showing positivity violations have an average order of the symmetry of
the automorphism group sizably larger than the average order for
graphs with the same number of vertices.
In the second class,
we have examined a large number of rectangular grids $N_x\times N_y$
with various boundary conditions.
We found no positivity violation for $min(N_x, N_y) > 4$.
In the three-dimensional case we could only verify the positivity for
relatively small cubic grids (with open b.c.). These results give
some support to the conjecture that for the infinite hypercubic
lattices in any dimension, with open b.c., all the coefficients of the
series for the dimer entropy are positive\cite{bfp}.
In the case of hexagonal lattices, in the brick-wall representation
$N_x \times N_y$, we found no violations for $N_x \ge N_y$, except
for $N_x=N_y=4$, while there are several violations for $N_x < N_y$.
This may be related to the fact that the entropy of the
hexagonal lattice depends on the b.c.\cite{elser}.
Also in this case these computations suggest that when taking the
limit $N \to \infty$ for the $N \times N$ cases, the coefficients of the
Newton expansion for the dimer entropy of the infinite hexagonal
lattice are all positive.
\section{Appendix A: Proof that $C_{2n}$ and $K_{v,v}$
are graph-positive}
A polygon $C_v$ with $v$ vertices has $N(i) =
\frac{v}{v-i}\binom{v-i}{i}$ [\onlinecite{godsil}].
%Here in this one subsection n is the number of vertices.
From (\ref{di}) one gets for $v$ even
\begin{equation}
d(i) = {\rm ln}(\frac{(v-i-1)!(v-1)^i}{(v-1)!})
\end{equation}
from which
\begin{equation}
\Delta d(i) = -{\rm ln}(1 - \frac{i}{v-1}) =
\sum_{j=1}^{\infty} \frac{i^j}{j(v-1)^j}
\end{equation}
which is positive; and thus
from $d(1) = 0$ one sees that $d(2), d(3), ...$ are positive.
\begin{equation}
\Delta^{(k+1)} d(i) = \sum_{j=1} \frac{\Delta^{k}(i^j)}{j(v-1)^j}
\end{equation}
Observing that $i^j = \sum_{h=0}^j S_{j, h} (i)_h$, with $S_{j, h}$ Stirling
numbers (of the second kind), and that $\Delta (i)_m = m(i)_{m-1}$,
from the positivity of the Stirling numbers
and of the falling factorials, it follows that
$\Delta^{k} d(i)$ is positive for $k \ge 1$, so that $C_v$ is graph-positive
for $v$ even.
A complete bipartite graph $K_{n,n}$ has $N(i) = \binom{n}{i}^2i!$.
\begin{equation}
d(i) = {\rm ln}(\frac{n!}{(n-i)!(2n-1)(2n-3)...(2n-2i+1)}(\frac{2n-1}{n})^i)
\end{equation}
One has
\begin{equation}
d(i+1) = d(i) + {\rm ln}(\frac{(n-i)(2n-1)}{(2n-2i-1)n}) =
d(i) + {\rm ln}(1 + \frac{i}{(2n-2i-1)n}) > d(i)
\end{equation}
for $i < n$; since $d(1) = 0$ it follows that $d(i) \ge 0$ for $i < n$.
One has
\begin{equation}
\Delta d(i) = {\rm ln}(\frac{(2n-1)(n-i)}{n(2n-2i-1)}) =
{\rm ln}(1 + \frac{i}{n(2n-2i-1)})
\end{equation}
so that $\Delta d(i) > 0$ for $i < n$.
From
\begin{equation}
\Delta d(i) = {\rm ln}(\frac{2n-1}{2n}) - {\rm ln}(1 - \frac{1}{2(n-i)}) =
{\rm ln}(\frac{2n-1}{2n}) + \sum_{j=1}\frac{1}{j2^j}\frac{1}{(n-i)^j}
\end{equation}
it follows that for $m \ge 1$
\begin{equation}
\Delta^{m+1} d(i) = \sum_{j=1}\frac{1}{j2^j}\Delta^m(\frac{1}{(n-i)^j})
\end{equation}
defined for $i \le n - m - 1$.
It is not difficult to show these are non-negative, observing that
\begin{equation*}
\Delta \prod_j\frac{1}{(n-i-n_j)}
\end{equation*}
where $0 \le n_j < k$, is the sum of terms of the form
\begin{equation*}
\prod_j\frac{1}{(n-i-n'_j)}
\end{equation*}
where $0 \le n'_j < k+1$. Therefore $K_{n,n}$ is graph-positive.
Friedland, Krop and Markstom\cite{FKM} have computed an approximation for
the average value of $N(i)$ over all $0-1$ $n\times n$ matrices with row
and column sums equal to $r$
\begin{equation}
N^{Av}(i) = \frac{\binom{n}{i}^2 r^{2i} i!(r n - i)!}{(r n)!}
\end{equation}
One can show by the techniques of this section that the sequence of
$N^{Av}(i)$ leads to $d(i)$ satisfying graph positivity.
This is very consistent with our conjecture that as $n \to \infty$
the frequency of violations of graph positivity goes to zero.
\section{Appendix B: A sequence of nanotubes}
A fullerene can be drawn on a sphere; it
has $12$ pentagonal faces, while the other faces are hexagons.
A nanotube $C_{40+20 N}$ can be formed by cutting a $C_{40}$
fullerene into a North cap and a South
cap, joined by a tube formed by hexagons, belonging to an hexagon lattice,
formed by $N$ hexagonal strips with $20$ nodes
characterized by a "chiral vector" $(m,n)$ which describes the
periodicity conditions on the tube. In the case we have considered
$m=n=5$.
\begin{figure}[tbp]
\begin{center}
\leavevmode
\includegraphics[width=5.5 in]{grafico_nano.pdf}
\caption{ \label{figura2} Nanotube with $N=1$; if the letter $a$
is present in a node index, add $20$ to the node index.}
\end{center}
\end{figure}
In the algorithm\cite{bpalg} for computing the matching generating polynomial,
the ordering of the edges is important for performance.
\begin{table}[ht]
\caption{North cap}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
0-2& 2-8& 6-8& 3-6& 0-3& 0-1& 3-4& 6-7\\
8-9& 2-5& 4-18& 17-18& 1-17& 1-14& 16-17& 18-19\\
4-21& 5-13& 12-13& 13-14& 5-10& 20-21& 19-20& 21-22\\
7-22& 7-25& 22-23& 23-24& 24-25& 25-26& 9-26& 9-29\\
26-27& 10-29& 28-29& 27-28& 10-11& 11-12& 14-15& 15-16\\
\hline
\end{tabular}
\label{tab6}
\end{table}
In Tables \ref{tab6}, \ref{tab7}, \ref{tab8} the edges must be read in
reading order, from
left to right, from up to down. The edges are ordered in such a way
that the maximum number of 'active nodes'\cite{bpalg} is $11$.
\begin{table}[ht]
\caption{Strips: the first index in an edge $a-b$ stands for
$a + 20 i$ or for $a + 20(i+1)$ if it is followed by an $A$;
the second index $b$ stands for $a + 20(i+1)$;
$20$ is the number of nodes added by a strip;
$i=0,...,N-1$ where $N$ is the number of strips.
}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
11-14& 12-17&15-18&17A-18&16A-17\\
19-22&16-21&21A-22&20A-21&18A-19\\
19A-20&22A-23&20-25&23-26&25A-26\\
24A-25&23A-24&26A-27&24-29&27-10\\
10A-29&28A-29&27A-28&28-13&13A-14\\
10A-11&11A-12&12A-13&14A-15&15A-16\\
\hline
\end{tabular}
\label{tab7}
\end{table}
\begin{table}[ht]
\caption{South cap; to the indices of the edges one must add $20 N$}
\begin{tabular}{|c|c|c|c|c|}
\hline
11-37& 28-35& 35-37& 33-35& 34-37\\
27-36& 24-36& 36-38& 33-38& 38-39\\
23-39& 20-39& 32-33& 19-32& 31-32\\
16-31& 31-34& 30-34& 12-30& 15-30\\
\hline
\end{tabular}
\label{tab8}
\end{table}
We considered $1 \le N \le 300$; graph positivity holds for $N > 7$.
\clearpage
\begin{thebibliography}{}
\bibitem{hamm}J. M. Hammersley,''Existence theorems and Monte Carlo
methods for the monomer-dimer problem'' in {\it ``Research papers in
statistics: Festschrift for J. Neyman''}, edited by F.N. David.
(Wiley, London 1966), pag 125.
\bibitem{FF} P. Federbush and S. Friedland, ``An Asymptotic Expansion
and Recursive Inequalities for the Monomer-Dimer Problem'',
\emph{J. Stat. Phys.} {\bf 143}, 306 (2011).
\bibitem{bpyl} P. Butera and M. Pernici, ``Yang-Lee edge singularities from extended activity expansions of the dimer density
for bipartite lattices of dimensionality $2 \le d \le 7$'',
{\it Phys. Rev. E} {\bf 86}, 011104 (2012).
\bibitem{bfp} P. Butera, P. Federbush and M. Pernici, `` Higher-order
expansions for the entropy of a dimer or a monomer-dimer system on
$d$-dimensional lattices'', \emph{ Phys. Rev. E} {\bf 87}, 062113
(2013).
\bibitem{nauty} B.D. McKay, \emph{ Congr. Numer.} {\bf 30}, 4587 (1981);
10th Manitoba Conference on Numerical Mathematics and Computing
(Winnipeg, 1980) [http://cs.anu.edu.au/bdm/nauty/PGI].
\bibitem{Sage} William A. Stein et al., {\it Sage Mathematics
Software} (Version 5.7), to be freely downloaded at the
[http://www.sagemath.org].
\bibitem{Wanless} I.M. Wanless, ``The Holens-Dokovic Conjecture on
permanents fails!''{\it Linear Algebra and Appl.} {\bf 286}, 273 (1999).
\bibitem{bpalg} P. Butera and M. Pernici,
``Sums of permanental minors using Grassmann algebra'',
http://arxiv.org/abs/1406.5337.
\bibitem{PR} pull request for inclusion in SymPy SymPy Development
Team (2014). SymPy: Python library for symbolic mathematics
URL $http://www.sympy.org$.
\bibitem{fkm} S. Friedland, E. Krop, P.H. Lundow and K. Markstrom,
``On the Validations of the Asymptotic Matching Conjectures'',
\emph{J. Stat. Phys.} {\bf 133}, 513 (2008).
\bibitem{csi} P. Csikvari, ``Lower Matching Conjecture, and a New Proof of Schrijver's and Gurvits's Theorems'', arXiv:1406.0766 [math.co]
\bibitem{G} L. Gurvits, ``Unleashing the power of Schrijver's permanental
inequality with the help of the Bethe Approximation'',
''Proc. Electron. Colloq. Comput. Complexity, 2011'' and arXiv:1106.2844v11.
\bibitem{godsil} C.D. Godsil, {\it ``Algebraic Combinatorics''},
Chapman and Hall London, 1993.
\bibitem{elser} V. Elser, {\it J. Phys. A: Math. Gen.} {\bf 17}, 1509 (1984).
\bibitem{Enting} I. G. Enting, ``Inclusion exclusion relations for series
expansions of boundary effects using the finite lattice method''
{\it J. Stat. Mechanics: Theory and Experiment}
P12007 (2005).
\bibitem{FKM} S. Friedland, E. Krop and K. Markstrom, ``On the Number of
Matchings in Regular Graphs'', {\it Electron. J. Combin.} {\bf 15}, R110 (2008).
\end{thebibliography}
\end{document}
---------------1408031005927
Content-Type: application/pdf; name="grafico_nano.pdf"
Content-Transfer-Encoding: base64
Content-Disposition: inline; filename="grafico_nano.pdf"
JVBERi0xLjIKJcfsj6IKNiAwIG9iago8PC9MZW5ndGggNyAwIFIvRmlsdGVyIC9GbGF0ZURl
Y29kZT4+CnN0cmVhbQp4nI1dSY4lu26d1ypqBWV10W3Bs+9YggeGjYzBhwd/+w6R57DRzSwY
D4WXh6LYqBel0P3n7/Kn/i7zP/z/P59f//z1b/8xfv/X//5qf8bvf/2qv//9/fc/77///tXH
cf1pv8co55/z9+O49j/7769ffavH+8cY23jzRjzZJi5d+A/wj6tGfC+UoIESDC8aVosEz/R2
xfT7g9K3/XzROGChILN324O12xgRQY7xAkPSvVAe5u8KlolsomO8erfrfL16gPa9q+SjTVPH
PobKPY7Xw702tV/RVsF77q+IkFdEOj4lm/HfC+VxXGmZSlDbXINjt+ZFTRSNVneW90LpvdRZ
Km3b1CLi/dJybaeUWjsr8LFJfsOQZ/zAkHcvlMclDJQBNQC365qpTdsDUBfZpYivbSt/UPaJ
8sou9YwcvUiFvta1BcNa8tMbygOGdnDfCZttJjtbl215XDd8AWroGeSWelHfIuVx+eCI5fT1
qx5H6nmGMRbUU6Wxp94L5QlYe1A9S+hf9bhaREcaSRyrdJNl/XylZHtfb6q2u9IvaSWGhW2m
14nOC6idju6EZ94xqyTkBe5qLbjbgGaRbCjaMbG4hPTpSWt9etLPQ0eHphXcz30X35s2iICP
WWHgD/jc1DryXwe9SZTHcly1hfxXhYXgvnoFVnscq73OD3sh/f6grBa144g1owgj1ttTpjVe
M8dVpLz2jdIXSjtLcxwkrBJZA+RnClGe4SPUF/roW7pdrVV0YXTTXveWCmYK4mE9Cn+//a/K
gGWSHEt/rdcU0S/0v3uhPI6pq8qgAvm97nMaMqSynReYowNk0Zb7g5KtnaNq2ST94qjbSkzt
iXfsWt8+ZkfKY/gqR8h/Nc4BqusDq2/MC7Rp73FP+iFrjHJgBiU+i6wwiswOtWJ+I27aenqX
RvoOcwewCDZ8LxSX7xKAFwof9hyYU0fTEeI86MFCMXxxlST9yW0cXTzCDD/m6kKR8655Vbau
ySKF+d26vv9k61zlyB/uG7GU9Z3wm7pLEXnJELPk9lpjWfdNjA5YpRk/MeTdJvHDHtq/iyhP
J6Y/+xHsuRN+iGgK8ho+GlY6Ays34ENXanv5PXq1lUbAjyFKmjXQG9YUh3TigFWucxNjnSCy
aMW94Gwl13c6BXC12c64EmzXHtaJiu6EfVVpNhimjcrtPqhsx1OvcyvysnL8/MUutwMeEB17
Wuu675AEfC+UJ5WOrcjeZtp8/fQipo6Zqe8bvCDGeu5eKLaCm80qrtkChoa8IvzUsNiDfl1k
MWWpRJQt41yQBWy6ZJQzW+6FMiXKOBashQaTALxqWOyR3lFljETanC+K+4W/oQWjv0klptbW
RyrD1lrE90Ix+Za/nN9IT5bojLUXKfs2uA8K+N2TtD+BV4YXQ5d63kZEWF0Zr+1mrlSK90J5
HJsHkGAlcORWRkuNH+kDM/9iwc058R2IdMVmeOyY4fpE5/AZ40Xo2e8+7J2dC3qAoYfzItJM
JvMZTlJXCzpnNV1xMv12Cve9xFgl9nGesmpW7UPXUgfWlIZNvnJT2v1Byfrm2LPN9nzoXgiI
u8LzkjZ6tJKQzciJMnOfzb2bOfYzoimbuYmi5MWKgzu2d/l1astA+iWhjHd9gtUtMWVfOl6Z
5quViO+F8pgGlwBsGsBfitYyNRg+dESUkpNyXyjE8PhCu5D8M1VHGcobpWpfgcfvMv/0Epoe
ZMrkGDrqoe7ebUWJOXK68x9F9ak0+vvqD+V7e+6rIzf4F3sDNm5DZln0TdvRrO+t7lb3W2Oc
SFvGtucWue3YH6DFbWfhqJkoD9og0yHdcitaZEc76h5ag6Z4e9zaGdrO1nNb2UZujY61tZpe
w7ajSpTHJdALajAMC+iXYWr4m0XqUaaYBT33sOlxyF+T9FxW4NR27SWnvUDr13uFW6r9YhtY
eTD/aGjFNcnLmK1SLWGbZVtij/gu1fsDy8hkbWuP2zb2uNmqmW75+wZ54F4tdxzKF6h16281
2eZeym5CVlMnNBFfRUaWbdf9L9uG7lWM+3YK65r45O5G1FKe7h4MCp0LjRfYo82JYjsX6Hfp
jqM1E+vq7Ry6EwPy/n0URJkwru67IdtjeNkco3hZYccislUW0eTc2vecD/9GXMtkMgJ/1KFx
MWLhRiu5F2y5V4sKQxpPFojF5uyf7KGOXLtt0/n+3RzL2GEYkfe2N+3JBZHefcZHNPUh6oi0
gpey7g9K1jZjUlr7KuFxPKDtOCf3qX2AiG0nYsTb3M5j1rMjyEVex0nyakXn2rqdTe0mB7DJ
P4v6SXkSIWs7Z/eMidA+sFvqjBkR66oae6eXPe2ViFVWrzGm16tH9FapqwqM5+uOq/H8Crjb
nsux7HEksuo26Y7JsfZCeqCosb2D23WrNOJ7oTyLdXMKLYNirxfPZhQ3rLihDyOnY0bBM2Xm
l4nQLerZIpM/rgVnCqs9irHTkKhjs1iWthdyIP4UsMRGwB+wjfiZYrG0d5vI8yloXDF9Yn7D
OjK0glEoYUP0eEg8IWifYxate7vF5t7MGUdC0LE8EmVy9Gb1t0kn87KwNOPriMZAivk4JA5i
+Ca/rtDIvVhpmLnrHhFsih5pFFtHgIIzLsPcjSJuXbkjIG4owarzR+22qk2UKVFHfnJQg0sA
XjR8WMQzvCpnzJZ+O+VUfUAaf2oStHLtTWJOkvo4stNM5VZJ94KjnskrW0mU1GPY/GiHrLuo
qZtNN89A3cdeso9vIYQ66LrS/C5VI+oRK6oFrQGSa9HYgu4SgDTfidU2bbjCOfCnxfBG5Whe
l2sWJ/+gqZ0HI/KCTovqBTxTZQnQLrZnYvYWHZXaZaOWJAQ8pTm3IB9vIG2x5eBpgoygr/Ua
xZDlV0iVscfwvVBsPJT8XwFdcexql42Gmm6eEpvt4B8WoUwUt9B9V/tdAtI5Xn9YMNTD06LR
C4XYbdzLizCayvpc0BfvfoSykJEnllaiPLyPYi3hXeiXmCOnO79br/IuO8k5mqPb81+IdpA/
2Wso1pQii21Fz2x9YrVAxDsGskJpl54bEtmJpK6DSrGdQ6J4nJgckI78QFn2Ygfju7LasNT7
g+KYlp9avpAOZJbreqfYSkxXF9GTSAnyTQJwlv9hCucFCSnDOh3nM8UwTmj77OmMHWg0G/iL
56WurR4jjhr3Qnl4fuulU2WtEOyL6YH/wCyl0rgfreN0dDs314bkX+01LPm5ylFklm3LONE2
WRVZTyMmxztVpTG2bbNXk/teMNClnOhDGGEMm2QZH4j0dkU7JRItkhcKMft0KzKTUFuRu0NT
qO5XgHecALa3xb2oYA+hh6jGfTsF54mGT97+eLeXLq1qf9ow3hjeS+D+kIWzy1dblxm/7VhN
Gpb2+a7mqtiOGm1dFmFtxzl1G1XTba7KlMkhfxhHG11LAyechtEujB+txjSuWO1j7hPe6E2Y
NkqRsgDaWXLKPQbLTmeaUQfqVWeaUQqkOZ43TnSm09TWdB7RvBHzBgu4cVvC0qmbeNOaMH47
N8yUYJ15A+spgeld95GfFsjZyLuA1xtBQBbJzBTRJy2hs2bmpTDLLX+z/TcdB5wTeENsos3+
FTU5nrLmuMBUSLacgla50YaiPVjHijZs179QiDv7HUaTxqiEjAHOLWhDyWG8aNewsSpSHsMu
XTwk2uVIejqqHhNT9y4Jb7EwchPxu0uUepho8u5nsHM/L/dypl7qlcV4dKRi+r1wPI4xIphE
uW3R9BKoIfByZCPvjnoK+KGltFrlcFQipp3Bq1l6OmsKu2+wUog3nPW/5S1tfcP5ftPLpW1g
f2H4RH3IrD0ulonjydu1Z15aojoCumRirG3AbZZAlmPVvNn5TKY8AVNDtC5a85h2+gF0MAYI
Xh9DEuVx2RxDUjlJ7Wv6oZYpMsuOMuvg4nllxm8dzqEKeHLrSG66D90DmW6N9ImuifJYfaf0
x9GFmKLI2rBjbMfcETkCr+yATe/F+8uZ8rilZnndrYz17+PTo7muhccyP9wLNmTcQ9swZ4BL
e4tyv+vioqlYexFvnKkzRe4RB+nvAjaWLWVzbiA26cJtMUORBDQ1yWTbhq2JgWH5uwrWmaft
XAVreZq8OG/OdeP7B/2smPf0jKI2LROuz6uO0t+lPo673f1PlCDd/IQlxOSv2F2Rn5arpasf
1c6iE+UJntJ+euqtZbtiG9uwW2uHluludwAz5XE8cn/ZOTceWPsYxsrJ+IG50oI8tedecLQW
91XfwVr7z5GsOM+g85z+Et0Jz0i9zrGWl1jnbOGlvil11T15tL7M5lOaIErxMWw+ntIB3mEK
956Rf8f+em6PozRH75Y6+n/pnGu1dUlM7dvUx7CtcSFr77xtlinTLt2dk8MkIOZh/MluR8jN
9Rcwrb0XyhM8/eJdUdQu4ueWdgU/cZsGdXEn/DhiZAN5d48MXbFuDKM1GP/GiKFa4q0pUx63
3CScYW/xfGNBCy0cd1JDrWRK4KD8GVl3++ZtoYBa6p2GGcVSbo/rBPxQssWA5PKF1Raxldym
s7Tn1nVwkD5j7fRzwwpF63CTu8zWNnDm/G2qfuuUKcRWppC+53OAgMHP6B356atYulpunlEa
2xSwW9/dsyIRZqyi7eajrWTvheLRGnLgvqCtwwpfMfLDVTxTOz0h9pu9ieL6OusR9jhWDyjB
0ovNq4sF2v7pz/1BMaz30it2dLSY2PRpf3F75KqA4XuhuHyXALxo+LCHJV6H7Sd0ZRAxkUvT
/tjYFmsz5LEs09VKWeo/UXDXkmXTZPntllka+azUIYW7XUa9iG/mvVq0YrXSsOZGGyNCfUWP
wklXfRvCbzuVqoU3nPXUKmDZBQl3QP7dXqI8np9f+jH92DI+07nZW8c8FYM9VzolM/7bOfb+
g0aZp8w/GffcH/1Gw/C9UB6eddFjIt6XJDe1MZ3+EdM/8ts+P1OCheYx7LcSQjr9/bBATKul
+7eOmWLYbJR4XJ1BQ5zIyd9fPK/ystCzsFhaiYJzI2j64gmdl3ZINV7aTUkHRnk9OzN8k58t
i/zZUiLNa7UE3NM5XPTjlD/PTS+uSpQAd2zmzT/+uZ/CYn/aot0h7gqeBy/UzhTejxJw8WOD
l+0qmNtVpUM15zLfYdJRv1Pxdm1aLn/yhq00IbLdmSA3FfeQjot7ZisgrVVmN1BEOZx6g7UG
aZOVQLIpmfCYTjpAGFl5WcvhY1JRSyiOmef9n109E2DeiUq9xIWriJGAO412yesSZ1Tbu/e6
rHmMIoctp90TbG5jSnsMwneKwfeQ/RLTCMmMNkXmnRvoRHjMQLNXhVlBKrQLn+aNxGfmMFDP
wtufKwW3vN5xiPEoaYsBSxAT/AEzbgr+szESh/TBU59MeQI+Y/5d7VVriGDrOGMav5peNN8a
BQyeCWq8RSZNyiTLdIrUx/BhXwcaf5bGUjhkQVP1s83HMbxuhyzzTf79QWmHLFKCfYeV+kyV
lZXXgiqCPsFXTL8Xjscx6wUST0bzD2mpjsnPswzyN4v8Jgr29dF+lcd2QUyLg39W663uhRHr
gOcm6f2bcS6J7Tp6BwDh878ZixS+AztuTfOYXcCPIeyHNXrsEdo9IlhmvGLbcXmrMJ2zjHRF
rtY+hl2anp9VixTu7+qtblyPZwxkvLqWroxnytq+HmgfI+k950qXZXYnbDcgoWfm7rG8U2rg
ZsmqLEQ3dQeg6HZexmyVN9uIWChyWjQX2GyKHulJ45iy2D4V0aau+zy0C5xBVsQXCvuYlCjz
lLFkH7ueyFoZ4NTQrCM/+zsxb3aSn72B8qqdACXKs9g8JWpMtLK3EauHQ2Nvbj/bHe2R65Ym
fZ6raszV9G0zemb2bXrWV9mbt9p+Sn0cs8WoLIs0R/y4LSw75uY5o3Kb5ef3nnCcIqalyS+N
lWm046gWXVNst241onBYrBtY2+Uly8i3s1Ga4ylL25mmmmTkBFrlrnbwhPfSMyym3xZl9xzA
0KYt5LCIvcZvD4uiA/uXo0XPRI7BeMKM0x8WhdeSPDwWnezTWPThUf2A505Ga/E77odoY5wE
ku2rS1nJOFbufnK5lrDlXu02DGmdcRVgv+Ec/PyymL2XO97tsNO+d1LUUy2U5Du6jYw1TsNT
L8MYqcnP8yTKJ74XyuMYexZKdKwWcQQn5rzy5q9xXnnz75H/dorMsIYwq9UTcRaTp5FRx3pO
4fzAMhqR28fqTHlMPjmiNV/6VkkrfM1CUNU1X13GVdzIKPayAm8xeG6OH5of4yTyv9trWXVd
TVdJhhHBq/qASL1wIv3+MWuyXtjVGua5c5EKDPkvlYfTccO492v8tn9fKVnjzCF/vBLw7gux
novPLbFpa0XjEW7dfrqvN28SGaVpGMKt03tJ0GWl/0P643jTe0mQttssmygP7bGbRcjNuwjk
NuthbfaGZ/zwCpYmz/SOyFW5k3gMXXxPZT6AUK+C+atjn6ErK30AADuFO2FZd8T9Sp/lf+r4
r3/rWE0urhqpYcFmj+QlktUB9kFYRwGbxQO7E52VuuxNVPOQ0CqsvRf8riKkdcH6sZkOQVfY
e4W0h4grUUqhN7r6MHyTn6tk8mcLz5SXKy9is8rtl9k/1KqMM5K64/Ya8TE4bspcUA+cLtT5
vFDdL/a1d3WKvD427HZHO1Mmv3xViPxfho8Sx5ZDvkGwNNNMvGGkADctFVsO+84l4gd2e94G
Pc+HVokA1/1kPsW0gqPNYW9WrZS3ezb1ib1OupSVQSujeonPdLmVAI0yIvWf01VjphCrB5R/
8Cy0aE9xDG49Wyb3Yq1j5MYJZMSPIbc9+vqW5n4035Mr4n72NVfqkzt+x2g7Ac+8l7XhKd7/
Piy+wb+zvKyd++e3OFpMvY3CeIVhrIvfJjBiPOBtWqfGI4h37XemnzhxY0yM+HHZ6hM1IycR
5f7Njsf1mt3AduM6Ux6T4GWjGtayooS6nS/3u3abeeXvjbbpR9XvRoUxj3f5ILIGwp3EG63f
9cTCJOx6XuFYzyucX/GwaGqmPCZhyI1qyieK1khLkr4wsPYhpv1vM5fRcCtcAayUuusJzWat
WqYgls4xhunWRySgS/D+fZrqyRTirWC0E8kb3k9527qsWxwjN9u+ci82Otbcw2JhmfI4Ntvd
S6n1V3pFLBZo1/LVmFijJsM2SicK21OTV1TqNiNe/HsP+Yiy1MUCvjqIOmeqt8mKuLpjrM3R
Zqq1Em1RjrXFuX5iWAd+tfxO+DHp8Au6PS9x+3/Y8phut52YcbtM8f7h5QMKa3lBAvvErFHv
IWYf+kMKLTdT2EPq0nastqRtmna0XLQf6SPfpcU+AsuIWFIqF68TsgU7BjfeZwT3aqNh5D64
PssU7yG0O/qI9qpnUNKo9WxB2jr+1Cas5zJ3hI8Dyjr9lIRpOLchZBFMVh5CiWIH+wgnUmoU
G0hWIK2BlijAMQpalsnUhsQXL++VgIZ35pa6CNMSICvKRsUAmD1fbFp67nSzbfJAiZBlo+2S
R0LMS/VaYypKGgOPqQxYE+NBkbROmBVTnJGFKCLot7YUh8rqo1MmaN7FSoMqyvqHQjPPXPri
twWYVx//2sAoxDt3SNqRql70/tLb/oFbEfaCI3MC+9lBojz6/YFrmt8fBCSSuVNStEperMB+
uGH2dh87Zuuhe0AgSuuYB3ecUDH/jjOqPpK8V9n2J+i7F4rFoFku/Tgif0wKvNj7QpLFz+Xe
eMDg5q40Ycu9Wm4Y0rDnBoKV0cu5A9Lxuts7FiuF2F4Kno921o4bGYyh9CWm4twa0XH+OfK6
tqZXHmrfdG8DZNx6V6EfOOfT3LirwYiI6a66F+7DTjgTBbEy0fXFr5OM29OMjy9cUAq/Hymy
oXWs3PyaJCDLuVpMTEmITgHBvujdF7+oqe3iiLtS2qzi2tjeZ/UHNPdDjREIQZ19UDj5ciPS
Ovqyocf+RqRNc/GFXtHtSC1zXkmt4VvBoA9rjNO+/1sohu1MUXty97dYFJt25Te8awwwaNjl
1mRtdr6pWL1uu/ZkvlbJ/N1PJT/kZYp8xeBlr6ea0Cb4/CnVzkC9fERW91hXwPZNkKVb7sIT
1bp/Wu4YudkSgFs8Bw6UZ/FU4l4yRuuNsjY0fsS7RG3IvBfwpffRxojIbsxlyuP5+UIP09l/
iNlTyc/xg/YYhrXGj/Td4uML5cOCTdY/9HfT+Lf5t/WasdywpL9EG05oA34878GvZqFpxfSF
uQrL8YrdKDN82J2H7dpd24a7e/hqanO7pcWPVG+4O1L8laBEkdsl+885/PaJlSM10Lu9RF/J
bW81rhTLn+0HKqFVAdlYET2deA+38nSu7SHmKefmHp3rW4p5cl5mhJNY42fkRqSOaf6VQqI8
AaN1Mz+/xxRbHPUWeYfFOFe9YqxFJG+nmI+KXZb2cdOkp/UBN42Bkh/YSgH8HhnOFLsfEMox
WuT91GKewBaX1VNti8Liu2SLY/pIYho3iWRTH/qtRTK3tqd6Tenez7VE74Qp2yKuY8Y0DJGz
DOdktBU2Opac2nbkb9p3J/ws3kkb1/dzCu+MAfM9/U3fQq3DvpDVF3qKrZ1Jsa8kgZveHJI1
pL2Qgy8hA9aX9Vw+8MYvxzLlcQm0kBoMQz+/CSY2Cn+zCHN8opgF8AjIvisFd+EXs5BvOJaP
rRFSCepNdNx8ADpt9aZ3zU//blXvA+A7U0Vn4ejq2Cx3WfjK9OS5JL5LPXnuSP5yBnSk72vt
vkbAj0k+zrHY+MXfWPA2RswaO/RlMdbQze/PPMepv0dQeSZJzDo+R261eHmO+F4oj2swCcCm
ge9IYaVOCvbSrjD6W04J6zun9j6RvJbqiK8bjYT4eup+hveVkFrtm+RMeRzzvSvNz/eoxA5H
aqPzbvaW07No9neI6RGQvt+Et0pNsl4jlpef7P4x3oG6E7Y7wYsklMa1vEUFuV52btOXvZ8a
3uq6duXna1XA9mqW3uDlO1PML5aMIqukIG2lyK1ks2WUHl7oErz/lPoYZvmqLJaQo8dea618
Q1jl4B0t2JAtRkleeE2M79UC+9vnifIs/rE9dL4srojvhKPkB99mNnym1jLUB7TKkVrlSO1O
c/LvLHWxwV8/xzu4lk5s7UVrFLKJqBfcw+4u8KXczjf5gc0elFi396b15dzury43t8ZfziWF
79XSA75ny1Ll67nfp/v7uf3k6iRTgoYr2HMlWd4ClXN5MXrxxVpLxHyX1+2Ofn7Zi+zDvioh
5neTs28Mfxcw4Adow0tZzV4T5hvxQJC5pRfjh78FGfTfC872fdl77cNefAfm22B435126C8Y
jYuyI8Y3noI85ypp2Mvz4DZLIOtby/S7S3k9drPvLkvwetO1xvA3z0rSvsn0FstFv/r0ktnO
ErTj1WOrt/kB5w+pj2N/ay9RTDq/YFVbriTLf6ulJLvPVB/M69/bJcoTPKXl0c8v/kIYP3SR
URgRb+wQqn2GlCm+h7C4ShnxrFglL2jNS+l91xmJ/RemxBcuE8XbbrHfjXt74r+S2mcxqel5
VN3tatt6cH+kjx7uhfJ85KDEi8slTbfLwMgfLwf/GW6lX4Ze8kGuP2qDdD4cwfz+kIQ4n83x
Ujbz9AVlV6PpruYHtYtZJu9ecjyfEqHR3nBCOt4hqPHb/dXJ1RoWXvZCVsGpkPVFPrMAqSb1
B4uClkR5fio1L2VNr7tHSwN+Ppvdkn5/5lCbw9c3W26Gq8dr+tIz2TyS689n0UjBoTKQdmwM
lmlew6ki74Sfj0K+l/zPp3x9RtEehNhS5+bT34ah7bJPmDPl+bDXGk9oclY1rjfh50PPR7o2
WfuZvHlUpz/mUmMJh3StiODsw9/u9Bc2l5EK6b21kwXFv5diuhfKsxSrFULoIQ/vp9di6z83
UhQ9iwk0sNtDtJrKnzPQnIZgki/WMuVJLt2L9GeZGr5sIrAfmED6UaJtQItl90J5Pny5k4Rn
lQ7d9iWkplr98ofyDEObf1mZKc9ib6og51mk/KBlVP7YpfxoqaGPNpgpT9L2tTTHdVVgQ8Rj
bwBzCJBWk0vEcps190J59EmM0UfspU57/uqd/8Sp5o9oBkVrKtucus7NH61y0yUpW0bGnh46
XxoKvpEQ+sVa6iy+6DgKauv759IhOzF646UFxfrLb4Z23jYC7px5Vgqx3/MB5rUPYvyGs+HC
70xXCnHZIz9PMQzzSxXFbwNP9gEbsrucwHYTU/EZ15z9tLd4V4rhmlbD/cC+wfDYY/n1o/J7
yZVCzN8fMjxSqt0zVLyF21+ZYniL9m31TPbzlykMY2Vyf1AMt9QirFEb3lL9995yCSomaldq
Cr3Z5RvgFlPrNZb6IMXwnltDxVkSceFXQMT2zuJKMZwXzr2UEoYAvvdr2H7hZKUYLnF5fx4l
2t/OfkX721m2XB9GIT6OvGE4cCPGsN1bVbwfWd5+RGl808lwTb27bWcJqdtIfbttPW1+BIfU
mjZLbZypn7exleTJqKmnt24TgVG2VPtNn/VwCe1Mtd/aFkuitaXujWID/JV6N79AI2qpb7dy
5Zou4c5ipASOPfX1VnpqCvW6Um+v157qvl65vOtVUt3Xc0+9u86PpUNqST25HscythvFcE99
ux4l1f+86J/s3Ueq4br7YjZRAkeJ+bcjtYC6jdS761ajdWMt7zpGGt39JhSw3irydN7vMYxb
MvcHhVh/GdXQlsby2mrqzbWeMTXcFE6UwLGlvl1rS2N75a96G95S+6plLe/rSoP5tYfefLU0
kJ85tHHuaeA996CH75v4oiMsQfjpKvA449puhDdgIiVw8AemiPngHXDnD1wSM5RGbM//Zkrg
4FoYuKGMDO/Ru8afDyeu2f5Wo3WVT+kT79G2yofjgAsf+yL2x6QSJXAwCErMEBexHQPo7uPi
D5gQ+xOriRI4+h7zl7Q27/7UD3CMBr69y4++IiVw8KEx4OPYUvqB2jPMHy0G5k833gslcPAn
Toj5QTlxjfb7zzEC7zmEuMX6830kcY2S+aNchrfUsvv4CFCOXHtvQz2S9x1X2gzzI3Xillr2
u8kaS+32pf7aGfM3PjZJbD9viQDqFe2vhx+hRkrg2HjhvMx1k4wf/3j/+z/5HkcdZW5kc3Ry
ZWFtCmVuZG9iago3IDAgb2JqCjgyOTYKZW5kb2JqCjUgMCBvYmoKPDwvVHlwZS9QYWdlL01l
ZGlhQm94IFswIDAgNjEyIDc5Ml0KL1JvdGF0ZSAwL1BhcmVudCAzIDAgUgovUmVzb3VyY2Vz
PDwvUHJvY1NldFsvUERGXQovRXh0R1N0YXRlIDggMCBSCj4+Ci9Db250ZW50cyA2IDAgUgo+
PgplbmRvYmoKMyAwIG9iago8PCAvVHlwZSAvUGFnZXMgL0tpZHMgWwo1IDAgUgpdIC9Db3Vu
dCAxCj4+CmVuZG9iagoxIDAgb2JqCjw8L1R5cGUgL0NhdGFsb2cgL1BhZ2VzIDMgMCBSCj4+
CmVuZG9iago0IDAgb2JqCjw8L1R5cGUvRXh0R1N0YXRlL05hbWUvUjQvVFIvSWRlbnRpdHk+
PgplbmRvYmoKOCAwIG9iago8PC9SNAo0IDAgUj4+CmVuZG9iagoyIDAgb2JqCjw8L1Byb2R1
Y2VyKEdOVSBHaG9zdHNjcmlwdCA3LjA3KT4+ZW5kb2JqCnhyZWYKMCA5CjAwMDAwMDAwMDAg
NjU1MzUgZiAKMDAwMDAwODYwMCAwMDAwMCBuIAowMDAwMDA4NzMyIDAwMDAwIG4gCjAwMDAw
MDg1NDEgMDAwMDAgbiAKMDAwMDAwODY0OCAwMDAwMCBuIAowMDAwMDA4NDAxIDAwMDAwIG4g
CjAwMDAwMDAwMTUgMDAwMDAgbiAKMDAwMDAwODM4MSAwMDAwMCBuIAowMDAwMDA4NzAzIDAw
MDAwIG4gCnRyYWlsZXIKPDwgL1NpemUgOSAvUm9vdCAxIDAgUiAvSW5mbyAyIDAgUgo+Pgpz
dGFydHhyZWYKODc4MgolJUVPRg==
---------------1408031005927--