2000/12/20 by Michael Joswig, Joswig, Michael, Volker Kaibel +3
Mathematics · #05C99 #52B05 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG #msc:05C99 #msc:52B05
paper · pdf · doi:10.48550/arxiv.math/0012204
8 pages, 3 figures, LaTeX 2e
arxiv created 2001/06/27 · arxiv updated 2009/11/30
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.