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

Summary: 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,\dots,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}\frac {p(x_1,...,x_n)}{x_1 \dots x_n}\) then the following inequality holds \[ \frac{\partial^n}{\partial x_1...\partial x_n} p(0,\dots,0) \geq Cap(p) \Pi_{2 \leq i \leq n} \left(\frac{C_i-1}{C_i}\right)^{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.