TY - JOUR

T1 - Homogeneous multivariate polynomials with the half-plane property

AU - Choe, Young Bin

AU - Oxley, James G.

AU - Sokal, Alan D.

AU - Wagner, David G.

N1 - Funding Information:
We thank Sankar Basu, Jason Brown, Jim Geelen, Russ Lyons, Richard Stanley, Dirk Vertigan, and Neil White for helpful comments and suggestions. We also thank James Renegar and Adam Strzebonski for correspondence concerning quantifier-elimination algorithms; Jürgen Bokowski, Andreas Dress, and Bernd Sturmfels for correspondence concerning determinants and Grassmann–Plücker identities; and Sankar Basu, Charles Desoer, and Paul Penfield for giving us pointers to the engineering literature (e.g., [23,58]). Finally, we thank Marc Noy and Dominic Welsh for organizing the Workshop on Tutte Polynomials and Related Topics (Barcelona, September 2001), at which this work was first presented. This research was supported in part by NSA grants MDA904-99-1-0030 and MDA904-01-1-0026 (J.G.O.), NSF grants PHY-9900769 and PHY-0099393 (A.D.S.), and an operating grant from NSERC (D.G.W.).

PY - 2004

Y1 - 2004

N2 - 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 PB(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.

AB - 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 PB(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.

UR - http://www.scopus.com/inward/record.url?scp=0346401580&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346401580&partnerID=8YFLogxK

U2 - 10.1016/S0196-8858(03)00078-2

DO - 10.1016/S0196-8858(03)00078-2

M3 - Article

AN - SCOPUS:0346401580

VL - 32

SP - 88

EP - 187

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

IS - 1-2

ER -