On Leonid Gurvits’s Proof for Van der Waerden Conjecture

by Uma Girish (Chennai Mathematical Institute, Chennai)

Friday 5 May 2017, 17:15 → 18:45 Asia/Kolkata

A-201 (STCS Seminar Room)

The Van der Waerden Conjecture states that the permanent of a doubly stochastic matrix n x n matrix is at least n!/n^n, which is the case when each entry of the matrix is $1/n$. Though this conjecture is simple to state, it was unsolved for over fifty years until it was proved by Falikman (1979) and Egorychev (1980). In 2008, Leonid Gurvits came up with an amazingly short proof of the Van der Waerden Conjecture using H-stable polynomials. This proof will be the primary focus of this talk. The proof is self-contained, and we will follow the exposition by Laurent and Schrijver.