О тупиковых комплексах граней в единичном кубе

Изучение свойств тупиковых комплексов граней связано с задачей минимизации булевых функций в классе дизъюнктивных нормальных форм (д.н.ф.). В работах С. В. Яблонского, Ю. И. Журавлева, В. В. Глаголева, Ю. Л. Васильева, А. А. Сапоженко на основе построения и исследования свойств конкретных булевых функций были получены оценки максимальных значений длины и числа тупиковых д.н.ф.
Автором был предложен другой подход, основанный на построении и оценивании мощности множеств тупиковых комплексов граней. В данной статье, с использованием вероятностного подхода, усовершенствованы методы построения и оценивания характеристик тупиковых комплексов граней, что позволило улучшить известные ранее оценки. На основе метода построения тупиковых комплексов граней в поясе единичного куба $B^n$ ширины $k$ получены оценки максимального числа граней и числа тупиковых комплексов для граней размерности $k<(1/4-\varepsilon)n$, где $\varepsilon$ – сколь угодно малая положительная постоянная. За счет оптимального выбора параметров для логарифма числа тупиковых комплексов граней получена нижняя оценка порядка $n2^n$ с константой $1,355\cdot2^{-5}$ при размерности граней $k\approx0,0526n$.
В силу эквивалентности задачи минимизации булевых функций в классе д.н.ф. и задачи построения комплексов граней, покрывающих подмножества вершин единичного куба, полученные результаты справедливы для оценки максимальных значений длины и числа тупиковых д.н.ф.