Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

zbMATH Open1182.15008arXiv0711.3496MaRDI QIDQ1010786FDOQ1010786

Authors: Leonid Gurvits 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $p$ be a homogeneous polynomial of degree $n$ in $n$ variables, $p(z_1,\mathrm{...},z_n)=p(Z)$, $Zin{C}^n$. We call such a polynomial $p$ {�f H-Stable} if $p(z_1,\mathrm{...},z_n)eq0$ provided the real parts $Re(z_i)>0,1leqileqn$. This notion from {it Control Theory} is closely related to the notion of {it Hyperbolicity} used intensively in the {it PDE} theory. The main theorem in this paper states that if $p(x_1,\mathrm{...},x_n)$ is a homogeneous {�f H-Stable} polynomial of degree $n$ with nonnegative coefficients; $de{g}_p(i)$ is the maximum degree of the variable $x_i$, $C_i=min(de{g}_p(i),i)$ and ${\displaystyle }$ Cap(p) = inf_{x_i > 0, 1 leq i leq n} frac{p(x_1,...,x_n)}{x_1 ... x_n} ${\displaystyle }$ then the following inequality holds ${\displaystyle }$ frac{partial^n}{partial x_1... partial x_n} p(0,...,0) geq Cap(p) prod_{2 leq i leq n} (frac{C_i -1}{C_i})^{C_{i}-1}. ${\displaystyle }$ This inequality is a vast (and unifying) generalization of the Van der Waerden conjecture on the permanents of doubly stochastic matrices as well as the Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs. These two famous results correspond to the {�f H-Stable} polynomials which are products of linear forms. Our proof is relatively simple and ``noncomputational; it uses just very basic properties of complex numbers and the AM/GM inequality.

Full work available at URL: https://arxiv.org/abs/0711.3496

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• A generalization of permanent inequalities and applications in counting and optimization
• A generalization of permanent inequalities and applications in counting and optimization
• Proof of the Monotone Column Permanent Conjecture
• scientific article; zbMATH DE number 1336291

zbMATH Keywords

perfect matchingsdoubly stochastic matricesregular bipartite graphspermanentsvan der Waerden conjectureH-stable polynomialhomogemeous polynomialschrijver valiant conjecture

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Determinants, permanents, traces, other special matrix functions (15A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (45)

• Introduction to the combinatorial atlas
• Imaginary projections of polynomials
• A short survey on stable polynomials, orientations and matchings
• Random dense bipartite graphs and directed graphs with specified degrees
• An upper bound on the number of high-dimensional permutations
• Contractive determinantal representations of stable polynomials on a matrix polyball
• Determinant majorization and the work of Guo-Phong-Tong and Abja-Olive
• On the algebraic and topological structure of the set of Turán densities
• Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Stable multivariate Eulerian polynomials and generalized Stirling permutations
• The Halász–Székely barycenter
• Matchings in Benjamini-Schramm convergent graph sequences
• Factorially many maximum matchings close to the Erdős-Gallai bound
• Maximizing products of linear forms, and the permanent of positive semidefinite matrices
• Paving property for real stable polynomials and strongly Rayleigh processes
• Matchings in vertex-transitive bipartite graphs
• Gårding's theory of hyperbolic polynomials
• Proof of the Monotone Column Permanent Conjecture
• On the monotone column permanent conjecture
• Conic stability of polynomials
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Stable Noncommutative Polynomials and Their Determinantal Representations
• On the proportion of transverse-free plane curves
• Interactions of computational complexity theory and mathematics
• Stable and real-zero polynomials in two variables
• Statistical Matching Theory
• Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
• Solutions to two problems on permanents
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
• Central swaths
• An approximation algorithm for counting contingency tables
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• On the codimension of permanental varieties
• Multivariate stable polynomials: theory and applications
• Roots of Gårding hyperbolic polynomials
• Counting matchings via capacity-preserving operators
• On the numbers of 1-factors and 1-factorizations of hypergraphs
• Relative entropy optimization and its applications
• Lower bounds for contingency tables via Lorentzian polynomials
• Smooth hyperbolicity cones are spectrahedral shadows
• A generalization of permanent inequalities and applications in counting and optimization
• Concentration of the mixed discriminant of well-conditioned matrices
• Permanents of multidimensional matrices: properties and applications
• The minimum number of spanning trees in regular multigraphs

This page was built for publication: Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010786)