Anari's Bethe permanent conjecture
Statement
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.
Record
- Source
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.