{"id":"arxiv/2609.02017","url":"https://arxiv.org/abs/2609.02017","tags":["math.CO","cs.DS"],"score":0,"title":"Optimal girth-dependent bounds for the Bethe approximation of the permanent","domain":"math.CO","source":"arxiv","authors":["Dingding Dong","Vishesh Jain"],"reviews":0,"subject":"math.CO","summary":"For an $n\\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \\[\\operatorname{Bethe}(A) \\leq \\operatorname{per}(A) \\leq 2^{n/2}\\operatorname{Bethe}(A).\\] The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of $4$-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of $A$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}