scientific article; zbMATH DE number 1241854

MaRDI QIDQ4225317zbMATH OpenFDO

Authors Günter M. Ziegler

Publication date 18 January 1999

zbMATH Keywords

convex polytopessurvey

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02) (n)-dimensional polytopes (52B11) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

This is a discussion of five very active and important areas of research on the (combinatorial) theory of (convex) polytopes, with reports about recent progress, and a selection of seven ``challenge problems that I hope to see solved soon: Universality theorems: for polytopes of constant dimensions: see Richter-Gebert's work! \textit{Challenge}: Can all three-dimensional polytopes be realized with coordinates of polynomial size? \textit{Challenge}: Provide a universality theorem for simplicial four-dimensional polytopes. Triangulations: and subdivisions of polytopes. \textit{Challenge}: Decide whether all triangulations on a fixed point set in general position can be connected by bistellar flips. 0/1-polytopes: and their combinatorial structure. \textit{Challenge}: The ``0/1 upper bound problem: Is the maximal number of facets of 0/1-polytopes bounded by an exponential function in the dimension? Neighborly polytopes: Explicit constructions and extremal properties. \textit{Challenge}: Is every polytope a quotient of a neighborly polytope? Monotone paths: and the simplex algorithm for linear programming. \textit{Challenge}: The ``Monotone upper bound problem: What is the maximal number of vertices of a monotone path on a \(d\)-dimensional polytope with \(n\) facets? \textit{Challenge}: Is there a polynomial upper bound for the running time of the random-edge simplex algorithm? For the entire collection see [Zbl 0902.00037].

Recommendations

• Long monotone paths on simple 4-polytopes
• scientific article; zbMATH DE number 665700
• On the Monotone Upper Bound Problem
• 0/1-Polytopes. Typical and extremal properties

Cited in

(10)

• The polytope of all triangulations of a point configuration
• Long monotone paths on simple 4-polytopes
• Normal polytopes: between discrete, continuous, and random
• scientific article; zbMATH DE number 3828714 (Why is no real title available?)
• scientific article; zbMATH DE number 1993723 (Why is no real title available?)
• scientific article; zbMATH DE number 1538125 (Why is no real title available?)
• On the Monotone Upper Bound Problem
• A point set whose space of triangulations is disconnected
• From singularities to polyhedral products
• On the genera of moment-angle manifolds associated with dual-neighborly polytopes: combinatorial formulas and sequences

This page was built for publication:

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