zbMATH — the first resource for mathematics

Polytopes of minimum positive semidefinite rank. (English) Zbl 1279.52023
Summary: The positive semidefinite (psd) rank of a polytope is the smallest \(k\) for which the cone of \(k\times k\) real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, and we characterize those polytopes whose psd rank equals this lower bound. We give several classes of polytopes that achieve the minimum possible psd rank including a complete characterization in dimensions two and three.

52C45 Combinatorial complexity of geometric structures
52B11 \(n\)-dimensional polytopes
Full Text: DOI arXiv
[1] Chudnovsky, M; Robertson, N; Seymour, P; Thomas, R, The strong perfect graph theorem, Ann. Math., 164, 51-229, (2006) · Zbl 1112.05042
[2] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties and Algorithms. Springer, New York (1992)
[3] Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of STOC, New York (2012) · Zbl 1286.90125
[4] Fiorini, S; Rothvoss, T; Tiwary, HR, Extended formulations for polygons, Discrete Comput. Geom., 48, 658-668, (2012) · Zbl 1290.68122
[5] Fiorini, S; Kaibel, V; Pashkovich, K; Theis, DO, Combinatorial bounds on nonnegative rank and extended formulations, Discret. Math., 313, 67-83, (2013) · Zbl 1259.90111
[6] Gillis, N; Glineur, F, On the geometric interpretation of the nonnegative rank, Linear Algebra Appl., 437, 2685-2712, (2012) · Zbl 1258.65039
[7] Goemans, M.: Smallest compact formulation of the permutahedron. Math. Program. B (to appear) · Zbl 1322.90048
[8] Gouveia, J; Parrilo, PA; Thomas, RR, Theta bodies for polynomial ideals, SIAM J. Optim., 20, 2097-2118, (2010) · Zbl 1213.90190
[9] Gouveia, J; Parrilo, PA; Thomas, RR, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 248-264, (2013) · Zbl 1291.90172
[10] Grayson, D.R., Stillman, M.E.: Macaulay 2, a software system for research in algebraic geometry. http://www.math.uiuc.edu/Macaulay2/
[11] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, 2nd edn. Springer, Berlin (1993) · Zbl 0837.05001
[12] Grünbaum, B.: Convex Polytopes, 2nd edn. Springer, New York (2003) · Zbl 1024.52001
[13] Kaibel, V; Pashkovich, K; Günlük, O (ed.); Woeginger, GJ (ed.), Constructing extended formulations from reflection relations, 287-300, (2011), Berlin · Zbl 1341.90148
[14] Lovász, L, On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1-7, (1979) · Zbl 0395.94021
[15] Lovász, L; Schrijver, A, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190, (1991) · Zbl 0754.90039
[16] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · Zbl 0748.90074
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.