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

Поиск точных пороговых вероятностей для различных свойств является одним из центральных направлений исследований в теории случайных графов и гиперграфов. Ярким представителем подобного класса задач является знаменитая проблема RANDOM k-SAT о выполнимости случайной булевой функции. Симметричный же вариант RANDOM k-SAT сводится к поиску пороговой вероятности для свойства наличия правильной раскраски в два цвета у случайного k-однородного гиперграфа. В докладе пойдет речь о естественном обобщении данной задачи, связанном с так называемыми дробными раскрасками гиперграфов. С помощью метода второго момента и решения ряда экстремальных задач для дважды стохастических матриц нам удалось получить очень точные оценки пороговой вероятности для свойства наличия дробной (4:2) раскраски в биномиальной модели случайного гиперграфа. Полученные результаты также показывают, что эта пороговая вероятность строго превышает пороговую вероятность для свойства правильной 2-раскрашиваемости. Доклад основан на совместной работе с П.А. Захаровым.