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

\(CW\)-sphere\(f\)-vectorcomputational complexityflag \(f\)-vectorpolytope

Mathematics Subject Classification ID

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

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

Review text

The face numbers of simple polytopes are characterized by the \(g\)-theorem, conjectured by \textit{P. McMullen} [Isr. J. Math. 9, 559--570 (1971; Zbl 0209.53701)] and proved by \textit{R. P. Stanley} [Ann. N. Y. Acad. Sci. 440, 212--223 (1985; Zbl 0573.52008)] and by \textit{L. J. Billera} and \textit{C. W. Lee} [J. Comb. Theory, Ser. A 31, 237--255 (1981; Zbl 0479.52006)]. The related \(f\)-vectors and flag \(f\)-vectors of general \(d\)-polytopes and regular \(CW\) \((d-1)\)-spheres are not well understood, despite considerable efforts. In this note the author proposes approaching the qualitative differences between \(f\)-vectors and flag \(f\)-vectors of these classes by comparing their computational complexity, in terms of geometric and computational measures.

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; zbMATH DE number 5302815
• 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

• 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
• 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?)
• 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
• scientific article; zbMATH DE number 4100062 (Why is no real title available?)
• Embedding divisor and semi-prime testability in f-vectors of polytopes
• f-vectors of triangulated balls

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)