The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

AGA

Seminar

Hyperbolic polynomials and lower bounds in combinatorics

Gurvits, L (Los Alamos)
Friday 16 February 2007, 11:30-12:30

Seminar Room 1, Newton Institute

Abstract

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.

Audio

MP3MP3

Back to top ∧