2011

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

Gurvits, Leonid

Understand

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.

Built on

H.S. Wilf, On the permanent of a doubly stochastic matrix, Canad. J. Math. 18 (1966) 758-761
1966
Earlier work this paper cites.
L.M. Bregman, Some properties of nonnegative matrices and their permanents, Soviet Math. Dokl, 1973
1973
Earlier work this paper cites.
M. Voorhoeve, A lower bound for the permanents of certain (0,1) matrices, Indagationes Mathematicae 41 (1979) 83-86
1979
Earlier work this paper cites.
A. Schrijver and W.G.Valiant, On lower bounds for permanents, Indagationes Mathematicae 42 (1980) 425-427
1980
Earlier work this paper cites.
G.P. Egorychev, The solution of van der Waerden’s problem for permanents, Advances in Math
1981
Earlier work this paper cites.
D. I. Falikman, Proof of the van der Waerden’s conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki
1981
Earlier work this paper cites.
B.D. McKay, Asymptotics for 0-1 matrices with prescribed line sums, Enumeration and Design, Academic Press, Canada (1984), pp. 225-238
1984
Earlier work this paper cites.
A. Schrijver, Counting 1 1 -factors in regular bipartite graphs, Journal of Combinatorial Theory, Series B 72 (1998) 122–135
1998
Earlier work this paper cites.
S. Szarek and E. Werner, A Nonsymmetric Correlation Inequality for Gaussian Measure, Journal of Multivariate Analysis, Volume 68, Issue 2, 193-211, 1999
1999
Earlier work this paper cites.

Similar

A. Schrijver, Matching, edge-colouring, dimers, in: “Graph-Theoretic Concepts in Computer Science” (H.L. Bodlaender, ed.), Lecture Notes in Computer Science 2880, Springer-Verlag, Berlin, 2003, pp. 13–22
2003
Cited alongside, same era.
B.D. McKay, X. Wang, Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums, Linear Algebra and its Applications; Volume 373, 2003, Pages 273-287
2003
Cited alongside, same era.
L. Gurvits, Combinatorial and algorithmic aspects of hyperbolic polynomials, 2004; available at http://xxx.lanl.gov/abs/math.CO/0404474
2004
Cited alongside, same era.
L. Gurvits, A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification, Electronic Colloquium on Computational Complexity (ECCC)(103): (2005) and arXiv:math/0504397
2005
Cited alongside, same era.
S. Friedland, E. Krop, Per H. Lundow, K. Markström; Validations of the Asymptotic Matching Conjectures, arXiv:math/0603001, 2006
2006
Cited alongside, same era.
L. Gurvits, Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications, Proc. 38 ACM Symp. on Theory of Computing (StOC-2006)
2006
Cited alongside, same era.
I.M. Wanless, Addendum to Schrijver’s work on minimum permanents, Combinatorica 26 (6) (2006) 743-745
2006
Cited alongside, same era.
S. Friedland and L. Gurvits, Lower Bounds for Partial Matchings in Regular Bipartite Graphs and Applications to the Monomer-Dimer Entropy, Combinatorics, Probability and Computing
2008
Cited alongside, same era.
L. Gurvits, Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all, Electronic Journal of Combinatorics 15 (2008)
2008
Cited alongside, same era.

Then

L. Gurvits, A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor. Discrete Comput. Geom
2009
Later among the works it cites.
L. Gurvits, On multivariate Newton-like inequalities. Advances in combinatorial mathematics, 61-78, Springer, Berlin, 2009; available at http://arxiv.org/pdf/0812.3687v3.pdf
Original
2009
Later among the works it cites.
B. Huang, T. Jebara; Approximating the Permanent with Belief Propagation, arXiv:0908.1769, 2009
Original
2009
Later among the works it cites.
M. Laurent and A. Schrijver, On Leonid Gurvits’ proof for permanents, Amer. Math. Monthly 117 (2010), no. 10, 903-911
2010
Later among the works it cites.
P.O. Vontobel, The Bethe permanent of a non-negative matrix, in Proc. of Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, 29 2010-Oct. 1 2010; available at Pascal Vontobel home page
2010
Later among the works it cites.
Yusuke Watanabe and Michael Chertkov, Belief propagation and loop calculus for the permanent of a non-negative matrix, Journal of Physics A: Mathematical and Theoretical Volume 43 Number 24, 2010
2010
Later among the works it cites.
A. Barvinok, A bound for the number of vertices of a polytope with applications, http://arxiv.org/abs/1108.2871, 2011
Original
2011
Closest in time.
L. Lu, A. Mohr, L. Szekely, Quest for Negative Dependency Graphs, preprint, 2012
2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…