Complex psd-minimal polytopes in dimensions two and three

DOI10.1142/S0219498824500257MaRDI QIDQ6089230zbMATH OpenOpenAlexFDO

Authors Tristram Bogart, João Gouveia, Juan Camilo Torres

Publication date 14 December 2023

Published in Journal of Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

3-polytopecomplex positive semidefinite (psd) minimalityextension complexitypolygonsemidefinite liftsslack idealslack matrix

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Factorization of matrices (15A23) Three-dimensional polytopes (52B10) Computational aspects related to convexity (52B55) Nonnumerical algorithms (68W05)

Abstract: The extension complexity of a polytope measures its amenability to succinct representations via lifts. There are several versions of extension complexity, including linear, real semidefinite, and complex semidefinite. We focus on the last of these, for which the least is known, and in particular on understanding which polytopes are complex psd-minimal. We prove the existence of an obstruction to complex psd-minimality which is efficiently computable via lattice membership problems. Using this tool, we complete the classification of complex psd-minimal polygons (geometrically as well as combinatorially). In dimension three we exhibit several new examples of complex psd-minimal polytopes and apply our obstruction to rule out many others.

Recommendations

• Extension complexity of polytopes with few vertices or facets
• Four-dimensional polytopes of minimum positive semidefinite rank
• Extension complexity of low-dimensional polytopes
• Maximum semidefinite and linear extension complexity of families of polytopes
• Polytopes of minimum positive semidefinite rank

Cites work

• An information complexity approach to extended formulations
• Common information and unique disjointness
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Extension complexity of polytopes with few vertices or facets
• Fast generation of planar graphs
• Four-dimensional polytopes of minimum positive semidefinite rank
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Lifts of Convex Sets and Cone Factorizations
• Lower bounds on the size of semidefinite programming relaxations
• On ranks of regular polygons
• On the finding of final polynomials
• Polytopes of minimum positive semidefinite rank
• Positive semidefinite rank
• Projectively unique polytopes and toric slack ideals
• Self-dual spherical grids
• Some upper and lower bounds on PSD-rank
• The phaseless rank of a matrix
• Which nonnegative matrices are slack matrices?

This page was built for publication: Complex psd-minimal polytopes in dimensions two and three

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089230)