The Anari-Oveis Gharan-Vinzant perfect-matching entropy conjecture

Theorem 1.1: for a loopless multigraph on $2m\ge2$ vertices with a perfect matching and every $x\in P(G)$, boundary included, $F(x)-(2-2/m)B(x)\le H(x)\le F(x)$, where $H(x)$ is the maximum entropy of a law on perfect matchings with marginals $x$. Hence $\log N(G)\le\max_{x\in P(G)}(F+B)\le\log N(G)+3m-2$, the conjectured linear error with an explicit constant. Also proved: the sharp bound $|\mathrm{supp}\,x|-\dim F_x\le3m-2$ for the minimal face, and lower counts such as $N(G)\ge e^{-2(m-1)}k^m$ for $k$-regular graphs with all odd cuts of size at least $k$. The paper notes the bipartite coefficient-one inequality $H\ge F-B$ fails for a nonbipartite eight-vertex example.

Theorem 1.1: for a loopless multigraph on $2m\ge2$ vertices with a perfect matching and every $x\in P(G)$, boundary included, $F(x)-(2-2/m)B(x)\le H(x)\le F(x)$, where $H(x)$ is the maximum entropy of a law on perfect matchings with marginals $x$. Hence $\log N(G)\le\max_{x\in P(G)}(F+B)\le\log N(G)+3m-2$, the conjectured linear error with an explicit constant. Also proved: the sharp bound $|\mathrm{supp}\,x|-\dim F_x\le3m-2$ for the minimal face, and lower counts such as $N(G)\ge e^{-2(m-1)}k^m$ for $k$-regular graphs with all odd cuts of size at least $k$. The paper notes the bipartite coefficient-one inequality $H\ge F-B$ fails for a nonbipartite eight-vertex example.