Combinatorial and algorithmic aspects of hyperbolic polynomials
| dc.creator | Gurvits, Leonid | |
| dc.date | 2004-04-27 | |
| dc.date | 2005-04-13 | |
| dc.date.accessioned | 2026-07-07T05:07:44Z | |
| dc.date.available | 2026-07-07T05:07:44Z | |
| dc.description | 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 . | |
| dc.description | 28 pages, extended and edited version . A proof of Conjecture 2.11 (hyperbolic van der Waerden conjecture) will be posted shortly | |
| dc.identifier | https://arxiv.org/abs/math/0404474 | |
| dc.identifier | http://arxiv.org/abs/math/0404474 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70977 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.title | Combinatorial and algorithmic aspects of hyperbolic polynomials | |
| dc.type | text |