Случайные гиперграфы и задачи экстремальной комбинаторики

Теория случайных графов и гиперграфов – это одна из наиболее активно развивающихся областей современной вероятностной комбинаторики. В докладе мы остановимся на классических моделях случайных графов, восходящих к работам П. Эрдеша и А. Реньи, а также на их естественных обобщениях – моделях случайных гиперграфов. Напомним одну из таких моделей.
Пусть $K_N^{(n)}$ – полный $n$-однородный гиперграф на $N$ вершинах (т.е. совокупность всех $n$-элементных подмножеств множества из $N$ элементов), тогда случайный гиперграф $H(N,n,p)$ есть подгиперграф $K_N^{(n)}$, полученный путем случайного включения ребер $K_N^{(n)}$: каждое ребро независимо от других включается в $H(N,n,p)$ с вероятностью $p$ и не включается с вероятностью $1-p$. Одним из наиболее важных открытий, сделанных Эрдешем и Реньи, является феномен пороговых вероятностей для многих теоретико-графовых свойств случайного графа. Эффект состоит в том, что с ростом параметра $p$ предельная вероятность обладания случайным графом (гиперграфом) некоторым свойством очень быстро «перескакивает» с 0 до 1 при переходе через эту пороговую вероятность.
В докладе будет рассказано об оценках пороговой вероятности для свойства случайного гиперграфа $H(N,n,p)$ быть $r$-раскрашиваемым. Данные оценки опираются на результаты экстремальной комбинаторики о достаточных условиях $r$-раскрашиваемости $n$-однородных гиперграфов, доказательства которых, в свою очередь, также основаны на применении вероятностной техники.