Теории Рамсея — математическая задача, которая ставит математиков в тупик (хоть прогресс и есть) уже почти столетие. Это сложная область, занимающаяся вопросами порядка в кажущихся случайными структурах. Но исследователи из Калифорнийского университета в Сан-Диего разгадали давнюю проблему: r (4,t).
Теория Рамсея сводится к поиску скрытой организации в графах — совокупностях точек, соединенных линиями. Теория утверждает, что если граф достаточно велик, то он будет содержать определенный вид порядка — либо группу точек, полностью соединенных линиями (клика), либо группу без связей. 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³ человек. Это не точный ответ, но очень близкая оценка.
Результаты исследования находятся на стадии анализа, но Верстрате полон решимости «добить» эту задачу.
Источник: www.ferra.ru
Похожие новости:
Apple закрывает ИИ-подразделение в Сан-Диего и переводит часть сотрудников в Остин
Астрономы считают, что наконец-то разобрались с происхождением огромных «космических дымовых колец»
Роботакси Waymo столкнулись с противодействием властей Калифорнии
Обзор IT-Weekly: Государство кратно повышает финансирование российской микроэлектроники, Dr.Web Industrial — продукт для защиты предприятий