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

Одна из наиболее известных задач вероятностной комбинаторики - это знаменитая проблема RANDOM k-SAT о выполнимости случайной булевой функции. Случайная булева функция представляет собой конъюнкцию из m случайных дизъюнкций, каждая из которых в свою очередь состоит из k случайно выбранных литералов среди n переменных или их отрицаний. Оказывается, что предельная вероятность выполнимости такой функции с ростом n и фиксированном k почти всегда равна либо нулю, либо единице в зависимости от числа дизъюнкций m=m(n). В настоящее время известно, что если m не превосходит a(k)n, то вероятность выполнимости стремится к единице, а если m больше чем b(k)n, то к нулю, причем разность b(k)-a(k) является экспоненциально быстро стремящейся к нулю функцией от k.

В докладе пойдет речь о естественном обобщении задачи RANDOM k-SAT, связанном с полноцветными раскрасками гиперграфов. Здесь с помощью метода второго момента нам удалось получить очень точные оценки пороговой вероятности наличия полноцветной раскраски в заданное число цветов у случайного гиперграфа.