Colloquia, Seminars and Conference News
Title : Hyperbolic Polynomials & Van der Waerden/Schrijver-Valiant like Conjectures
Date : October 25, 2006. (11:00 am) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Leonid Gurvits
Abstract:
The van der Waerden conjecture states that the permanent of n by n doubly stochastic matrix A satisfies the inequality Per(A) >= n! / n^n (VDW bound) and was finally proven (independently) by D.I. Falikman and G.P. Egorychev in 1981. Its worthy successor, the SCHRIJVER-VALIANT conjecture on the lower bound on the number of perfect matchings in k-regular bipartite graphs was posed in 1980 and resolved by A.Schrijver in 1998. The Schrijver's proof is one the most remarkable (and "highly complicated") results in the graph theory.
We introduce and prove a vast generalization of the VAN der WAERDEN conjecture as well SCHRIJVER-VALIANT conjecture. Our generalization not only affects the world of permanents, but also has important implications concerning PDEs, stability and control theory, complexity theory. Besides, our proof is much shorter and conceptually simpler than the original proofs; it proves VAN der WAERDEN / SCHRIJVER-VALIANT conjectures in "one shot". The main tool in our generalizations and proofs is a concept of hyperbolic polynomials. Hyperbolic polynomials were originally introduced and studied in the PDE theory. They are also closely related to the multivariate stable polynomials. VAN der WAERDEN / SCHRIJVER-VALIANT CONJECTURES correspond to the hyperbolic polynomials being products of linear forms. Our proof is relatively simple and "noncomputational"; it actually improves Schrijver's lower bound, provides a generalization for non-regular graphs, and uses very basic (more or less centered around Gauss-Lukas theorem ) properties of hyperbolic polynomials.
The theory is fairly straightly generalized to handle the number of partial matchings (joint work with S. Friedland). One of the applications results in the best estimate of the 3-dimensional monomer-dimer entropy.
Time permit, I will describe my recent result on analogues of VAN der WAERDEN / SCHRIJVER-VALIANT CONJECTURES for the mixed volume of compact convex sets. This generalization goes beyond hyperbolic polynomials and results in a randomized poly-time algorithm to approximate the mixed volumeof n convex compact subsets in R^n within a multiplicative factor e^n.
Bio:
[Back]
