On k-level matroids: geometry and combinatorics
Francesco Grande · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · 2015
The Theta rank of a finite point configuration V is the maximal degree necessary for a sum-of-squares representation of a non-negative linear function on V . This is an important invariant for polynomial optimization that is in general hard to determine. We study the Theta rank of point configurations via levelness, that is a discrete-geometric invariant, and completely classify the 2-level (equivalently Theta-1) configurations whose convex hull is a simple or a simplicial polytope. We consider configurations associated to the collection of bases of matroids and show that the class of matroids with bounded Theta rank or levelness is closed under taking minors. This allows us to find a characterization of matroids with bounded Theta rank or levelness in terms of forbidden minors. We give the complete (finite) list of excluded minors for Theta-1 matroids which generalize the well-known series-parallel graphs. Moreover, we characterize the class of Theta-1 matroids in terms of the degree of generation of the vanishing ideal and in terms of the psd rank for the associated matroid base polytope. We analyze in full detail Theta-1 matroids from a constructive perspective and discover that they are sort-closed, which allows us to determine a unimodular triangulation of every matroid base polytope and to characterize its volume by means of permutations. A closed formula for the enumeration of Theta-1 matroids on a ground set of size n seems out of reach, but we exploit the constructive properties to provide asymptotic estimates. As a consequence, we obtain an exponential lower bound on the number of 2-level polytopes of any fixed dimension. As for the k-level matroids with k > 2, we prove that the list of excluded minors is finite for every k and we describe the excluded minors for k level graphs. We also investigate the excluded minors for graphs of Theta rank 2. For the case of hypersimplices, that is, matroid base polytopes of uniform matroids, we present results about the non-negative rank and the Gröbner fan together with conjectures about possible generalizations to the class of Theta-1 matroids.