Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials : One Theorem for all
| dc.creator | Gurvits, Leonid | |
| dc.date | 2007-11-22 | |
| dc.date | 2008-05-13 | |
| dc.date.accessioned | 2026-07-07T09:38:29Z | |
| dc.date.available | 2026-07-07T09:38:29Z | |
| dc.description | Let $p$ be a homogeneous polynomial of degree $n$ in $n$ variables, $p(z_1,...,z_n) = p(Z)$, $Z \in C^{n}$. We call such a polynomial $p$ {\bf H-Stable} if $p(z_1,...,z_n) \neq 0$ provided the real parts $Re(z_i) > 0, 1 \leq i \leq n$. This notion from {\it Control Theory} is closely related to the notion of {\it Hyperbolicity} used intensively in the {\it PDE} theory. The main theorem in this paper states that if $p(x_1,...,x_n)$ is a homogeneous {\bf H-Stable} polynomial of degree $n$ with nonnegative coefficients; $deg_{p}(i)$ is the maximum degree of the variable $x_i$, $C_i = \min(deg_{p}(i),i)$ and $$ Cap(p) = \inf_{x_i > 0, 1 \leq i \leq n} \frac{p(x_1,...,x_n)}{x_1 ... x_n} $$ then the following inequality holds $$ \frac{\partial^n}{\partial x_1... \partial x_n} p(0,...,0) \geq Cap(p) \prod_{2 \leq i \leq n} (\frac{C_i -1}{C_i})^{C_{i}-1}. $$ This inequality is a vast (and unifying) generalization of the Van der Waerden conjecture on the permanents of doubly stochastic matrices as well as the Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs. These two famous results correspond to the {\bf H-Stable} polynomials which are products of linear forms. Our proof is relatively simple and ``noncomputational''; it uses just very basic properties of complex numbers and the AM/GM inequality. | |
| dc.description | A slightly corrected (a few typos fixed) version of EJC paper. This version is self-contained and elementary. Written as a Lecture Notes, can be used in an undergraduate/graduate combinatorics course | |
| dc.identifier | https://arxiv.org/abs/0711.3496 | |
| dc.identifier | http://arxiv.org/abs/0711.3496 | |
| dc.identifier | The Electronic Journal of Combinatorics, 2008 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160824 | |
| dc.subject | Combinatorics | |
| dc.subject | Algebraic Geometry | |
| dc.title | Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials : One Theorem for all | |
| dc.type | text |