Polygons as sections of higher-dimensional polytopes

MaRDI QIDQ2256121zbMATHFDO

Authors Arnau Padrol, Julian Pfeifle

Publication date 19 February 2015

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

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

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

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)

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).

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

Cites work

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

Cited in

(11)

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

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)