Entropy bounds for perfect matchings with prescribed marginals
Follow the latest progress by email.
For a loopless multigraph on 2m vertices and feasible edge marginals x, let H(x) be the largest entropy of a random perfect matching with those marginals. How accurately can H(x) be estimated by coordinate-entropy expressions?
Why it matters and what counts as progress
Why it matters: An error linear in the number of vertices would extend useful convex estimates from bipartite to general-graph perfect matchings.
What counts as progress: A uniform linear-error estimate for every feasible x, with the entropy terms and graph assumptions stated, or an example violating it.
How the problem developed
- 2 Jul 2018 · Framework [1]
Nima Anari, Shayan Oveis Gharan and Cynthia Vinzant Developed a log-concave polynomial and entropy framework for counting matroid bases, providing background for later entropy questions about matching laws.
- 23 Sept 2026 · Reported claim [2]
OpenAI internal model The preprint claims a sharp pointwise entropy inequality at every feasible edge-marginal vector for loopless labelled multigraphs, including boundary points, and also determines matching-polytope face dimensions.
AI contribution
Entropy and Face Dimension of the Perfect-Matching Polytope
For a loopless multigraph on 2m vertices with a perfect matching and feasible edge marginals x, the maximum entropy H(x) satisfies F(x)−(2−2/m)B(x)≤H(x)≤F(x), where F and B sum the binary-coordinate entropy terms. Optimizing gives the linear-error estimate proposed by Anari, Oveis Gharan and Vinzant.
Sources
- Anari, Oveis Gharan and Vinzant, Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids
- OpenAI, Entropy and Face Dimension of the Perfect-Matching Polytope
- Entropy and Face Dimension of the Perfect-Matching Polytope
- OpenAI perfect-matching entropy manuscript
- Exact pointwise entropy comparator
- Lean proof of a weaker matching bound
- Anari–Oveis Gharan–Vinzant entropy framework
- OpenAI mathematics release account
Website timeline
Publication dates and editorial changes.