Аннотация:
Поиск точных пороговых вероятностей для различных свойств является одним из центральных направлений исследований в вероятностной комбинаторике, и, в частности, в теории случайных графов и гиперграфов, первые результаты подобного рода были получены еще Эрдешем и Реньи на рубеже 50-60-х годов прошлого века. Одной из наиболее известных подобных задач является проблема RANDOM k-SAT о выполнимости случайной булевой функции, активное изучение которой началось около 30 лет назад. Симметричный вариант RANDOM k-SAT сводится к поиску пороговой вероятности для свойства наличия правильной раскраски случайного k-однородного гиперграфа в два цвета, сильные оценки которой были получены в 2011 году Койя-Огланом и Панайоту. В докладе пойдет речь о естественных обобщениях данной задачи, связанных с так называемыми дробными раскрасками гиперграфов. Будут представлены результаты докладчика с соавторами, в которых также удалось получить очень точные оценки для соответствующих пороговых вероятностей.
|
