Combinatorial and algorithmic aspects of hyperbolic polynomials

Details Combinatorial and algorithmic aspects of hyperbolic polynomials Combinatorial and algorithmic aspects of hyperbolic polynomials

2004-04-27

arxiv.org/abs/math/0404474v3

Mathematics

Combinatorics

28 pages, extended and edited version . A proof of Conjecture 2.11 (hyperbolic van der Waerden conjecture) will be posted shor

Scientific paper

Let $p(x_1,...,x_n) =\sum_{(r_1,...,r_n) \in I_{n,n}} a_{(r_1,...,r_n)} \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$ be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients. The support of such polynomial $p(x_1,...,x_n)$ is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 \}$ . The convex hull $CO(supp(p))$ of $supp(p)$ is called the Newton polytope of $p$ . We study the following decision problems, which are far-reaching generalizations of the classical perfect matching problem : {itemize} {\bf Problem 1 .} Consider a homogeneous polynomial $p(x_1,...,x_n)$ of degree $n$ in $n$ real variables with nonnegative integer coefficients given as a black box (oracle) . {\it Is it true that $(1,1,..,1) \in supp(p)$ ?} {\bf Problem 2 .} Consider a homogeneous polynomial $p(x_1,...,x_n)$ of degree $n$ in $n$ real variables with nonnegative integer coefficients given as a black box (oracle) . {\it Is it true that $(1,1,..,1) \in CO(supp(p))$ ?} {itemize} We prove that for hyperbolic polynomials these two problems are equivalent and can be solved by deterministic polynomial-time oracle algorithms . This result is based on a "hyperbolic" generalization of Rado theorem .

Affiliated with

Also associated with

No associations

Rating

Combinatorial and algorithmic aspects of hyperbolic polynomials 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 Combinatorial and algorithmic aspects of hyperbolic polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial and algorithmic aspects of hyperbolic polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-511224