KIAM Main page Web Library  •  Publication Searh   
Publication

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.
Keywords:
Convex polyhedron boundary complex, triangulation, monotone Boolean functions
Publication language: russian, pages: 14 (p. 43-56)
Research direction:
Mathematical problems and theory of numerical methods
Source text: