|
СЕМИНАРЫ |
|
Некоторые задачи о раскрасках случайных графов и гиперграфов Ю. А. Демидович Московский физико-технический институт (национальный исследовательский университет), Московская облаcть, г. Долгопрудный |
|||
Аннотация: Первая часть доклада будет посвящена задаче об изучении предельной концентрации значений хроматического числа случайного гиперграфа в биномиальной модели Вторая часть доклада будет посвящена задаче об отыскании асимптотического поведения клико-хроматического числа случайного графа Эрдеша-Реньи. Клико-хроматическое число графа — это наименьшее число цветов, требуемое для раскраски множества вершин графа таким образом, что ни одна максимальная по включению клика в нем не будет одноцветной. К. МакДиармид, Д. Митше и П. Пралат доказали, что клико-хроматическое число биномиального случайного графа Идентификатор конференции: 942 0186 5629 Код доступа-шестизначное число, первые три цифры которого образуют число p+44, а последние три цифры-число q+63, где p,q-наибольшая пара близнецов, меньших 1000. Website: https://mi-ras-ru.zoom.us/j/94201865629?pwd=aUlIbFBFelhFTjhnUnZtdTNFL1IvZz09 |