Isaac Newton Institute for Mathematical Sciences

Hyperbolic Polynomials and lower bounds in combinatorics

16th February 2007

Author: Leonid Girvits (Los Alamos )


The Van der Waerden conjecture states that the permanent of an nxn doubly stochastic matrix A satisfies the inequality Per(A) >= n! / n^n (VDW bound). It had been for many years the most important conjecture about permanents, till it was finally proven independently by D.I. Falikman and by G.P.Egorychev in 1981. The VDW bound is the simplest and most powerful bound on permanents and therefore is among the most useful general purpose bounds in combinatorics. Its worthy successor , the Erdos-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 describe the proof of a vast algebraic generalization of both Van der Waerden and Schrijver-Valiant conjectures. Besides being much more general, 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 is the concept of hyperbolic polynomials, which were originally introduced and studied in PDEs. In this language, Van der Waerden and Schrijver-Valiant Conjectures correspond to the case of hyperbolic polynomials that are products of linear forms. Our proof is relatively simple and "noncomputational"; it in fact slightly improves the Schrijver's lower bound, and uses only basic properties of hyperbolic polynomials .

Time permitting, I will talk about non-hyperbolic results, such as analogues of Van der Waerden/Schrijver-Valiant conjectures for mixed volumes on convex sets.