Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Leonid Gurvits

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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 a such polynomial $p$ 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 Control Theory is closely related to the notion of Hyperbolicity used intensively in the PDE theory. The main theorem in this paper states that if $p(x_1,...,x_n)$ is a homogeneous 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} {p(x_1,...,x_n)\over x_1 \cdots x_n}$ then the following inequality holds $${\partial^n\over\partial x_1...\partial x_n} p(0,...,0) \geq Cap(p) \prod_{2 \leq i \leq n} \bigg({C_i-1\over C_i}\bigg)^{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 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.

Détail

DOI : 10.37236/790

Classification : 15A15, 05A15, 05C70
Mots-clés : homogemeous polynomial, H-stable polynomial, van der Waerden conjecture, permanents, doubly stochastic matrices, schrijver valiant conjecture, perfect matchings, regular bipartite graphs