Ученые нашли решение столетней математической теории Рамсея

Теория Рамсея сводится к поиску скрытой организации в графах — совокупностях точек, соединенных линиями. Теория утверждает, что если граф достаточно велик, то он будет содержать определенный вид порядка — либо группу точек, полностью соединенных линиями (клика), либо группу без связей. r (s, t) представляет собой минимальный размер графа, необходимый для обеспечения такой клики, причем s — это количество соединенных точек, а t — количество несвязанных. Самая известная задача Рамсея, r (3,3) гласит, что в компании из шести человек всегда найдется не менее трех общих друзей или незнакомцев. Решить r (3,3) было все равно что найти первое домино — математики жаждали получить ответы на r (4,4), r (5,5) и так далее. Решение для r (4,4) было найдено в 1930-х годах, но r (5,5) остается загадкой.

Что же делает эти, казалось бы, простые задачи такими сложными? Количество возможных графов растет по мере увеличения числа точек (и потенциальных связей). Для r (5,5) с предполагаемым решением между 40−50 точками необходимо рассмотреть более 10 триллионов графов. В таких случаях математики часто прибегают к оценкам.

Именно здесь на помощь приходит команда Калифорнийского университета в Сан-Диего. Жак Верстрате и Сэм Маттеус занялись r (4,t) — проблемой, которая интересовала Верстрате еще со студенческих времен. Ключом к их подходу стали «псевдослучайные графы» — техника, позволяющая получить более точные оценки, чем традиционные случайные графы.

Предыдущий успех псевдослучайных графов в решении r (3,t) в 2019 году подкрепил их решимость. Однако задача r (4,t) оказалась более сложной. Верстрате вышел за рамки своей обычной области комбинаторики, обратившись к конечной геометрии, алгебре и вероятности. Это сотрудничество с экспертом по конечной геометрии Сэмом Маттеусом оказалось плодотворным.

После нескольких лет упорных усилий они нашли ответ: r (4,t) — близкая к кубической функция от t. Проще говоря, для гарантированной группы из четырех общих друзей или t незнакомцев на вечеринке вам понадобится примерно t³ человек. Это не точный ответ, но очень близкая оценка.

Результаты исследования находятся на стадии анализа, но Верстрате полон решимости «добить» эту задачу.