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