zbMATH — the first resource for mathematics

Four-dimensional polytopes of minimum positive semidefinite rank. (English) Zbl 1360.52006
Summary: The positive semidefinite (psd) rank of a polytope is the size of the smallest psd cone that admits an affine slice that projects linearly onto the polytope. The psd rank of a \(d\)-polytope is at least \(d + 1\), and when equality holds we say that the polytope is psd-minimal. In this paper we develop new tools for the study of psd-minimality and use them to give a complete classification of psd-minimal 4-polytopes. The main tools introduced are trinomial obstructions, a new algebraic obstruction for psd-minimality, and the slack ideal of a polytope, which encodes the space of realizations of a polytope up to projective equivalence. Our central result is that there are 31 combinatorial classes of psd-minimal 4-polytopes. We provide combinatorial information and an explicit psd-minimal realization in each class. For 11 of these classes, every polytope in them is psd-minimal, and these are precisely the combinatorial classes of the known projectively unique 4-polytopes. We give a complete characterization of psd-minimality in the remaining classes, encountering in the process counterexamples to some open conjectures.

52B11 \(n\)-dimensional polytopes
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
Full Text: DOI
[1] Briët, J.; Dadush, D.; Pokutta, S., On the existence of 0/1 polytopes with high semidefinite extension complexity, (Algorithms, ESA 2013, Lecture Notes in Computer Science, vol. 8125, (2013), Springer Berlin-Heidelberg), 217-228 · Zbl 1395.90241
[2] A. Bohn, Y. Faenza, S. Fiorini, V. Fisikopoulos, M. Macchia, K. Pashkovich, Enumeration of 2-level polytopes, preprint. · Zbl 1394.52008
[3] Bohn, A.; Faenza, Y.; Fiorini, S.; Fisikopoulos, V.; Macchia, M.; Pashkovich, K., Enumeration of 2-level polytopes, (Bansal, N.; Finocchi, I., Algorithms - ESA 2015: 23rd Annual European Symposium, Proceedings, Patras, Greece, September 14-16, 2015, (2015), Springer Berlin, Heidelberg), 191-202 · Zbl 1394.52008
[4] Beasley, L. B.; Klauck, H.; Lee, T.; Theis, D. O., Communication complexity, linear optimization, and lower bounds for the nonnegative rank of matrices, Dagstuhl Rep., 3, 2, 127-143, (2013)
[5] Boocher, A., Free resolutions and sparse determinantal ideals, Math. Res. Lett., 19, 4, 805-821, (2012) · Zbl 1273.14097
[6] Fawzi, H.; Gouveia, J.; Parrilo, P. A.; Robinson, R. Z.; Thomas, R. R., Positive semidefinite rank, Math. Program., 153, 1, Ser. B, 133-177, (2015) · Zbl 1327.90174
[7] Fawzi, H.; Parrilo, P. A., Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity, CoRR, (2013)
[8] Fawzi, H.; Saunderson, J.; Parrilo, P. A., Equivariant semidefinite lifts of regular polygons, Math. Oper. Res., (2016), in press · Zbl 1364.90245
[9] Gouveia, J.; Grappe, R.; Kaibel, V.; Pashkovich, K.; Robinson, R. Z.; Thomas, R. R., Which nonnegative matrices are slack matrices?, Linear Algebra Appl., 439, 10, 2921-2933, (2013) · Zbl 1283.15103
[10] Giusti, M.; Merle, M., Singularités isolées et sections planes de variétés déterminantielles. II. sections de variétés déterminantielles par LES plans de coordonnées, (Algebraic geometry, La Rábida, 1981, Lecture Notes in Math., vol. 961, (1982), Springer Berlin), 103-118 · Zbl 0509.14004
[11] Gouveia, J.; Parrilo, P. A.; Thomas, R. R., Theta bodies for polynomial ideals, SIAM J. Optim., 20, 4, 2097-2118, (2010) · Zbl 1213.90190
[12] Gouveia, J.; Parrilo, P. A.; Thomas, R. R., Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 2, 248-264, (2013) · Zbl 1291.90172
[13] Gouveia, J.; Robinson, R. Z.; Thomas, R. R., Polytopes of minimum positive semidefinite rank, Discrete Comput. Geom., 50, 3, 679-699, (2013) · Zbl 1279.52023
[14] Grünbaum, B., Convex polytopes, Graduate Texts in Mathematics, vol. 221, (2003), Springer New York
[15] Grande, F.; Sanyal, R., Theta rank, levelness, and matroid minors · Zbl 1354.05020
[16] Grayson, D. R.; Stillman, M. E., Macaulay2, a software system for research in algebraic geometry, Available at
[17] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1, 1-7, (1979) · Zbl 0395.94021
[18] Lee, J. R.; Raghavendra, P.; Steurer, D., Lower bounds on the size of semidefinite programming relaxations, CoRR, (2014)
[19] Lee, T.; Wei, Z., The square root rank of the correlation polytope is exponential, CoRR, (2014)
[20] Lee, T.; Wei, Z.; de Wolf, R., Some upper and lower bounds on psd-rank, CoRR, (2014)
[21] McMullen, P., Constructions for projectively unique polytopes, Discrete Math., 14, 4, 347-358, (1976) · Zbl 0319.52010
[22] Stein, W. A., Sage mathematics software (version 5.11), (2015)
[23] Sturmfels, B., Gröbner bases and convex polytopes, University Lecture Series, vol. 8, (1996), American Mathematical Society Providence, RI · Zbl 0856.13020
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.