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

MaRDI QIDQ1010786zbMATH OpenFDO

Authors Leonid Gurvits

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0711.3496, https://eudml.org/doc/117248, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r66.html

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

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)

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.

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

Cited in

(45)

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

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)