Article collection "Mathematical Problems of Cybernetics" ¹16, Moscow, 2007

Authors:Shevchenko V.N.

Triangulations of convex polyhedra and their Boolean functions

Abstract:

In the paper a short overview of results concerning boundary complexes of convex polyhedra and its triangulations is given. The overview would be quite traditional unless the main theme of the paper, the connection between this theory and Boolean functions.
This connection is introduced in Section 1, where a convex polyhedron P is related to a Boolean function φ_{P} that equales to 0 on the characteristic vectors of the faces of P and only on them. In Section 2 boundary complexes ∂P of simplicial polyhedra are considered; their functions φ_{∂P} are monotonous. In Section 3 we consider simplicial complexes (the corresponding Boolean functions are monotonous too) of triangulations of convex polyhedra. Since functions φ_{P} and φ_{∂P} have different realizations, different problems connected with economical representation of Boolean functions arise. Besides, they give us a new vision of some problems studying in the theory of linear inequalities such as realizability of f-vectors (the i-th components of the f-vectors is the number of the i-dimensional faces) of polytopes and its triangulations.
The paper is the extended version of the talk given by the author in the 16-th international school-seminar «Synthesis and complexity of control systems».