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

Boolean ranknonnegative rankpolygonssemidefinite 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

• 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
• scientific article; zbMATH DE number 4031722 (Why is no real title available?)
• Lifts of Convex Sets and Cone Factorizations
• Lower bounds on the size of semidefinite programming relaxations
• Non-projectability of polytope skeleta
• On a unimodal sequence of binomial coefficients
• On Polyhedral Approximations of the Second-Order Cone
• 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)

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

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)