Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs

Marc Lelarge, Hang Zhou

For a graph $G$, let $Z(G,\lambda )$ be the partition function of the monomer-dimer system defined by ${\sum }_k{m}_k(G){\lambda }^k$, where $m_k(G)$ is the number of matchings of size $k$ in $G$. We…