Computer Science/Discrete Mathematics Seminar III

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. It was for more than XX years the most important conjecture about permanents. The VDW bound is the simplest and most powerful bound on permanents and therefore among the simplest and most powerful general purpose bounds in combinatorics. 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 least understood) results in the graph theory . We introduce and prove a vast generalization of as 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. 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 slightly improves Schrijver's lower bound, and uses very basic (more or less centered around Rolle's theorem) properties of hyperbolic polynomials . The paper with the proof is available at http://lanl.arxiv.org/abs/math.CO/0504397, see also the paper at http://xxx.lanl.gov/abs/math.CO/0404474.