Complexity yardsticks for f-vectors of polytopes and spheres

DOI10.1007/S00454-019-00138-2zbMATH Open1456.52014arXiv1908.09628OpenAlexW2980197407WikidataQ127151159 ScholiaQ127151159MaRDI QIDQ2197688FDOQ2197688

Authors: Eran Nevo 

Publication date: 1 September 2020

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

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

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

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

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)

Cites Work

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

Cited In (4)

• Unimodality and log-concavity of \(f\)-vectors for cyclic and ordinary polytopes
• Embedding divisor and semi-prime testability in \(f\)-vectors of polytopes
• \(f\)-vectors of triangulated balls
• Title not available (Why is that?)

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)