On ranks of regular polygons

DOI10.1137/16M1105608MaRDI QIDQ4594484zbMATH OpenFDO

Authors António Pedro Goucha, João Gouveia, Pedro M. Silva

Publication date 24 November 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

polygonsnonnegative rankBoolean ranksemidefinite rank

Mathematics Subject Classification ID

Factorization of matrices (15A23) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Abstract: In this paper we study various versions of extension complexity for polygons through the study of factorization ranks of their slack matrices. In particular, we develop a new asymptotic lower bound for their nonnegative rank, shortening the gap between the current bounds, we introduce a new upper bound for their boolean rank, deriving from it some new numerical results, and we study their complex semidefinite rank, uncovering the possibility of non monotonicity of the ranks of regular $n$-gons.

Recommendations

• On the linear extension complexity of regular \(n\)-gons
• Extended formulations for polygons
• A geometric lower bound on the extension complexity of polytopes based on the f-vector
• An upper bound for nonnegative rank
• Polygons as sections of higher-dimensional polytopes

Cites work

• scientific article; zbMATH DE number 4031722 (Why is no real title available?)
• An upper bound for nonnegative rank
• Constructing extended formulations from reflection relations
• Exponential lower bounds for polytopes in combinatorial optimization
• Extended formulations for polygons
• Four-dimensional polytopes of minimum positive semidefinite rank
• Heuristics for exact nonnegative matrix factorization
• Lifts of Convex Sets and Cone Factorizations
• Lower bounds on the size of semidefinite programming relaxations
• Non-projectability of polytope skeleta
• On Polyhedral Approximations of the Second-Order Cone
• On a unimodal sequence of binomial coefficients
• On the geometric interpretation of the nonnegative rank
• On the linear extension complexity of regular \(n\)-gons
• Polytopes of minimum positive semidefinite rank
• The maximum numbers of faces of a convex polytope
• Which nonnegative matrices are slack matrices?
• Worst-case results for positive semidefinite rank

Cited in

(12)

• A geometric lower bound on the extension complexity of polytopes based on the f-vector
• scientific article; zbMATH DE number 6686868 (Why is no real title available?)
• Algorithms for positive semidefinite factorization
• Extended formulations for polygons
• The phaseless rank of a matrix
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• On the linear extension complexity of regular \(n\)-gons
• Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
• An upper bound for nonnegative rank
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Complex psd-minimal polytopes in dimensions two and three
• Polygons as sections of higher-dimensional polytopes

This page was built for publication: On ranks of regular polygons

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