Content-Type: multipart/mixed; boundary="-------------1411020928570" This is a multi-part message in MIME format. ---------------1411020928570 Content-Type: text/plain; name="14-74.comments" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="14-74.comments" 16 pages ---------------1411020928570 Content-Type: text/plain; name="14-74.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="14-74.keywords" virial, dimer, lattice, graph, entropy ---------------1411020928570 Content-Type: application/x-tex; name="milano3.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="milano3.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{Positivity of the virial coefficients in lattice dimer models, 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} Using a simple relation between the virial expansion coefficients of the pressure and the entropy expansion coefficients in the case of the monomer-dimer model on infinite regular lattices, we have shown that, on hypercubic lattices of any dimension, the virial coefficients are positive through the 20th order. We have also observed that all virial coefficients so far known for this system are positive also on various infinite regular lattices of a different structure. We are thus led to conjecture that all of them are always positive. These considerations are generalized to the study of related bounds on finite graphs bearing some similarity to infinite regular lattice models, namely regular biconnected graphs and finite grids. The validity of the bounds $\Delta^k {\rm ln}(i! N(i)) \le 0$ for $k \ge 2$, where $N(i)$ is the number of configurations of $i$ dimers on the graph and $\Delta$ is the finite difference operator, is shown to correspond to the positivity of the virial coefficients. An exhaustive survey of some classes of regular biconnected graphs with a not too large number $v$ of vertices shows that there are only few violations of these bounds. We conjecture that the frequency of the violations vanishes as $v \to \infty$. These bounds are valid also for square and triangular $N \times N$ grids with $N \le 19$ or $N \le 18$ respectively, and with open boundary conditions, giving some support to the conjecture on the positivity of the virial coefficients. \end{abstract} \pacs{ 05.50.+q, 64.60.De, 75.10.Hk, 64.70.F-, 64.10.+h} \keywords{Dimer problem } \maketitle \section{Introduction} The virial expansion coefficients of the pressure have been computed for the monomer-dimer (MD) models on various infinite regular lattices. Presently, they are known\cite{kenzie} through order $19$ for the tetrahedral lattice and through order $7$ for the hexagonal lattice\cite{Ftri}. Moreover, they are known for the triangular and the fcc lattices through orders $14$ and $10$ respectively\cite{gaunt, kurtze}. In the case of the one-dimensional dimer model, they are all known\cite{fp}. We have recently computed them through order $24$ for the $bcc$ lattices\cite{bp1} in $d=3,4,5,6,7$ and for hypercubic lattices through order $24$ for the square, cubic and $4d$ hypercubic models, through order $22$ and $21$ in dimensions $d=5$ and $ 6$ respectively, and finally\cite{bfp} in general dimensions through the order $20$. Heilmann and Lieb\cite{HL1, HL} have also studied the MD models on finite graphs. They have shown that the zeroes of the matching generating polynomial $\sum N(i) z^i$ of a graph lie only on the negative real axis of the complex plane of the activity $z$. In the thermodynamic limit, this implies the absence of a phase-transition in the MD models. In this paper, we show that the first $20$ coefficients of the virial expansion on hypercubic infinite lattices of any dimension are positive. Together with the observation that all the coefficients of the virial expansions of the MD model computed up to now are positive on all infinite regular lattices this fact leads us to conjecture that in general all virial coefficients are positive for these models. Using the definition of the graph dimer entropy\cite{bfp} we argue that for a finite regular graph the bounds which correspond to the positivity of the virial coefficients for infinite regular lattices are \begin{equation} \Delta^k {\rm ln}(i! N(i)) \le 0 \label{Delta0} \end{equation} with $k=2,...,\nu$ and $i=0,...,\nu-k$, where $\nu$ is the maximum value of $i$ for which the number of $i$-dimer configurations on the graph $N(i)$ is non vanishing. The validity of the bound in the case $k=2$ follows from Eq.(4) in [\onlinecite{HL1}]. We have tested the validity of Eq.(\ref{Delta0}) in two classes of finite graphs which are related to infinite regular lattices. The first class consists in biconnected regular graphs, the second one consists in finite grids. The tests of Eq.(\ref{Delta0}) for the first class have been performed by generating all biconnected regular graphs with certain limits on the number of vertices $v$, with the aid of the {\it Nauty} program\cite{nauty} via the {\it Sage} interface\cite{Sage}. In the case of the bipartite connected $3$-regular graphs, we could test these bounds through $v=28$ vertices. There are a few violations of the bounds for $v \ge 18$, and the frequency of the violations decreases regularly for $v \ge 18$. In the case of bipartite connected $4$-regular graphs, we have tested Eq.(\ref{Delta0}) through order $v=22$. We observe a single violation for $v=20$; the frequency of violations is even lower for $v=22$. In the case of bipartite connected with degree larger than $4$ we tested cases only to order $20$, finding only one violation, occurring in the case of degree $5$. When considering non-bipartite biconnected $3$-regular graphs, we observed few violations for $v \le 28$, starting from $v=12$; again the frequency of the violations decreases regularly for $v \ge 12$ even. Up to $v=22$ the testing has been exhaustive, beyond that case we used a uniform random distribution to sample graphs. In the case of non-bipartite biconnected $4$-regular graphs, the frequency of the violations decreases regularly for $v$ even after the first violation; similarly for $v$ odd. We could complete the tests only up to $v=17$, in which case one has to consider over $80$ million graphs. Based on the results of this survey, we are led to conjecture that, for biconnected regular graphs, the frequency of violations of the bounds vanishes as $v \to \infty$. We have also shown that these bounds are satisfied by the average bipartite regular graph distribution obtained\cite{FKM} from $0-1$ $n\times n$ matrices with row and column sums equal to $r$. This gives a strong indication that this conjecture is true for bipartite regular graphs. Let us now turn to the class of finite lattices. We are interested in finding sequences of finite lattices with no violations of the bounds Eq.(\ref{Delta0}), which would indicate that all the virial coefficients are positive for the corresponding infinite regular lattices. Even if the bounds Eq.(\ref{Delta0}) have been derived only for regular graphs, we will consider them also in the case of finite grids with open boundary conditions. In the case of square grids $M \times N$ with $M \le 19$ and $N \le M$ (open boundary conditions), there are no violations of the bounds. Also for triangular lattices grids $M \times N$ with $4 \le M \le 18$ and $4 \le N \le M$ (open boundary conditions), there are no violations. In the case of hexagonal lattices $M \times N$ (in the brick-wall representation with periodic boundary conditions), there are no violations for $4 \le M \le 14$, $M \ge N$. The paper is organized as follows. In the second Section, using a simple relation between the coefficients of the virial expansion of the pressure and the expansion coefficients of the dimer entropy, we prove that on hypercubic lattices the virial coefficients through order $20$ are positive for generic $d$. In the third Section we derive Eq.(\ref{Delta0}). The fourth Section summarizes the results of the graph tests for a variety of graphs and lattices. In Appendix A, the validity of Eq.(\ref{Delta0}) is proven for the polygons, for the complete graphs, for the complete bipartite graphs and for an approximate average distribution of bipartite regular graphs. \section{Positivity of virial coefficients} The combinatorial-statistical properties of the lattice MD system are usually described in the grand-canonical formalism of the statistical mechanics, in which the pressure is defined as \begin{equation} \lim_{N \to \infty} \frac{1}{N} {\rm ln} \Xi_N(z) = P_d(z) =\sum_i b_i(d)z^i. \label{pr} \end{equation} Here $\Xi_N(z)$ is the grand-canonical partition function for a $N$-site $d$-dimensional lattice and $z$ is the activity. The dimer density is then \begin{equation} \rho_d(z) = z \frac{dP_d} {dz} = \sum_{i=1}^{\infty}i b_i(d) z^i \label{den} \end{equation} Setting $p = 2\rho$, and solving Eq.(\ref{den}) for $z = z(p)$, we can express the pressure in terms of $p$ \begin{equation} P(p) = p/2 + \sum_{k=2}^{\infty} m_k p^k \label{vir} \end{equation} This is the virial expansion. The entropy is defined by \begin{equation} \lambda_d(p)=-\rho(z) {\rm ln} z + P(z) \label{entr} \end{equation} from Eqs.(\ref{den}) and (\ref{entr}) one gets \begin{equation} \frac{d \lambda_d}{d p} = -\frac{\ln z}{2} \label{dla} \end{equation} Using the expansion\cite{FF, bfp} \begin{equation} \lambda_d(p)= R(p) + \sum_{k=2}^{\infty}a_k p^k \label{entr2} \end{equation} where \begin{equation} R(p) = \frac{1}{2}(p{\rm ln}(r)-p{\rm ln}p -2(1-p){\rm ln}(1-p)-p) \label{entrR} \end{equation} and $r$ is the lattice coordination number, from Eq.(\ref{dla}) one has \begin{equation} \ln z = \ln(\frac{p}{r(1-p)^2}) -2\sum_{k=2}^{\infty} ka_kp^{k-1}. \label{logz} \end{equation} Then from Eqs.(\ref{vir}), (\ref{entr}), (\ref{entr2}) and (\ref{logz}) a simple relation is obtained between the coefficients $m_k$ of the virial expansion and the coefficients $a_k$ of the entropy expansion \begin{equation} m_k = (k-1)(\frac{1}{k(k-1)} - a_k) \label{mayer} \end{equation} In the case of hypercubic lattices in any dimension $d$ the coefficients $a_k(d)$ have been computed in [\onlinecite{bfp}] through the order $20$. On these lattices, we can express the coefficients of the virial expansion and the entropy expansion as simple polynomials in the variable $1/d$. Using the expressions for $a_k(d)$ with $k \le 20$ in Ref.[\onlinecite{bfp}] to examine the real roots of $m_k(d)$, reported in Table \ref{tabr}, and observing that, for large $d$, the leading coefficient of $m_k(d)$ is positive, it follows that $m_k(d)$ is positive for any integer $d$ with $d \ge 1$. \begin{table}[ht] \caption{ Real roots of $m_k(d)$ for $k \le 20$} \begin{tabular}{|c|c|c|c|c|} \hline $k=2$& 0.25 & && \\ $k=3$& -0.354 & 0.354 && \\ $k=4$& -0.859 & && \\ $k=5$& none & && \\ $k=6$& -0.239 & && \\ $k=7$& -2.032 & 0.848 &&\\ $k=8$& -1.796& -0.557& 0.859&\\ $k=9$& 1.044& 1.257&&\\ $k=10$& -0.655& 1.029& 1.313&\\ $k=11$& -3.404& 0.998&&\\ $k=12$& -3.241& -0.125& 0.997&\\ $k=13$& 1.000097& 1.725&&\\ $k=14$& 0.9994 &&&\\ $k=15$& -4.657& 0.999997 &&\\ $k=16$& -4.617& 1.000004& 1.801&\\ $k=17$& 1.000000085& 1.963 &&\\ $k=18$& 0.99999993 &&&\\ $k=19$& -5.852& 0.999999998& 2.005& 2.396\\ $k=20$& -5.879& 1.000000001& 1.993 &\\ \hline \end{tabular} \label{tabr} \end{table} As remarked in the introduction, all the virial expansion coefficients so far computed for the lattice dimer models are positive. This leads us to conjecture that they are all positive on all infinite regular lattices. Note that with the assumption that the virial coefficients are all positive, one gets an upper bound on the $a_k$, \begin{equation} a_k \le \frac{1}{k(k-1)} \label{quousquetandem} \end{equation} \section{Derivation of the bounds in Eq.(\ref{Delta0}). } In Ref.[\onlinecite{bfp_pos}] we introduced the Newton series for the dimer entropy of a graph, in terms of the quantities \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 where $N(i)$ is the number of configurations of $i$ dimers on the graph $G$ with $v$ vertices and $\bar N(i)$ is the number of configurations of $i$ dimers on the completed graph with $\bar v=2\nu$ and $\nu$ the maximum value of $i$ for which $N(i)\neq 0$; \begin{equation} \bar N(i) = \frac{\bar{v}!}{(\bar{v}-2i)!i!2^i} \label{nbar} \end{equation} If there is a perfect matching $v = \bar{v}$. For a graph which satisfies the ``graph positivity'' property of Ref.[\onlinecite{bfp_pos}] one has \begin{equation} \Delta^k[d](i) \geq 0 \label{Delta} \end{equation} \noindent where $k=0,...,\nu$ and $i=0,...,\nu-k$. It is in fact equivalent to only require this when $i=0$. If the ``graph positivity'' conjecture of Ref. [\onlinecite{bfp_pos}] is true, then eq.(\ref{Delta}) holds for almost all regular bipartite graphs (in a reasonable sense). In particular, if this conjecture is true, then for each $q$ the fraction of regular bipartite graphs of degree $q$ and number of vertices $v$ that satisfy eq.(\ref{Delta}) tends to $1$ as $v \to \infty$. This positivity property is often satisfied also in non-regular bipartite graphs, while it is usually not satisfied by non-bipartite graphs. We have a similar situation here. Based upon the conjecture that all virial coefficients are positive for dimer models on infinite regular lattices, we make the following conjecture: that the fraction of regular graphs with $v$ vertices that satisfies \begin{equation} \Delta^k[d](i) \leq \Delta^k {\rm ln}\frac{(\bar v -2i)!\bar v^{2i}} {\bar v !} \label{Delta1} \end{equation} \noindent tends to 1 as $v \to \infty$, when $k=0,...,\nu$ and $i=0,...,\nu-k$. It is equivalent to require this only when $i=0$. So we are getting upper bounds for $d(i)$ and its derivatives. Unfortunately, we do not know how to state mathematically how preponderantly this property holds for finite $v$. This will be seen in the following section. We now trace the path which leads from positivity of the virial series coefficients to Eq.(\ref{Delta1}) in the case of finite lattices. We start from eq.(\ref{mayer}) slightly reformulated \begin{equation} a_k = \frac{1}{k(k-1)} - \frac{1} {k-1} m_k \label{mayer1} \end{equation} From Eq.(11) in [\onlinecite{bfp_pos}] \begin{equation} \frac {1}{v}d(i)-\frac {1}{v} {\rm ln}\frac {(v-2i)!v^{2i}} {v!} \to - \sum_{k=2}^{\infty}\frac{1}{(k-1)}m_kp^k \label{d1} \end{equation} Using Eq.(12) in [\onlinecite{bfp_pos}] and assuming that the $m_k$ are positive, it follows that for $v$ very large and $p \approx \frac{2i}{v}$ finite \begin{equation} \Delta^k[d](i) < \Delta^k {\rm ln}\frac {(v-2i)!v^{2i}} {v!} \label{d1a} \end{equation} The positivity of the virial coefficients and Eq.(\ref{d1}) does not guarantee the validity of Eq.(\ref{d1a}). Anyway we will investigate Eq.(\ref{d1a}) for $i=0,..,\nu-k$. Examining these inequalities for small $v$, we found that replacing $v$ with $\bar{v}$ in Eq.(\ref{d1a}) the number of violations is much smaller; we arrive therefore to Eq.(\ref{Delta1}) above. Using Eqs.(\ref{di}, \ref{nbar}) one can rewrite Eq.(\ref{Delta1}) as \begin{equation} \Delta^k {\rm ln} N(i) \le \Delta^k\left(i\, {\rm ln}(\frac{N(1)v^2}{\bar{N}(1)}) - {\rm ln}(i!)\right) \label{Delta1a} \end{equation} For $k \ge 2$ these bounds reduce to Eq.(\ref{Delta0}). From Eq.(4) in [\onlinecite{HL1}] \begin{equation} \Delta^2 {\rm ln} N(i) \le {\rm ln} \frac{(i+1)([\frac{v}{2}] - i - 1)}{(i+2)([\frac{v}{2}] - i)} \label{hl} \end{equation} it follows that the bounds Eq.(\ref{Delta1a}) for $k=2$ hold for any regular graph. %Let us prove that for $r$-regular lattices Eq.(\ref{Delta1}) %holds for $k = 0, 1$. %For $r$-regular graphs $N(1) = \frac{vr}{2}$ and %$N(2) = \frac{vr}{4}(\frac{vr}{2}-2r+1)$ so that Eq.(\ref{Delta1a}) %holds for $k=1, i=1$; using the $k=2$ case it follows that Eq.(\ref{Delta1a}) %holds for $k=1$. Since Eq.(\ref{Delta1a}) holds for $k=0, i=1$, %from the $k=1$ case one obtains the validity for the $k=0$ case. Let us prove that Eq.(\ref{Delta1}) holds for $k = 0, 1$ for any graph. It is true for $k=1, i=0$, so that using the case $k=2$ it follows that it is true for $k=1$. Similarly for $k=0$. Initially Eq.(\ref{Delta1}) would seem only to hold for the graphs whose limit are used to get the given lattice functions, for example periodic cubical graphs. But we will try to apply eq.(\ref{Delta1}) to all regular biconnected graphs and to finite lattices. \section{Tests on the upper bounds} In the following tests we consider separately bipartite and non-bipartite graphs, since the former have fewer violations than the latter. To generate systematically regular graphs we have used the {\it geng} program in the { \it Nauty} package\cite{nauty}, via the {\it Sage} interface\cite{Sage}. The matching generating polynomials are computed with the aid of the algorithm described in [\onlinecite{bpalg}]. To perform our computations we have used an ordinary desktop personal computer based on a processor Intel $i7$ $860$ with a RAM of 8 $GB$. We have tested the validity of the upper bounds Eq.(\ref{Delta1}) for regular bipartite connected graphs (RBB), by enumerating and studying exhaustively a large class of graphs. Up to $v=18$ vertices, we observe a single violation in the case of a $3$-regular graph with $v=18$. For $3$-regular graphs with $ 18 \le v \le 28$, the frequency of the violations decreases with increasing $v$. 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 a few times larger than the average order of the automorphism group of all the RBB graphs with the same degree. The same is true in the following tests in this section. \begin{table}[ht] \caption{For RBB graphs with $18 \le v \le 28$ vertices of degree 3, we have listed the number of graphs in this class, the number of violations of the upper bounds, the average order $ng$ of the automorphism group of graphs, the average order $ngv$ of this group for graphs violating the bounds Eq.(\ref{Delta0}). $k$ is the minimum value for which Eq.(\ref{Delta0}) is violated. } \begin{tabular}{|c|c|c|c|c|c|} \hline $v$ & number of graphs & violations & $ng$ & $ngv$ & $k$\\ \hline 18& 149& 1& 15.1 & 64. & 9\\ 20& 703& 3& 8.7 & 91. & 10\\ 22& 4132& 13& 4.5 & 40. & 9\\ 24& 29579& 38& 3.3 & 32. & 7\\ 26& 245627& 253& 2.3 & 22. & 7\\ 28& 2291589& 1392& 1.9& 20. & 6\\ \hline \end{tabular} \label{tabdeg3} \end{table} For RBB graphs with degree $4$ there is one violation for $v=20$ and $k=10$ is the minimum value for which Eq.(\ref{Delta0}) is violated. The order of the automorphism group of the violating graph is $256$, while the average order is $3.1$. For $v=22$ there are $5$ violations out of $2806490$ graphs and the minimum value for which Eq.(\ref{Delta0}) is violated is $k=11$; the order of the automorphism group of the violating graph is $3722.$ while the average order is $1.5$. For RBB graphs with degree $5$ the first violation is with $v=20$ with $k=9$; the order of the automorphism group of the violating graph is $1327104$, while the average order is $7.1$. For RBB graphs with degree larger than $5$ we considered up to $v=20$; there are no violations. In the case of biconnected $3$-regular non-bipartite graphs with $v$ up to $v=22$ there is a first violation for $v=12$; for $v \ge 12$ the frequency of the violations decreases with $v$, see Table \ref{tabdeg3n}. \begin{table}[ht] \caption{For biconnected regular non-bipartite graphs with degree 3, we have listed the number of graphs in this class, the number of violations of the upper bounds, the average order $ng$ of the automorphism group of graphs, the average order $ngv$ of this group for graphs violating the bounds Eq.(\ref{Delta0}). The cases with $v$ odd are not listed, since there is no graph. $k$ is the minimum value for which Eq.(\ref{Delta0}) is violated. } \begin{tabular}{|c|c|c|c|c|c|} \hline $v$ & number of graphs & violations & $ng$ & $ngv$ & $k$\\ \hline 12& 76& 1& 7.4& 16. & 6\\ 14& 467& 6& 4.4& 8.7 & 6\\ 16& 3836& 44& 3.1& 8.3 & 5\\ 18& 39717& 257& 2.2& 7.5 & 5\\ 20& 497115& 2856& 1.7& 5.6 & 5\\ 22& 7183495& 29597& 1.5& 4. & 5\\ \hline \end{tabular} \label{tabdeg3n} \end{table} To investigate the frequency of violations for higher $v$, where there are too many graphs to be enumerated in a reasonable time, we produced one million graphs randomly for each $v$ using the Networkx [\onlinecite{networkx}] random regular graph generator, which gives asymptotically a uniform distribution for small $r/v$. We checked for doublers among the violating graphs, and assumed that the frequency of doublers for all the graphs is the same as for the violating graphs; the doublers decrease as $v$ increases, they are $5\%$ for $v=22$, $1\%$ for $v=24$, zero for $v \ge 26$. For $v=22,24,26,28,30$ we obtained respectively the frequencies of violations $0.0036(5), 0.0032, 0.0029, 0.0022, 0.0017$. In the case of biconnected $4$-regular non-bipartite graphs with $v$ up to $v=17$ the first violations are for $v=12$, as shown in Table \ref{tabdeg4n}. \begin{table}[ht] \caption{For biconnected regular non-bipartite graphs with degree 4, we have listed the number of graphs in this class, the number of violations of the upper bounds, the average order $ng$ of the automorphism group of graphs, the average order $ngv$ of this group for graphs violating the bounds Eq.(\ref{Delta0}). $k$ is the minimum value for which Eq.(\ref{Delta0}) is violated. } \begin{tabular}{|c|c|c|c|c|c|} \hline $v$ & number of graphs & violations & $ng$ & $ngv$ & $k$\\ \hline 12& 1538& 2& 3.4& 40 & 6\\ 13& 10768& 0& & &\\ 14& 88112& 12& 1.6& 17 & 6\\ 15& 805281& 30& 1.3& 14.& 7\\ 16& 8036122& 454& 1.2& 14. & 6\\ 17& 86214189& 295& 1.2& 10. & 6\\ \hline \end{tabular} \label{tabdeg4n} \end{table} Unlike in the bipartite case and in the non-bipartite case with degree $3$, there are graphs for $v$ odd. The subsequence with $v$ even is regularly decreasing after the first violation, as well as the one with $v$ odd. Let us now turn to testing Eq.(\ref{Delta0}) on finite lattices. In the case of rectangular grids $M \times N$, with open boundary conditions, we examined the cases $2 \le M \le 19$ and $2 \le N \le M$, finding no violations to Eq.(\ref{Delta0}). In the case of periodic square grids $N \times N$ we considered the cases with $N \le 12$, with $N$ even; there is no violation. In the case of hexagonal lattices $M \times N$ in the brick-wall representation with periodic boundary condition there are no violations for $4 \le M \le 14$, $M \ge N$; there are violations for $M < N$ and $M=4,6$; the minimum value for which Eq.(\ref{Delta0}) is violated is $k=20$. In the case of triangular grids $M \times N$, obtained by adding a SW-NE diagonal in a rectangular grids $M \times N$, with open boundary conditions, for $2 \le M \le 18$ and $2 \le N \le M$ there are violations only for $M \times 3$ with $M \ge 10$. The minimum value for which Eq.(\ref{Delta0}) is violated is $k=16$. For all the graphs examined in this section Eq.(\ref{Delta0}) is satisfied for $k \le 4$. It would be interesting to know if they are always satisfied for regular biconnected graphs. In the case of non-regular biconnected graphs there are violations for $k=3,4$. \section{Conclusions} We have observed that the coefficients of the virial expansions of the MD model computed up to now are positive on all infinite lattices. We have shown that the first $20$ coefficients of the virial expansion for hypercubic infinite lattice of any dimension $d$ are positive. This lead us to conjecture that the virial coefficients are all positive for any infinite lattice model. Using a simple relation between virial coefficients and the coefficients of the series for the dimer entropy, we introduced the bounds in Eq.(\ref{Delta0}) for finite graphs which have some feature in common with infinite lattice graphs, namely biconnected regular graphs and finite lattice graphs. Testing Eq.(\ref{Delta0}) on finite sequences of graphs one can check whether they tend to agree with the virial positivity conjecture. In the case of $N \times N$ grids of square and triangular lattices, we tested Eq.(\ref{Delta0}) holds up to $N=19$ and $N=18$ respectively in the open boundary condition case; in the case of the hexagonal lattice $N \times N$ in the brick-wall representation with periodic boundary conditions Eq.(\ref{Delta0}) holds up to $N=14$. This is consistent with the conjecture of the positivity of the virial expansions coefficients in the case of square, hexagonal and triangular lattices. In the case of bipartite connected $3$-regular graphs, we tested Eq.(\ref{Delta0}) to order $v=28$. There are a few violations of this property for $v \ge 18$. The frequency of the violations decreases regularly for $v \ge 18$. In the case of bipartite connected $4$-regular graphs, we tested Eq.(\ref{Delta1}) to order $v=22$. There is one violation for $v=20$; the frequency of violations is lower for $v=22$. A class of bipartite connected $4$-regular graphs with higher values of $v$ which we tested is the $N \times N$ square lattice with periodic boundary conditions; for $N \le 12$ Eq.(\ref{Delta1}) is satisfied. From these considerations we conjecture that for bipartite connected regular graphs of any degree the frequency of violations tends to zero as $v \to \infty$, and that infinite bipartite lattices have all the virial coefficients positive. In the case of non-bipartite biconnected $3$-regular graphs, there are few violations for $v \le 22$ starting from $v=12$; the frequency of the violations decreases for $v \ge 12$. In the case of non-bipartite biconnected $4$-regular graphs with $v \le 17$, the decrease in the frequency of the violations of the $v$-even and odd subsequences is regular after the first violation. Overall the evidence for the validity of Eq.(\ref{Delta0}) for non-bipartite graphs is weaker than in the bipartite case: in the case of infinite non-bipartite lattices, we have data only for two models, not extending to high orders. On finite regular lattices, there are many more graphs for given $v$ than in the bipartite case, so that we could obtain less information with Nauty than in the bipartite case. Besides, in the bipartite case an average distribution of regular graphs satisfies Eq.(\ref{Delta0}), but we do not know enough about the average distribution of non-bipartite regular graphs. Only in the case of finite lattice grids, do we have a comparable confirmation of Eq.(\ref{Delta0}) for bipartite and non-bipartite cases. It would be interesting to investigate further the non-bipartite case. There are a few similarities between the graph positivity property\cite{bfp_pos} and Eq.(\ref{Delta0}): in both cases for the bipartite connected regular graphs the frequency of violations decreases regularly after the first violation; the violating graphs have an average order of the automorphism group which is a few times larger than the average over all the graphs with the same $v$. \section{Appendix A} Define \begin{equation} u(i) = {\rm ln}\frac{(\bar v -2i)!\bar v^{2i}} {\bar v !} \label{ui} \end{equation} where $v, \bar{v}$ are defined in Section II. One gets \begin{equation} \Delta u(i) = {\rm ln} \frac{v^2}{(v-2i)(v-2i-1)} \label{dui} \end{equation} Define $D(i) = d(i) - u(i)$; the inequalities Eq.(\ref{Delta1}) read \begin{equation} \Delta^k D(i) \le 0 \label{Delta2} \end{equation} Since $d(1) = 0$, the case $k=i=0$ in Eq.(\ref{Delta2}) is trivially satisfied. For a polygon $C_v$ with $v$ vertices one has\cite{bfp} \begin{equation} \Delta d(i) = -{\rm ln}(1 - \frac{i}{v-1}) \label{Delta1p} \end{equation} For $v \ge 2$ one gets for $m \ge 0$ \begin{equation} \Delta^{m+1} D(i) = \sum_{j=1}\frac{1}{j}(\frac{1}{(v-1)^j} - (\frac{2}{\bar{v}})^j)\Delta^m i - \sum_{j=1}\frac{1}{j\bar{v}^j} \Delta^m(2i+1)^j \label{Delta1pa} \end{equation} For $v \ge 2$ one has $\frac{1}{(v-1)} \le \frac{2}{\bar{v}}$; since $\Delta^m i^j \ge 0$ and $\Delta^m (2i+1)^j \ge 0$ it follows that $\Delta^{m+1} D(i) \le 0$. For $m > 0$ this gives Eq.(\ref{Delta2}) for $k > 0$. The case $k=0$ in Eq.(\ref{Delta2}) follows from the case $m=0$ in Eq.(\ref{Delta1pa}) and the case $k=i=0$ in Eq.(\ref{Delta2}). In the case of the complete graph $K_{v}$ one has $d(i) = 0$, so that Eq.(\ref{Delta2}) becomes $\Delta^k u(i) \ge 0$, which is easily verified. In the case of the complete bipartite graph $K_{n,n}$ \begin{equation} \Delta d(i) = {\rm ln} \frac{(2n-1)(n-i)}{n(2n-2i-1)} \end{equation} so that \begin{equation} \Delta D(i) = -{\rm ln}\frac{2n}{2n-1} + 2{\rm ln}(1 - \frac{i}{n}) \le 0 \end{equation} so that the case $k=0$ in Eq.(\ref{Delta2}) follows. One gets from the previous equation for $m \ge 1$ \begin{equation} \Delta^{m+1} D(i) = -2\sum_{j=1}\frac{1}{jn^j}\Delta^m(i^j) \le 0 \end{equation} so that Eq.(\ref{Delta2}) is satisfied. Friedland, Krop and Markstr$\ddot{ \rm o}$m\cite{FKM} have computed $n\times n$ matrices with row and column sums equal to $r$ \begin{equation} N(i) = \frac{\binom{n}{i}^2 r^{2i} i!(r n - i)!}{(r n)!} \end{equation} One gets \begin{equation} \Delta D(i) = -{\rm ln}\frac{2n}{2n-1} - {\rm ln}\frac{2n}{2(n-i)} - {\rm ln}\frac{rn-i}{r(n-1)} \le 0 \end{equation} so that Eq.(\ref{Delta2}) is satisfied for $k=0$. From the previous equation, with $m \ge 1$, \begin{equation} \Delta^{m+1} D(i) = \sum_{j=1}\frac{1}{jn^j}(2 - r^{-j})\Delta^m(i^j) \le 0 \end{equation} so that Eq.(\ref{Delta2}) is satisfied. It is easy to show that also the bipartite mean-field approximation \begin{equation} N(i) = \binom{n}{i}^2 i! \left(\frac{r}{n}\right)^i \end{equation} satisfies the bounds Eq.(\ref{Delta0}) for $k \ge 2$. \clearpage \begin{thebibliography}{} \bibitem{kenzie} S. McKenzie, ``Extended high-temperature low-field expansions for the Ising model'', \emph{Can. J. Phys.} {\bf 57}, 1239 (1979). \bibitem{bp1} P. Butera and M. Pernici, ``Yang-Lee edge singularities from extended activity expansions of the dimer density for bipartite lattices of dimensionality $2 \leq d \leq 7$'', \emph{Phys. Rev.} E {\bf 86}, 011104 (2012). \bibitem{Ftri} P.Federbush, ``For the Monomer-Dimer Problem on Triangular and Hexagonal Lattices, the New $p$-Expansion", arXiv:1110.0684. \bibitem{gaunt} D.S. Gaunt, `` Exact Series-Expansion Study of the Monomer-Dimer Problem'', \emph{ Phys. Rev.} {\bf 179}, 174 (1969). \bibitem{kurtze} D. A. Kurtze and M.E. Fisher,''Yang-Lee edge singularity at high temperature'', \emph{ Phys. Rev.} B {\bf 20}, 2785 (1979). \bibitem{fp} S. Friedland and U. N. Peled, `` Theory of computation of multidimensional entropy with an application to the monomer-dimer problem'', \emph{Adv. Appl. Math.} {\bf 34}, 486 (2005). \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{HL1} O.J.Heilmann and E.H. Lieb, ``Monomers and Dimers'', \emph{Phys. Rev. Lett.} {\b 24} (1970) 1412. \bibitem{HL} O.J.Heilmann and E.H. Lieb, ``Theory of Monomer-Dimer Systems'', \emph{Commun. math. Phys.} {\bf 25}, 190 (1972). \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{bfp_pos} P. Butera, P. Federbush and M. Pernici, ``A positivity property of the dimer entropy of graphs ``, arXiv:1409.4549. \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{FKM} S. Friedland, E. Krop and K. Markstr$\ddot{ \rm o}$m, ``On the Number of Matchings in Regular Graphs'', {\it Electron. J. Combin.} {\bf 15}, R110 (2008). \bibitem{bpalg} P. Butera and M. Pernici, ``Sums of permanental minors using Grassmann algebra'', arxiv:1406.5337. \bibitem{networkx} Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008 \end{thebibliography} \end{document} ---------------1411020928570--