The Monomer-Dimer Problem, Stable (a.k.a. hyperbolic) Homogeneous Polynomials, and the Bethe Approximation.
Time and place
11 AM on Thursday, May 3rd, 2012; NAC 5-110
Leonid Gurvits (Los Alamos National Laboratory)
Abstract
Van Der Waerden stated in 1926 a conjecture on the minimum value of the permanent of doubly-stochastic matrices. Apparently, the conjecture grew up in his discussion with O. Schreier about G.A. Miller's result on the existence of a system of representatives for the right and left cosets of a subgroup H of a finite group G. The conjecture was resolved independently by Falikman(1979) and Egorychev(1981).
The Monomer-Dimer Problem is one of the major topics in Combinatorics, Statistical Physics, Computational Chemistry, and many other theoretical as well applied fields. The main combinatorial application of Van Der Waerden Conjecture is the lower bound on the number of perfect matchings (dimer coverings) in regular bipartite graphs (possibly with multiple edges). The Monomer-Dimer Problem is (roughly) about bounds on the number of matchings of given density(monomer-dimer coverings) in the same class of graphs. Friedland's Lower Asymptotic Matching Conjecture (LAMC) on Monomer-Dimer Entropy states that the exact asymptotics of the minimum is equal to that of averages over some natural class of distributions.
The Bethe Approximation has been applied to the monomer-dimer problem as a heuristic since the late 1930s. In the last 10--15 years the Bethe Approximation has also become one of the main practical tools in Machine Learning, especially in inference on graphical models. Surprisingly, this practical tool also has amazing theoretical power: L.G. used it to get new lower bounds on the permanent of doubly-stochastic matrices. The main trust of the talk is to sketch a proof of (LAMC), which is based on this new lower bound(s).
A central technique in earlier work on Friedland's Conjecture was the stable (a.k.a. hyperbolic, as in PDE theory) polynomial approach to obtain lower bounds on mixed derivatives. This technique was introduced by L.G. in 2005 and used in series of recent papers to give an unified simple proof of several earlier lower bounds(such as Van Der Waerden and Schrijver-Valiant etc.) and to prove new results, notably an analogue of Van Der Waerden Conjecture for the Mixed Volume of the convex bodies. So we review this algebraic technique as we discuss and compare it to our more recent Bethe approximation approach.
Bio: Leonid Gurvits was born in (Soviet)Bukovina and reborn in Brooklyn. Leonid received his Ph.D in mathematics from Niznii Novgorod State University (USSR) in 1985. He is currently Scientist-5 at Los Alamos National Laboratory. Leonid is world renowned for his breakthrough results in Mathematics, Control Theory, Theoretical Computer Science and Quantum Information.
