Polytopes of minimum positive semidefinite rank

DOI10.1007/s00454-013-9533-xzbMath1279.52023arXiv1205.5306OpenAlexW2071242430MaRDI QIDQ377501

João Gouveia, Rekha R. Thomas, Richard Z. Robinson

Publication date: 6 November 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.5306

zbMATH Keywords

polytopecone liftHadamard square rootspositive semidefinite rankslack matrix

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Combinatorial complexity of geometric structures (52C45)

Related Items

Extended formulations for convex heptagons, Rank functions of tropical matrices, Lifting for Simplicity: Concise Descriptions of Convex Sets, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Bounds on the number of 2-level polytopes, cones, and configurations, Deciding Polyhedrality of Spectrahedra, Complex psd-minimal polytopes in dimensions two and three, On Ranks of Regular Polygons, Positive semidefinite rank and nested spectrahedra, Lifts of non-compact convex sets and cone factorizations, Enumeration of 2-level polytopes, Theta rank, levelness, and matroid minors, Extension complexity and realization spaces of hypersimplices, Four-dimensional polytopes of minimum positive semidefinite rank, The Phaseless Rank of a Matrix, Rational and real positive semidefinite rank can be different, Two Results on the Size of Spectrahedral Descriptions, Lower bounds on nonnegative rank via nonnegative nuclear norms, Tropical lower bounds for extended formulations, Positive semidefinite rank, Worst-case results for positive semidefinite rank, Projectively unique polytopes and toric slack ideals, On Vertices and Facets of Combinatorial 2-Level Polytopes, Two-Level Polytopes with a Prescribed Facet, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Tropical lower bound for extended formulations. II. Deficiency graphs of matrices, An upper bound for nonnegative rank

Uses Software

• Macaulay2

Cites Work

• Unnamed Item
• Extended formulations for polygons
• Smallest compact formulation for the permutahedron
• The strong perfect graph theorem
• Expressing combinatorial optimization problems by linear programs
• Geometric algorithms and combinatorial optimization.
• On the geometric interpretation of the nonnegative rank
• Combinatorial bounds on nonnegative rank and extended formulations
• Constructing Extended Formulations from Reflection Relations
• Theta Bodies for Polynomial Ideals
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Convex Polytopes
• Lifts of Convex Sets and Cone Factorizations
• Linear vs. semidefinite extended formulations