Polytopes of minimum positive semidefinite rank

DOI10.1007/s00454-013-9533-xzbMath1279.52023arXiv1205.5306MaRDI 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

polytope; cone lift; Hadamard square roots; positive semidefinite rank; slack matrix

Mathematics Subject Classification ID

52B11: (n)-dimensional polytopes

52C45: Combinatorial complexity of geometric structures

Related Items

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

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