Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials : One Theorem for all

Abstract

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)\ne 0$ provided the real parts $Re(z_i)>0,1\le i\le 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; $de{g}_p(i)$ is the maximum degree of the variable $x_i$, $C_i=\min (de{g}_p(i),i)$ and $$Cap(p)=\underset{x_i>0,1\le i\le n}{\inf }\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)\ge Cap(p)\prod _{2\le i\le 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.

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

References in corpus (3)

• Combinatorial and algorithmic aspects of hyperbolic polynomials
• A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification
• Van der Waerden Conjecture for Mixed Discriminants