On the k-Systems of a Simple Polytope
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
8 pages, 3 figures, LaTeX 2e
8 pages, 3 figures, LaTeX 2e