2005/04/19 by Leonid Gurvits, Gurvits, Leonid
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.math/0504397
15 pages, preliminary (still) version . A subsection on generalizations (with simpler proofs) of recent lower bounds by A.Schrijver for the number of perfect matchings of $k$-regular bipartite graphs
openalex publication_date 2005/04/19 · arxiv created 2005/08/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a homogeneous polynomial p(z1,...,zn) of degree n in n complex variables . Assume that this polynomial satisfies the property : |p(z1,...,zn)| ≥ ∏1 ≤ i ≤ n Re(zi) on the domain \(z1,...,zn) : Re(zi) ≥ 0, 1 ≤ i ≤ n \ . We prove that |(∂n)/(∂ z1...∂ zn) p | ≥ (n!)/(nn) . 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 × n nonnegative entry-wise matrices within multiplicative factor (en)/(nm) for any fixed positive m .