On k-level matroids: geometry and combinatorics

Abstract

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.

Der Theta-Rang einer endlichen Punktkonfiguration V ist der maximal benötigte Grad, um eine beliebige, nicht-negative, lineare Funktion auf V als Summe von Quadraten darzustellen. Diese Zahl ist eine wichtige Invariante für Probleme der polynomiellen Optimierung und ist im Allgemeinen schwer zu bestimmen. Wir untersuchen den Theta-Rang einer Punktkonfiguration mittels levelness, einer Invariante aus der diskreten Geometrie, und klassifizieren die 2-level (d.h. Theta-1) Konfigurationen deren konvexe Hülle ein simples oder simpliziales Polytop ist. Wir betrachten Konfigurationen, die man aus der Familie von Basen eines Matroids erhält und zeigen, dass die Klasse von Matroiden mit beschränktem Theta-Rang beziehungsweise levelness abgeschlossen bezüglich Minoren ist. Dies gestattet es, Matroide mit beschränktem Theta-Rang oder beschränkter levelness durch verbotene Minoren zu charakterisieren. Die vollständige (endliche) Liste ausgeschlossener Minoren wird für Theta-1 Matroide angegeben, die den Fall von series-parallel graphs verallgemeinern. Zudem lässt sich die Klasse der Theta-1 Matroide über den degree of generation des Verschwindungs-Ideals sowie über den psd-Rang des assozierten Matroidenbasispolytops bestimmen. Theta-1 Matroide sind sort-closed. Dies gestattet es, unimodulare Triangulierungen des Matroidpolytops zu finden und sein Volumen mittels Permutationen zu charakterisieren. Asymptotische Schranken für die Anzahl an Theta-1 Matroiden auf einer Grundmenge mit fester Größe werden gefunden. Somit gelingt es auch, eine exponentielle untere Schranke an die Anzahl von 2-level polytopes einer beliebigen aber festen Dimension anzugeben. Es wird bewiesen, dass k-level Matroide für k > 2 sich durch nur endlich viele ausgeschlossene Minoren beschreiben lassen. Zudem wird eine Charakterisierung von k-level graphs durch verbotene Minoren angegeben und die verbotenen Minoren für Graphen von Theta-Rang 2 untersucht. Der nicht- negative Rang und Gröbnerfächer von Hypersimplizes – also Matroidbasispolytopen von uniformen Matroiden – werden vollständig beschrieben. Vermutungen über mögliche Verallgemeinerungen auf Theta-1 Matroide werden präsentiert.