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

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

2005-10-21

arxiv.org/abs/math/0510452v3

Mathematics

Combinatorics

21 pages, some typos are corrected . Section 2.2 is added . This section sketches the extension of the main result to the volu

Scientific paper

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) \geq ... \geq \lambda_{n}(X)$ . The number of nonzero roots $|\{i :\lambda_{i}(X) \neq 0 \}|$ is called $Rank_{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$, $Rank_{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 , $ then the following inequality holds $$ \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}.

Affiliated with

Also associated with

No associations

Rating

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : Sharper Bounds, Simpler Proofs and Algorithmic Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : Sharper Bounds, Simpler Proofs and Algorithmic Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : Sharper Bounds, Simpler Proofs and Algorithmic Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-89503