A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

Details A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

2005-04-19

arxiv.org/abs/math/0504397v3

Mathematics

Combinatorics

15 pages, preliminary (still) version . A subsection on generalizations (with simpler proofs) of recent lower bounds by A.Schr

Scientific paper

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables . Assume that this polynomial satisfies the property : \\ $|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0, 1 \leq i \leq n \}$ . \\ We prove that $|\frac{\partial^n}{\partial z_1...\partial z_n} p | \geq \frac{n!}{n^n}$ . Our proof is relatively short and self-contained (i.e. we only use basic properties of hyperbolic polynomials). As the van der Waerden conjecture for permanents, proved by D.I. Falikman and G.P. Egorychev, as well Bapat's conjecture for mixed discriminants, proved by the author, are particular cases of this result. We also prove so called "small rank" lower bound (in the permanents context it corresponds to sparse doubly-stochastic matrices, i.e. with small number of non-zero entries in each column). The later lower bound generalizes (with simpler proofs) recent lower bounds by A.Schrijver for the number of perfect matchings of $k$-regular bipartite graphs. We present some important algorithmic applications of the result, including a polynomial time deterministic algorithm approximating the permanent of $n \times n$ nonnegative entry-wise matrices within multiplicative factor $\frac{e^n}{n^m}$ for any fixed positive $m$ .

Affiliated with

Also associated with

No associations

Rating

A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification 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 A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-516337