Homogeneous multivariate polynomials with the half-plane property (Q1432999)

Let \(P\) be a polynomial in \(n\) complex variables. \(P\) is said to have the {half-plane property} or {Hurwitz property} if it is nonvanishing whenever all of its variables lie in the open right half-plane. When such a polynomial is homogeneous and multiaffine, it arises as the weighted generating function of some \(r\)-uniform set system. The paper is an extensive treatment of the question: When does a set system arise as the support of a homogeneous multiaffine polynomial having the half-plane property? A necessary condition is established that the set system be a matroid. However it is also shown that not all matroids have a basis generating polynomial that has the half-plane property. A number of interesting matroid classes are nonetheless shown to have the half-plane property, such as sixth-root-of-unity matroids, and certain classes of transversal matroids, among others. The class of matroids with the half-plane property is shown to be closed under a wide range of matroid operations. Establishing that a matroid class does have the half-plane property relies on numerous connections with constructions involving the determinant and the permanent. This paper serves to unify many different research directions, establishes some deep and surprisingly complex characterizations of matroids with the half-plane property, and poses a set of challenging open questions.