VibeMathedMath problems solved with AI
Sign in

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

Let GG be a graph on n=2mn=2m vertices with N(G)≥1N(G)\ge1 perfect matchings and perfect-matching polytope P(G)P(G). For x∈P(G)x\in P(G) put F(x)=−∑exelog⁡xeF(x)=-\sum_e x_e\log x_e and B(x)=−∑e(1−xe)log⁡(1−xe)B(x)=-\sum_e(1-x_e)\log(1-x_e). Anari, Oveis Gharan and Vinzant proposed a convex-programming approach to counting, in which max⁡x∈P(G)(F(x)+B(x))\max_{x\in P(G)}(F(x)+B(x)) estimates log⁡N(G)\log N(G); for bipartite graphs the Schrijver and Gurvits inequalities make it accurate. Is it true for every graph that max⁡x∈P(G)(F(x)+B(x))≤log⁡N(G)+O(n)\max_{x\in P(G)}(F(x)+B(x))\le\log N(G)+O(n), that is, that the binary-coordinate entropy of a perfect-matching mean exceeds log⁡N(G)\log N(G) by at most a linear function of the number of vertices?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Approximate counting; matching polytope; entropy
Posed by
Nima Anari, Shayan Oveis Gharan and Cynthia Vinzant, Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids, FOCS 2018, Conjecture 6
Year posed
2018
Years open
8y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
18 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for a loopless multigraph on 2m≥22m\ge2 vertices with a perfect matching and every x∈P(G)x\in P(G), boundary included, F(x)−(2−2/m)B(x)≤H(x)≤F(x)F(x)-(2-2/m)B(x)\le H(x)\le F(x), where H(x)H(x) is the maximum entropy of a law on perfect matchings with marginals xx. Hence log⁡N(G)≤max⁡x∈P(G)(F+B)≤log⁡N(G)+3m−2\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 ∣supp x∣−dim⁡Fx≤3m−2|\mathrm{supp}\,x|-\dim F_x\le3m-2 for the minimal face, and lower counts such as N(G)≥e−2(m−1)kmN(G)\ge e^{-2(m-1)}k^m for kk-regular graphs with all odd cuts of size at least kk. The paper notes the bipartite coefficient-one inequality H≥F−BH\ge F-B fails for a nonbipartite eight-vertex example.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The README also cautions that unformalized results could have issues.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 and the counting corollary of the manuscript were read against Conjecture 6 as the manuscript states it; the conjecture text in the FOCS paper was not opened here. The proof was not refereed. Lean: lean/formalization.yaml lists OAI.MatchingEntropy.entropy_main (Comparator MatchingEntropy). Its statement, read here, is an earlier coefficient-eight bound, F(x)−H(x)≤8m(1−e−F(x)/m)F(x)-H(x)\le 8m(1-e^{-F(x)/m}) for every xx in the polytope; with H≤log⁡NH\le\log N and B≤mB\le m this already gives the conjecture's linear form with constant 9m9m, though not the paper's sharp 3m−23m-2. The sharp pointwise bound F−(2−2/m)B≤H≤FF-(2-2/m)B\le H\le F is the separate challenge MatchingEntropyBounds (OAI.MatchingEntropyBounds.Refined.pointwise_entropy, solution module OAI.Combinatorics.MatchingEntropy.Main, present at the pinned commit), which is not in the formalization catalogue; its statement was read here. Neither development was rebuilt here.

Sources

Changelog1 change

Discussion