Рандомизированные алгоритмы раскрасок гиперграфов

В работе исследуются обобщения классической задачи П. Эрдёша о свойстве $B$ гиперграфов. Согласно определению Эрдёша гиперграф обладает свойством $B$, если существует двухцветная раскраска множества его вершин, в которой ни одно ребро гиперграфа не является одноцветным. Требуется найти величину $m(n)$, равную минимально возможному количеству ребер в $n$-равномерном (каждое ребро содержит ровно $n$ вершин) гиперграфе, не обладающем свойством $B$. Рассматриваются более общие постановки проблемы, приводится ряд параметрических свойств гиперграфов и соответствующих им экстремальных величин. Основные результаты улучшают ранее известные нижние оценки этих экстремальных величин.
Библиография: 9 названий.