Polygons as sections of higher-dimensional polytopes

zbMATH Open1312.52008arXiv1404.2443MaRDI QIDQ2256121FDOQ2256121

Authors: Arnau Padrol, Julian Pfeifle 

Publication date: 19 February 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We show that every heptagon is a section of a $3$-polytope with $6$ vertices. This implies that every $n$-gon with $ngeq7$ can be obtained as a section of a $(2+lfloorfracn7floor)$-dimensional polytope with at most $lceilfrac6n7ceil$ vertices; and provides a geometric proof of the fact that every nonnegative $nimesm$ matrix of rank $3$ has nonnegative rank not larger than $lceilfrac6min(n,m)7ceil$. This result has been independently proved, algebraically, by Shitov (J. Combin. Theory Ser. A 122, 2014).

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• An upper bound for nonnegative rank
• On ranks of regular polygons
• Extended formulations for convex heptagons
• Extended formulations for polygons
• Hidden vertices in extensions of polytopes

zbMATH Keywords

extension complexitynonnegative rankpolygonnonrealizabilitypseudo-line arrangementspolytope projecions and section

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Factorization of matrices (15A23) Polytopes and polyhedra (52B99)

Cites Work

• Real rank versus nonnegative rank
• Expressing combinatorial optimization problems by linear programs
• An upper bound for nonnegative rank
• On Polyhedral Approximations of the Second-Order Cone
• Extended formulations for polygons
• Detecting matrices of combinatorial rank three
• Lifts of Convex Sets and Cone Factorizations
• Worst-case results for positive semidefinite rank
• Stochastic factorizations, sandwiched simplices and the topology of the space of explanations

Cited In (9)

• Euclidean distance matrices and separations in communication complexity theory
• Heuristics for exact nonnegative matrix factorization
• Extension complexity of low-dimensional polytopes
• Hidden vertices in extensions of polytopes
• Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
• The best ways to slice a polytope
• Extension complexity and realization spaces of hypersimplices
• Extension complexity of polytopes with few vertices or facets
• A separation between tropical matrix ranks

This page was built for publication: Polygons as sections of higher-dimensional polytopes

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