An Algorithm for Testing the Half-plane Property of Matroids

Büşra Sert

13 January 2023 17:00

Abstract

For each hyperbolic polynomial $h$, there is an associated closed convex cone called the hyperbolicity cone of $h$. A convex cone is called spectrahedral if it can be described by linear matrix inequalities. Spectrahedral cones can be described as hyperbolicity cones of some hyperbolic polynomials. Whether the other direction is true, however, is an open question. This is the question the generalized Lax conjecture considers and posits.

Choe et al. in 2004 showed that the support of every homogeneous multiaffine polynomial with the half-plane property (such a polynomial is hyperbolic) is the collection of bases of some matroid $M$. In search of potential counter-examples, this connection made finding matroids with the half-plane property of new interest. For example, Brändén used the structure of matroids to produce counter-examples for a stronger version of the conjecture.

In this talk, we present an algorithm for testing the half-plane property of matroids. The tests are performed by checking some criteria on the Rayleigh differences of the basis generating polynomials, given by Brändén and Wagner-Wei, using the packages SumsOfSquares'', Matroids’’ for Macaulay2, and the Julia package ``Homotopy Continuation.jl’’. Using this algorithm, we give a complete classification of matroids on at most $8$ elements with respect to the half-plane property, and provide our test results on matroids on $9$ elements.