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

Первая часть доклада будет посвящена задаче об изучении предельной концентрации значений хроматического числа случайного гиперграфа в биномиальной модели $H(n,k,p).$ Мы покажем, что при фиксированном $k\ge3$ и не слишком быстро растущем значении $n^{k-1}p$ хроматическое число $H(n,k,p)$ с вероятностью, стремящейся к 1, принадлежит множеству из некоторых двух соседних значений. Кроме того, при чуть более сильных ограничениях на рост $n^{k-1}p$ данные значения можно отыскать явным образом, как функции от $n$ и $p.$ Результаты были получены в совместных работах с Д.А. Шабановым.
Вторая часть доклада будет посвящена задаче об отыскании асимптотического поведения клико-хроматического числа случайного графа Эрдеша-Реньи. Клико-хроматическое число графа — это наименьшее число цветов, требуемое для раскраски множества вершин графа таким образом, что ни одна максимальная по включению клика в нем не будет одноцветной. К. МакДиармид, Д. Митше и П. Пралат доказали, что клико-хроматическое число биномиального случайного графа $G(n,1/2)$ не превосходит $(1/2+o(1))\log_2(n)$ с асимптотической вероятностью 1. Н. Алон и М. Кривелевич установили, что оно хотя бы $(1/2000+o(1))\log_2(n)$ с асимптотической вероятностью 1. В совместной работе с М.Е. Жуковским нам удалось показать, что верхняя оценка асимптотически точна.
Идентификатор конференции: 942 0186 5629 Код доступа-шестизначное число, первые три цифры которого образуют число p+44, а последние три цифры-число q+63, где p,q-наибольшая пара близнецов, меньших 1000.