ECCC-Report TR05-103https://eccc.weizmann.ac.il/report/2005/103Comments and Revisions published for TR05-103en-usTue, 20 Sep 2005 19:46:14 +0300
Paper TR05-103
| A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification |
Leonid Gurvits
https://eccc.weizmann.ac.il/report/2005/103Consider 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 .
Tue, 20 Sep 2005 19:46:14 +0300https://eccc.weizmann.ac.il/report/2005/103