Search

Abstract: There has recently been ample interest in the question of which sets can be represented by linear matrix inequalities (LMIs). A necessary condition is that the set is rigidly convex, and it has been conjectured that rigid convexity is also sufficient. To this end Helton and Vinnikov conjectured that any real zero polynomial admits a determinantal representation with symmetric matrices. We disprove this conjecture. By relating the question of finding LMI representations to the problem of determining whether a polymatroid is representable over the complex numbers, we find a real zero polynomial such that no power of it admits a determinantal representation. The proof uses recent results of Wagner and Wei on matroids with the half-plane property, and the polymatroids associated to hyperbolic polynomials introduced by Gurvits. [Copyright &y& Elsevier]

Murota et al. have recently developed a theory of discrete convex analysis which concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over a field of generalized Puiseux series) with prescribed non-vanishing properties. This family contains several of the most well studied M-concave functions in the literature. In the language of tropical geometry, we study the tropicalization of the space of polynomials with the half-plane property and show that it is strictly contained in the space of M-concave functions. We also provide a short proof of Speyer's "hive theorem" which he used to give a new proof of Horn's conjecture on eigenvalues of sums of Hermitian matrices. [ABSTRACT FROM AUTHOR]

Abstract: A multivariate polynomial is stable if it is non-vanishing whenever all variables have positive imaginary parts. A matroid has the weak half-plane property (WHPP) if there exists a stable polynomial with support equal to the set of bases of the matroid. If the polynomial can be chosen with all of its non-zero coefficients equal to one then the matroid has the half-plane property (HPP). We describe a systematic method that allows us to reduce the WHPP to the HPP for large families of matroids. This method makes use of the Tutte group of a matroid. We prove that no projective geometry has the WHPP and that a binary matroid has the WHPP if and only if it is regular. We also prove that and fail to have the WHPP. [Copyright &y& Elsevier]

Abstract: Murota et al. have recently developed a theory of discrete convex analysis as a framework to solve combinatorial optimization problems using ideas from continuous optimization. This theory concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over the field of Puiseux series) with prescribed non-vanishing properties. We also provide a short proof of Speyer''s “hive theorem” which he used to give a new proof of Horn''s conjecture on eigenvalues of sums of Hermitian matrices. Due to limited space a more coherent treatment and proofs will appear elsewhere. [Copyright &y& Elsevier]

Abstract: A polynomial f is said to have the half-plane property if there is an open half-plane , whose boundary contains the origin, such that f is non-zero whenever all the variables are in H. This paper answers several open questions relating multivariate polynomials with the half-plane property to matroid theory. [(1)] We prove that the support of a multivariate polynomial with the half-plane property is a jump system. This answers an open question posed by Choe, Oxley, Sokal and Wagner and generalizes their recent result claiming that the same is true whenever the polynomial is also homogeneous. [(2)] We prove that a multivariate multi-affine polynomial has the half-plane property (with respect to the upper half-plane) if and only if for all and . This is used to answer two open questions posed by Choe and Wagner regarding strongly Rayleigh matroids. [(3)] We prove that the Fano matroid is not the support of a polynomial with the half-plane property. This is the first instance of a matroid which does not appear as the support of a polynomial with the half-plane property and answers a question posed by Choe et al. We also discuss further directions and open problems. [Copyright &y& Elsevier]