On ranks of regular polygons

DOI10.1137/16M1105608zbMATH Open1384.52004arXiv1610.09868MaRDI QIDQ4594484FDOQ4594484

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)

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.

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

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

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)

Cites Work

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

Cited In (12)

• A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
• Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
• Title not available (Why is that?)
• 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
• 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)