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».

Convex polyhedron boundary complex, triangulation, monotone Boolean functions

Mathematical problems and theory of numerical methods