Four Amazing Positivities with Dimers/i-Matchings

NEW

Problem: Reconstructed literal conjecture: for each fixed $r$, let $\mathcal G_{n,r}$ be the finite set of simple labelled $r$-regular bipartite graphs with fixed bipartition of size $n+n$. For $G\in\mathcal G_{n,r}$, let $m_i(G)$ be the number of $i$-matchings, set

$$u_i(G)=-\log(i!\,m_i(G)),\qquad 0\le i\le n,$$

and say $G$ has virial positivity if

$$\Delta^k u_i\ge 0\qquad(2\le k\le n,\ 0\le i\le n-k).$$

The conjecture says

$$\frac{|\{G\in\mathcal G_{n,r}:G\text{ has virial positivity}\}|}{|\mathcal G_{n,r}|}\to 1 \quad(n\to\infty).$$

The paper does not state connectedness or $r\ge3$, so $r=2$ disconnected graphs are included in the literal formulation.

Result: The literal conjecture is false.

Take $r=2$. A $2$-regular bipartite graph is a disjoint union of even cycles. If the component half-lengths are $\ell_1,\dots,\ell_c$, $\sum \ell_j=n$, then for a cycle $C_{2\ell}$,

$$q_t(\ell):=\#\{\text{matchings of size }\ell-t\} =\frac{2\ell}{\ell+t}\binom{\ell+t}{2t}.$$

For $s\le4$,

$$m_{n-s}(G)=2^c n^{2s}\,H_s+o(n^{2s}),$$

where, with $x_j=\ell_j/n$,

$$H_s=[y^s]\prod_j \cosh(x_j\sqrt y).$$

Hence

$$\Delta^4u_{n-4} = 4\log H_1-6\log H_2+4\log H_3-\log H_4+o(1).$$

For two macroscopic components with proportions tending to $(1/2,1/2)$,

$$\prod_j\cosh(x_j\sqrt y)\to \cosh(\sqrt y/2)^2,$$

so

$$H_1=\frac14,\quad H_2=\frac1{48},\quad H_3=\frac1{1440},\quad H_4=\frac1{80640}.$$

Therefore

$$4\log H_1-6\log H_2+4\log H_3-\log H_4 = \log\frac{112}{125}<0.$$

By continuity, the same strict negativity holds whenever two components have half-lengths sufficiently close to $n/2$ and all remaining components have total $o(n)$-proportion small enough. Thus such graphs violate virial positivity at $i=n-4,k=4$.

It remains only to note that such graphs occur with positive limiting probability among labelled $2$-regular bipartite graphs. Indeed, if a component size partition has $m_j$ parts of size $j\ge2$, then the number of graphs of that type is

$$n!^2\prod_{j\ge2}\frac{(1/(2j))^{m_j}}{m_j!}.$$

Thus the normalizing generating function is

$$Z(z)=\exp\!\left(\sum_{j\ge2}\frac{z^j}{2j}\right) =e^{-z/2}(1-z)^{-1/2},$$

so $[z^n]Z(z)\sim e^{-1/2}/\sqrt{\pi n}$.

Choose two disjoint intervals $I,J$ very near $1/2$, both below $1/2$, such that for $a/n\in I$, $b/n\in J$, the above negativity still holds. The probability that a random $2$-regular bipartite graph has components of half-lengths $a\in nI$, $b\in nJ$, and arbitrary remaining components is

$$\sum_{a\in nI,\ b\in nJ} \frac1{2a}\frac1{2b}\, \frac{[z^{\,n-a-b}]Z(z)}{[z^n]Z(z)}.$$

The coefficient asymptotic gives a positive limiting lower bound for this sum. Hence a positive proportion of $\mathcal G_{n,2}$ violates virial positivity for all large $n$. The fraction satisfying virial positivity therefore cannot tend to $1$.

This failure is caused by the missing connectedness or $r\ge3$ hypothesis. A natural repair would restrict to connected $r$-regular bipartite graphs, or at least to fixed $r\ge3$; that repaired conjecture is not settled by this counterexample.

Citation: No known literature source is needed for the disproof. Definitions are from Federbush, “Four Amazing Positivities with Dimers/$i$-Matchings,” arXiv:2105.10772. The coefficient asymptotic is the standard transfer theorem for $e^{-z/2}(1-z)^{-1/2}$.