Thursday, February 16th, 2012 | 4pm-5pm | McConnell 103 |

CNRS, Paris / Charles University, Prague

Gurvits's proof of the van der Waerden Conjecture

The van der Waerden Conjecture about permanents of doubly stochastic matrices was stated in 1926, and proved in 1981 by Egorychev and, independently, Falikman. In 2008, Gurvits found a simple, beautiful and elementary proof of both this conjecture and an extension of a theorem of Schrijver (whose original proof is most complicated).

The goal of the talk is to convey the main ideas used by Gurvits. After a presentation of van der Waerden's Conjecture and its links with other problems, I will introduce the ideas used by Gurvits, state his theorem and derive from it the two aforementioned results. Last, we shall formally prove the theorem, as much as time permits.