Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation

Abstract

Let $A\in {\Omega }_n$ be doubly-stochastic $n\times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n. We use the above Shrijver's inequality to prove the following lower bound: \frac{per(A)}{F(A)} \geq 1; F(A) =: \prod_{1 \leq i,j \leq n} (1- A(i,j))^{1- A(i,j)}. We use this new lower bound to prove S.Friedland's Asymptotic Lower Matching Conjecture(LAMC) on monomer-dimer problem. We use some ideas of our proof of (LAMC) to disprove [Lu,Mohr,Szekely] positive correlation conjecture. We present explicit doubly-stochastic $n\times n$ matrices $A$ with the ratio $\frac{per(A)}{F(A)}={\sqrt{2}}^n$; conjecture that \max_{A \in Ω_n}\frac{per(A)}{F(A)} \approx (\sqrt{2})^{n} and give some examples supporting the conjecture. If true, the conjecture (and other ones stated in the paper) would imply a deterministic poly-time algorithm to approximate the permanent of $n\times n$ nonnegative matrices within the relative factor $(\sqrt{2}{)}^n$. The best current such factor is $e^n$.

30 pages, more typos are fixed, more remarks are added, importantly a concrete counter-example to [Lu,Mohr,Szekely] positive correlation conjecture is presented

References in corpus (4)

• Approximating the Permanent with Belief Propagation
• Combinatorial and algorithmic aspects of hyperbolic polynomials
• Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix
• A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

Cited by in corpus (16)

• The Bethe Partition Function of Log-supermodular Graphical Models
• Extremal regular graphs: independent sets and graph homomorphisms
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• Extremal regular graphs: the case of the infinite regular tree
• New Understanding of the Bethe Approximation and the Replica Method
• A positivity property of the dimer entropy of graphs
• On the Degeneracy of Spin Ice Graphs, and its Estimate via the Bethe Permanent
• The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood
• Loop Calculus and Bootstrap-Belief Propagation for Perfect Matchings on Arbitrary Graphs
• Approximating the Bethe partition function
• Bounding the Bethe and the Degree-$M$ Bethe Permanents
• A conjecture on independent sets and graph covers
• Phase Transitions for the Uniform Distribution in the PML Problem and its Bethe Approximation
• Asymptotic Behavior of the Expectation Value of Permanent Products, a Sequel
• Matchings in regular graphs: minimizing the partition function
• Capacity of Lorentzian polynomials and distance to binomial distributions