Four-dimensional polytopes of minimum positive semidefinite rank

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:145

Article

Gouveia, Joao¹  Pashkovich, Kanstanstin²  Robinson, Richard Z.³  Thomas, Rekha R.³ 

[1] Univ Coimbra, Dept Math, CMUC, P-3001454 Coimbra, Portugal

[2] Univ Waterloo, Dept Combinator & Optimizat, 200 Univ Ave W, Waterloo, ON N2L 3G1, Canada

[3] Univ Washington, Dept Math, Box 354350, Seattle, WA 98195 USA

关键词: Polytopes;    Positive semidefinite rank;    psd-minimal;    Slack matrix;    Slack ideal;   

DOI  :  10.1016/j.jcta.2016.08.002

来源: Elsevier

【 摘 要 】

The positive semidefinite (psd) rank of a polytope is the size of the smallest psd cone that admits an aifine 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-rninimal 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. (C) 2016 Elsevier Inc. All rights reserved.

【 授权许可】

Free