Conjecture on the non-integer BP solution for the permanent

From papers

Let PP be a nonnegative matrix, let TcT_c be the critical temperature from Proposition 1, and let βij\beta_i^j denote a solution of the belief-propagation (BP) equations on the edge set EE. The solution under consideration is the non-integer BP solution that emerges from the maximum-likelihood configuration at T=TcT=T_c.

Non-integer BP solution conjecture. The non-integer solution extends beyond the small Tc+εT_c+\varepsilon vicinity of TcT_c and transitions smoothly as TT\to\infty into the fully homogeneous solution

βij=1/Nfor all (i,j)E.\beta_i^j=1/N\quad\text{for all }(i,j)\in E.

Moreover, no other non-integer solutions exist for T<TcT<T_c; consequently, when this solution emerges at T=TcT=T_c, it gives a global minimum of the belief-propagation free energy.

This conjecture concerns the global continuation and uniqueness of the non-integer BP solution beyond the local analysis near the critical temperature. The source presents these claims as plausible conjectures and does not provide a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yusuke Watanabe and Michael Chertkov, “Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix”, arXiv:0911.1419 (2010).

Solutions 0

No solutions have been posted yet.