Browse › Theoretical computer science › 113 Approximate counting and entropy of perfect matchings
Entropy and Face Dimension of the Perfect-Matching Polytope
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant. For every feasible vector x of perfect-matching edge marginals in a loopless labelled multigraph on $2m\ge2$ vertices, the maximum entropy $H(x)$ of a matching law with marginals x satisfies $\displaystyle F(x)-(2-2/m)B(x)\le H(x)\le F(x),$ where $F(x)=-\sum_e x_e\log x_e$ and $B(x)=-\sum_e(1-x_e)\log(1-x_e)$. This bound holds throughout the polytope, including its boundary. We also prove the sharp bound $|\mathop{\mathrm{supp}}\nolimits x|-\dim F_x\le3m-2$, where Fx is the minimal face of the perfect-matching polytope containing x.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI, Approximate counting and entropy of perfect matchings: Lean scope note (OpenAI math release, 2026-10-06). States that the Lean development proves $F(x)-(2-2/m)B(x)\le H(x)\le F(x)$ including boundary points, the coefficient-eight bound, the $512^n$ and $2^{18n}$ deterministic counting approximations and the triangle-expansion face correspondence; the sharp global face-dimension bound $3m-2$ is not part of the formalized statement. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Noga Alon, Shmuel Friedland, The maximum number of perfect matchings in graphs with a given degree sequence (arXiv:0803.2578, 2008). A Brègman-type upper bound on the number of perfect matchings in general (non-bipartite) graphs, possibly relevant to the paper's upper bounds via $H\le F$ and non-bipartite counting bounds.
- Péter Csikvári, Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems (arXiv:1406.0766, 2014). New proofs of Schrijver's and Gurvits's bipartite lower bounds, which underlie the bipartite coefficient-one comparison $H\ge F-B$ contrasted with the paper's non-bipartite counterexample.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 113
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026,
author = {{OpenAI}},
title = {{Entropy and Face Dimension of the Perfect-Matching Polytope}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026/main.pdf}{OAI:Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/113.md. The Lean statements have not been checked by people against the paper's claims.
Family 113: Approximate counting and entropy of perfect matchings
Gives a fully polynomial randomized approximation scheme for counting perfect matchings in arbitrary finite simple graphs, with exact detection of zero counts. Also proves the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant, bounding the maximum entropy of a matching law at every feasible edge-marginal vector in a loopless labelled multigraph, including boundary points.
Other papers in this family: