Bethe permanent approximation bounds at fixed support girth

For a nonnegative n×n matrix whose bipartite support graph has even girth at least g≥4, is its permanent at most 2^(2n/g) times its Bethe permanent? The reverse inequality is known; disjoint g-cycles give candidate equality cases when g divides 2n.

Why it matters and what counts as progress

Why it matters: Girth isolates how short support cycles affect the accuracy of the Bethe permanent, refining the universal approximation factor.

What counts as progress: Prove the optimal girth-dependent upper factor, characterize equality, or improve bounds for other support-graph restrictions.

How the problem developed

2011 · Lower bound [1]
Leonid Gurvits Established the lower comparison Bethe(A)≤per(A) for nonnegative matrices.
2019 · Upper bound [2]
Nima Anari and Alireza Rezaei Proved the tight universal upper comparison per(A)≤2^(n/2)Bethe(A), with equality on disjoint 4-cycles.
2 Sept 2026 · Reported claim [3]
Dingding Dong and Vishesh Jain Proved the optimal girth refinement per(A)≤2^(2n/g)Bethe(A) when the bipartite support graph has even girth at least g; disjoint g-cycles attain equality.

AI contribution

Optimal girth-dependent bounds for the Bethe approximation of the permanent

Dingding Dong, Vishesh Jain

Dong and Jain report that, for a nonnegative n-by-n matrix whose bipartite support graph has girth at least even g>=4, Theorem 1.3 proves Bethe(A)<=per(A)<=2^(2n/g)Bethe(A); disjoint unions of g-cycles attain the upper bound when g divides 2n. The model-developed intermediate proof had a weaker exp(n Theta(log g/g)) factor; the exact model-origin step retained in the final sharp proof is not identified.

AI involvementAI-centered

ImportanceNotable

Technical verificationReported

Human understandingFull