Об одном фазовом переходе в теории Рамсея

Теория Рамсея – это классический раздел комбинаторики, активно изучающийся как в России, так и за рубежом. Задачи, связанные с её количественными аспектами (т.е. асимптотическим поведением возникающих здесь функций) обычно оказываются очень трудными и далеки от своего окончательного решения. К числу таких задач относится поставленная Эрдёшом и Хайналом в 1972 г. проблема о наличии “фазового перехода” в определённых ситуациях. Проблема Эрдёша–Хайнала зависит от двух параметров $k$ и $s$ и ранее ответ был известен лишь для $k=3$ и лишь для небольшого числа значений $s$.
В совместной работе Д. Мубаи и А. Разборова задача полностью решена для всех $k\geq 4$ и произвольного $s$. Методы доказательства включают как традиционные для экстремальной комбинаторики (в том числе теорию алгебр флагов), так и специально введённые для этой цели. Из числа новых идей стоит отметить рассмотрение комбинаторных объектов с некоторыми свойствами типа универсальности или жёсткости, а также рассмотрение интерпретаций соответствующих теорий в теории гиперграфов.