Permanents, matchings and van der Waerdens conjecture.

by Dr Amitava Bhattacharya (TIFR)

Thursday 8 Jul 2010, 16:00 → 17:00 Asia/Kolkata

AG-69 (Colaba Campus)

In 1926 van der Waerden conjectured that the minimum value of the permanent of a doubly stochastic matrix is $\frac {n!}{n^n}$. This was proved by Egorychev and Falikman in 1980. Their proofs used special case of Alexandorff-Fenchel inequalities. In this talk we will see an outline of a very simple proof using hyperbolic polynomials (due to Leonid Gurvits, 2008) and its applications in various graph matching counting problems. [This colloquium is meant for the VSRP students].