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

Abstract

Let $p(x_1,...,x_n)=p(X),X\in R^n$ be a homogeneous polynomial of degree $n$ in $n$ real variables, $e=(1,1,..,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$ the univariate polynomial equation $P(te-X)=0$ has all real roots ${\lambda }_1(X)\ge ...\ge {\lambda }_n(X)$ . The number of nonzero roots $|\{i:{\lambda }_i(X)\ne 0\}|$ is called $Ran{k}_p(X)$ . A $e$-hyperbolic polynomial $p$ is called $POS$-hyperbolic if roots of vectors $X\in R_{+}^n$ with nonnegative coordinates are also nonnegative (the orthant $R_{+}^n$ belongs to the hyperbolic cone) and $p(e)>0$ . Below $\{e_1,...,e_n\}$ stands for the canonical orthogonal basis in $R^n$. The main results states that if $p(x_1,x_2,...,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)\ge {\prod }_{1\le i\le n}{x}_i;x_i>0,1\le i\le n,$ then the following inequality holds $$\frac{{\partial }^n}{\partial x_1...\partial x_n}p(0,...,0)\ge \prod _{1\le i\le 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}.

21 pages, some typos are corrected . Section 2.2 is added . This section sketches the extension of the main result to the volume polynomials . This extension leads to a randomized poly-time algorithm to approximate the mixed volume of n compact convex sets in R^n within multiplicative factor e^n

References in corpus (1)

• Combinatorial and algorithmic aspects of hyperbolic polynomials

Cited by in corpus (2)

• Capacity Lower Bounds via Productization
• Capacity of Lorentzian polynomials and distance to binomial distributions