В статье представлен краткий обзор результатов о граничных комплексах выпуклых многогранников и их триангуляций. Он был бы вполне традиционен для комбинаторной теории выпуклых многогранников, если бы не главная тема статьи – связь этой теории с булевыми функциями. Эта связь вводится в п. 1, где выпуклому многограннику P ставится в соответствие булева функция φ_P , равная 0 на характеристических векторах граней P, и только на них. В п. 2 рассматриваются граничные комплексы ∂P симплициальных многогранников, для них функции φ_∂P монотонны. В п. 3 рассматриваются симплициальные комплексы (для них соответствующие булевы функции тоже монотонны) триангуляций выпуклых многогранников. Статья является расширенной версией доклада, прочитанного автором на 16-й международной школе-семинаре 'Синтез и сложность управляющих систем'.

Выпуклый многогранник, граничный комплекс, триангуляция, монотонные булевы функции

Математические вопросы и теория численных методов