{"id":"openai-math/Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope","pdf":"https://github.com/openai/math/blob/main/preprints/Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026","tags":["combinatorics","entropy","matching-polytope"],"score":0,"title":"Entropy and Face Dimension of the Perfect-Matching Polytope","domain":"Theoretical computer science","family":"113","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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 F x is the minimal face of the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{},"formalized":true,"family_title":"Approximate counting and entropy of perfect matchings"}