Master Thesis - Representing matroids by polynomials with the half-plane property

R. S. González D'León

Kungliga Tekniska Högskolan, May 2009.
Advisor P. Brändén
MATLAB code

Abstract:

A matroid \(\MM\) is said to have the weak half-plane property (wHPP) if there exists a stable multiaffine homogeneous complex polynomial \(f\) with support equal to the set of bases of \(\MM\). This is a generalization of the half-plane property (HPP), where we require that all the coefficients of \(f\) are equal to zero or one. Both properties were recently treated by Choe, Oxley, Sokal and Wagner in \cite{choe-2004-32}. In \cite{branden-2006}, Br"{a}nd'{e}n proved that not every matroid is wHPP by showing that the Fano matroid \(F_7\) is not. We provide two new proofs of the fact that \(F_7\) is not a wHPP-matroid. We investigate and state conditions for when wHPP=HPP for \(\MM\). We use concepts and techniques developed for the Tutte-group of a matroid and valuated matroids by Dress, Wenzel and Murota to prove that the projective geometry matroids \(PG(r-1,q)\) are not wHPP and that a binary matroid is a wHPP-matroid if and only if it is regular. This shows that there exist large families of matroids that are not wHPP. We answer questions posed by Choe et al., by proving that the coextensions \(AG(3,2)\) and \(S_8\) of \(F_7\), and the matroids \(T_8\) and \(R_9\), are not wHPP, extending the answer given by \cite{branden-2006}.