Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-103 | 17th August 2005 00:00

A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification


Authors: Leonid Gurvits
Publication: 20th September 2005 19:46
Downloads: 3874


Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables .
Assume that this polynomial satisfies the property : \\

$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$ . \\

We prove that $|\frac{\partial^n}{\partial z_1...\partial z_n} p | \geq \frac{n!}{n^n}$ . \\
Our proof is relatively short and self-contained (i.e. we only use basic
properties of hyperbolic polynomials ). \\
As the van der Waerden conjecture for permanents , proved by D.I. Falikman and G.P. Egorychev ,
as well Bapat's conjecture for mixed discriminants , proved by the author ,
are particular cases of this result. \\
We also prove so called "small rank" lower bound (in the permanents context it corresponds to
sparse doubly-stochastic matrices , i.e. with small number of non-zero entries in each column).
The later lower bound generalizes (with simpler proofs and slightly better bound) recent bound by A.Schrijver on the
number of perfect matchings in $k$-regular bipartite graphs.\\
Some important algorithmic applications are presented in the last section .

ISSN 1433-8092 | Imprint