加载中…
For an nonnegative matrix , the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison 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 -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 has girth at least an even integer , then The upper bound is attained by the adjacency matrix of a disjoint union of -cycles.

生成讲解博客的中文版本

生成AI智能校验的中文版本