Homogeneous multivariate polynomials with the half-plane property

Abstract

A polynomial P in n complex variables is said to have the "half-plane property" (or Hurwitz property) if it is nonvanishing whenever all the variables lie in the open right half-plane. Such polynomials arise in combinatorics, reliability theory, electrical circuit theory and statistical mechanics. A particularly important case is when the polynomial is homogeneous and multiaffine: then it is the (weighted) generating polynomial of an r-uniform set system. We prove that the support (set of nonzero coefficients) of a homogeneous multiaffine polynomial with the half-plane property is necessarily the set of bases of a matroid. Conversely, we ask: For which matroids M does the basis generating polynomial P_{B(M)} have the half-plane property? Not all matroids have the half-plane property, but we find large classes that do: all sixth-root-of-unity matroids, and a subclass of transversal (or cotransversal) matroids that we call "nice". Furthermore, the class of matroids with the half-plane property is closed under minors, duality, direct sums, 2-sums, series and parallel connection, full-rank matroid union, and some special cases of principal truncation, principal extension, principal cotruncation and principal coextension. Our positive results depend on two distinct (and apparently unrelated) methods for constructing polynomials with the half-plane property: a determinant construction (exploiting "energy" arguments), and a permanent construction (exploiting the Heilmann-Lieb theorem on matching polynomials). We conclude with a list of open questions.

LaTeX2e, 111 pages. Submission includes Mathematica programs niceprincipal.m and nicetransversal.m Version 2 corrects a small error at the beginning of Appendix B, and makes a few small improvements elsewhere. To appear in Advances in Applied Mathematics

References in corpus (1)

• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions

Cited by in corpus (32)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Polynomials with the half-plane property and matroid theory
• Obstructions to determinantal representability
• The Lee-Yang and Pólya-Schur Programs. I. Linear Operators Preserving Stability
• A Little Statistical Mechanics for the Graph Theorist
• The Lee-Yang and Pólya-Schur Programs. II. Theory of Stable Polynomials and Applications
• On the roots of all-terminal reliability polynomials
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Nonequilibrium stationary states and equilibrium models with long range interactions
• Hyperbolic polynomials, interlacers, and sums of squares
• Representing some non-representable matroids
• Real Fibered Morphisms and Ulrich Sheaves
• Polynomial-sized Semidefinite Representations of Derivative Relaxations of Spectrahedral Cones
• Introduction to the combinatorial atlas
• The separating semigroup of a real curve
• The Chow form of a reciprocal linear space
• A Note on the Hyperbolicity Cone of the Specialized Vámos Polynomial
• Spectral linear matrix inequalities
• A generalization of the Heine--Stieltjes theorem
• Multivariate Eulerian polynomials and exclusion processes
• On the half-plane property and the Tutte group of a matroid
• Discrete concavity and the half-plane property
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• Lee-Yang Problems and The Geometry of Multivariate Polynomials
• Positive Ulrich Sheaves
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• On complete classes of valuated matroids
• Matroids on Eight Elements with the Half-plane Property and Related Concepts
• Quantum states supported by matroids
• A converse to the Grace--Walsh--Szegő theorem
• Three results related to the half-plane property of matroids
• Matroids arising from electrical networks