On the k-systems of a simple polytope

DOI10.1007/BF02773157MaRDI QIDQ1601467zbMATH OpenWikidataFDO

Authors Michael Joswig, Volker Kaibel, Friederike Körner

Publication date 4 April 2003

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

abstract objective functionalgorithmic complexityedge graphsimple polytope

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A k-system of the graph G(P) of a simple polytope P is a set of induced subgraphs of G(P) that shares certain properties with the set of subgraphs induced by the k-faces of P. This new concept leads to polynomial-size certificates in terms of G(P) for both the set of vertex sets of facets as well as for abstract objective functions (AOF) in the sense of Kalai. Moreover, it is proved that an acyclic orientation yields an AOF if and only if it induces a unique sink on every 2-face.

Review text

It is known that the combinatorial type of a simple polytope is determined by the isomorphism type of its edge graph \(G\) [\textit{R. Blind} and \textit{P. Mani-Levitska}, Aequationes Math. 34, 287-297 (1987; Zbl 0634.52005)]. Algorithms exist which perform this determination, however, the best known algorithms are exponential in the size of \(G\). The reader is referred to the work of \textit{G. Kalai} [J. Comb. Theory, Ser. A 49, 381-383 (1988; Zbl 0673.05087)]. The article under review examines subproblems relating specifically to Kalai's algorithm, with a view to finding polynomial-time solutions to them. The work is done in terms of \(k\)-systems. A \(k\)-system of \(P\) is a set of sets of vertices of \(P\) satisfying certain properties given in the article. An example is the set of vertex sets of the \(k\)-faces of \(P\), but other examples exist. The article should be useful to anyone concerned to find efficient algorithms to characterize simple polytopes from their edge graphs.

Recommendations

• Finding a simple polytope from its graph in polynomial time
• scientific article; zbMATH DE number 1953195
• A simple way to tell a simple polytope from its graph
• scientific article; zbMATH DE number 1538125
• Combinatorial face enumeration in convex polytopes

Cites work

• A simple way to tell a simple polytope from its graph
• Examples and counterexamples for the Perles conjecture
• From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
• scientific article; zbMATH DE number 1538125 (Why is no real title available?)
• Lectures on Polytopes
• Maximum matching and a polyhedron with 0,1-vertices
• Paths, Trees, and Flowers
• Puzzles and polytope isomorphisms
• Realization spaces of polytopes

Cited in

(10)

• Finding a simple polytope from its graph in polynomial time
• On the reconstruction of polytopes
• Long monotone paths on simple 4-polytopes
• scientific article; zbMATH DE number 1538125 (Why is no real title available?)
• On the Monotone Upper Bound Problem
• Efficient edge-skeleton computation for polytopes defined by oracles
• Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra
• Subword complexes and Kalai's conjecture on reconstruction of spheres
• Graphs, skeleta and reconstruction of polytopes
• On double-\(k\)-systems of spheres

This page was built for publication: On the \(k\)-systems of a simple polytope

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