On the \(k\)-systems of a simple polytope (Q1601467): Difference between revisions

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.