Complexity yardsticks for f-vectors of polytopes and spheres

DOI10.1007/S00454-019-00138-2MaRDI QIDQ2197688zbMATH OpenOpenAlexWikidataFDO

Authors Eran Nevo

Publication date 1 September 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitypolytope\(f\)-vectorflag \(f\)-vector\(CW\)-sphere

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Polytopes and polyhedra (52Bxx) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Abstract: We consider geometric and computational measures of complexity for sets of integer vectors, asking for a qualitative difference between $f$-vectors of simplicial and general $d$-polytopes, as well as flag $f$-vectors of $d$-polytopes and regular CW $(d-1)$-spheres, for $dge4$.

Recommendations

• A geometric lower bound on the extension complexity of polytopes based on the f-vector
• On the combinatorial complexity of approximating polytopes
• On the combinatorial complexity of approximating polytopes
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• scientific article
• scientific article; zbMATH DE number 3876926
• scientific article; zbMATH DE number 20626
• A comparison theorem for \(f\)-vectors of simplicial polytopes
• Extension complexity of polytopes with few vertices or facets
• On the complexity of computing the diameter of a polytope

Cites work

• scientific article; zbMATH DE number 66626 (Why is no real title available?)
• scientific article; zbMATH DE number 2008526 (Why is no real title available?)
• scientific article; zbMATH DE number 2068109 (Why is no real title available?)
• scientific article; zbMATH DE number 1789919 (Why is no real title available?)
• A generalized lower‐bound conjecture for simplicial polytopes
• A new basis of polytopes
• A proof of the lower bound conjecture for convex polytopes
• A proof of the sufficiency of McMullen's conditions for f-vectors of simplicial convex polytopes
• Combinatorics and commutative algebra.
• Flag \(f\)-vectors and the \(cd\)-index
• Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets
• Monotonicity of the cd-index for polytopes
• NP-complete decision problems for binary quadratics
• On the generalized lower bound conjecture for polytopes and spheres
• Projected products of polygons
• Rigidity and the lower bound theorem. I
• Semi-algebraic sets of \(f\)-vectors
• Squarefree \( P\)-modules and the \({\mathbf {cd}}\)-index
• The cd-index of fans and posets
• The extended f-vectors of 4-polytopes
• The flag f-vectors of Gorenstein^ order complexes of dimension 3
• The number of faces of a simplicial convex polytope
• The numbers of faces of simplicial polytopes

Cited in

(4)

• Unimodality and log-concavity of \(f\)-vectors for cyclic and ordinary polytopes
• \(f\)-vectors of triangulated balls
• Embedding divisor and semi-prime testability in \(f\)-vectors of polytopes
• scientific article; zbMATH DE number 4100062 (Why is no real title available?)

This page was built for publication: Complexity yardsticks for \(f\)-vectors of polytopes and spheres

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