Theta rank, levelness, and matroid minors. (English) Zbl 1354.05020

Summary: 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.


05B35 Combinatorial aspects of matroids and geometric lattices
05C83 Graph minors


Full Text: DOI arXiv


[1] Ardila, Federico; Klivans, Caroline J., The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B, 96, 1, 38-49 (2006) · Zbl 1082.05021
[2] Brylawski, Thomas H., A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc., 154, 1-22 (1971) · Zbl 0215.33702
[3] Chaourar, Brahim; Oxley, James, On series-parallel extensions of uniform matroids, European J. Combin., 24, 7, 877-879 (2003) · Zbl 1026.05022
[4] Diestel, Reinhard, Graph Decompositions. A Study in Infinite Graph Theory, Oxford Science Publications (1990), Oxford University Press: Oxford University Press New York · Zbl 0726.05001
[5] Dirac, Gabriel A., Minimally 2-connected graphs, J. Reine Angew. Math., 228, 204-216 (1967) · Zbl 0153.25804
[6] Edmonds, Jack, Submodular functions, matroids, and certain polyhedra, (Combinatorial Structures and Their Applications. Proc. Calgary Internat. Conf.. Combinatorial Structures and Their Applications. Proc. Calgary Internat. Conf., Calgary, Alta., 1969 (1970), Gordon and Breach: Gordon and Breach New York), 69-87 · Zbl 0268.05019
[7] Feichtner, Eva Maria; Sturmfels, Bernd, Matroid polytopes, nested sets and Bergman fans, Port. Math. (N. S.), 62, 4, 437-468 (2005) · Zbl 1092.52006
[8] Gouveia, João; Laurent, Monique; Parrilo, Pablo A.; Thomas, Rekha, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Math. Program., 133, 1-2, Ser. A, 203-225 (2012), MR 2921097 · Zbl 1262.90123
[9] Gouveia, João; Parrilo, Pablo A.; Thomas, Rekha R., Theta bodies for polynomial ideals, SIAM J. Optim., 20, 4, 2097-2118 (2010) · Zbl 1213.90190
[10] Gouveia, João; Parrilo, Pablo A.; Thomas, Rekha R., Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 2, 248-264 (2013) · Zbl 1291.90172
[11] Gouveia, João; Robinson, Richard Z.; Thomas, Rekha R., Polytopes of minimum positive semidefinite rank, Discrete Comput. Geom., 50, 3, 679-699 (2013) · Zbl 1279.52023
[12] Grayson, Daniel R.; Stillman, Michael E., Macaulay2, a software system for research in algebraic geometry, available at
[13] Kim, Sangwook, Flag enumerations of matroid base polytopes, J. Combin. Theory Ser. A, 117, 7, 928-942 (2010) · Zbl 1228.05112
[14] McMullen, Peter, Constructions for projectively unique polytopes, Discrete Math., 14, 4, 347-358 (1976) · Zbl 0319.52010
[15] Oxley, James G., The regular matroids with no 5-wheel minor, J. Combin. Theory Ser. B, 46, 3, 292-305 (1989) · Zbl 0626.05009
[16] Oxley, James G., Matroid Theory, Oxf. Grad. Texts Math., vol. 21 (2011), Oxford University Press: Oxford University Press Oxford · Zbl 1254.05002
[17] Plummer, Michael D., On minimal blocks, Trans. Amer. Math. Soc., 134, 85-94 (1968) · Zbl 0187.21101
[18] Robertson, Neil; Seymour, Paul D., Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, 92, 2, 325-357 (2004) · Zbl 1061.05088
[19] Sanyal, Raman; Werner, Axel; Ziegler, Günter M., On Kalai’s conjectures concerning centrally symmetric polytopes, Discrete Comput. Geom., 41, 2, 183-198 (2009) · Zbl 1168.52013
[20] Schrijver, Alexander, Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms Combin., vol. 24 (2003), Springer-Verlag: Springer-Verlag Berlin · Zbl 1041.90001
[21] Sullivant, Seth, Compressed polytopes and statistical disclosure limitation, Tohoku Math. J. (2), 58, 3, 433-445 (2006) · Zbl 1121.52028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.