__
TR05-103 | 17th August 2005 00:00
__

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

**Abstract:**
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 .