Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : Sharper Bounds, Simpler Proofs and Algorithmic Applications

Let $p(x_1,\mathrm{.}\mathrm{.}\mathrm{.},x_n)=p(X),X\in R^n$ be a homogeneous polynomial of degree $n$ in $n$ real variables, $e=(1,1,\mathrm{.}\mathrm{.},1)\in R^n$ be a vector of all ones . Such polynomial $p$ is called $e$-hyperbolic if for all real vectors $X \in R^{n}$theunivariatepolynomialequation$P(te - X) = 0$ has all real roots ${\lambda }_1(X)\ge \mathrm{.}\mathrm{.}\mathrm{.}\ge {\lambda }_n(X)$ . The number of nonzero roots $\mathrm{\mid }\{i:{\lambda }_i(X)\mathrm{\ne }0\}\mathrm{\mid }$ is called $Ran{k}_p(X)$ . A $e$-hyperbolic polynomial $p$ is called $POS$-hyperbolic if roots of vectors $X \in R^{n}{+}$withnonnegativecoordinatesarealsononnegative(theorthant$R^{n}{+}$belongstothehyperboliccone)and$p(e) > 0$\mathrm{.}Below${e_1,…,e_n}$standsforthecanonicalorthogonalbasisin$R^{n}$. The main results states that if $p(x_1,x_2,\mathrm{.}\mathrm{.}\mathrm{.},x_n)$ is a $POS$-hyperbolic (homogeneous) polynomial of degree $n$, $Ran{k}_p(e_i)=R_i$ and $ p(x_1,x_2,…,x_n) \geq \prod_{1 \leq i \leq n} x_i ; x_i > 0, 1 \leq i \leq n , $thenthefollowinginequalityholds$$ \frac{\partial^n}{\partial x_1…\partial x_n} p(0,…,0) \geq \prod_{1 \leq i \leq n} (\frac{G_{i} -1}{G_{i}})^{G_{i} -1} (G_i = \min(R_{i}, n+1-i)) . $$ This theorem is a vast (and unifying) generalization of as the van der Waerden conjecture on the permanents of doubly stochastic matrices as well Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs . The paper is (almost) self-contained, most of the proofs can be found in the {\bf Appendices}.