Theta rank, levelness, and matroid minors

详细信息    查看全文

• 作者：Francesco Grande^a ; ^{fgrande@math.fu-berlin.de} ; Raman Sanyal^b ; ^{sanyal@math.uni-frankfurt.de}
• 关键词：Sum-of-squares ; Theta rank ; Levelness ; Matroid base configurations ; Excluded minor characterization
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：123
• 期：Complete
• 页码：1-31
• 全文大小：639 K
• 卷排序：123

文摘

The Theta rank of a finite point configuration V is the maximal degree necessary for a sum-of-squares representation of a non-negative affine function on V. This is an important invariant for polynomial optimization that is in general hard to determine. We study the Theta rank and levelness, a related discrete-geometric invariant, for matroid base configurations. It is shown that the class of matroids with bounded Theta rank or levelness is closed under taking minors. This allows for 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 generalizes the well-known series-parallel graphs. Moreover, the class of Theta-1 matroids can be characterized 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 further give a finite list of excluded minors for k-level graphs and matroids and we investigate the graphs of Theta rank 2.