A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification
| dc.creator | Gurvits, Leonid | |
| dc.date | 2005-04-19 | |
| dc.date | 2005-08-15 | |
| dc.date.accessioned | 2026-07-07T05:19:15Z | |
| dc.date.available | 2026-07-07T05:19:15Z | |
| dc.description | 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) recent lower bounds by A.Schrijver for the number of perfect matchings of $k$-regular bipartite graphs. We present some important algorithmic applications of the result, including a polynomial time deterministic algorithm approximating the permanent of $n \times n$ nonnegative entry-wise matrices within multiplicative factor $\frac{e^n}{n^m}$ for any fixed positive $m$ . | |
| dc.description | 15 pages, preliminary (still) version . A subsection on generalizations (with simpler proofs) of recent lower bounds by A.Schrijver for the number of perfect matchings of $k$-regular bipartite graphs | |
| dc.identifier | https://arxiv.org/abs/math/0504397 | |
| dc.identifier | http://arxiv.org/abs/math/0504397 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/74950 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.title | A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification | |
| dc.type | text |