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--