Впервые за десятилетия математики приблизились к разгадке таинственных «числ Рамсея»
Проблема связана с числами Рамсея, обманчиво простой концепцией, но довольно скользкой с математической точки зрения. Число Рамсея — это минимальный размер группы, необходимый для того, чтобы определенное количество узлов в этой группе было соединено друг с другом. Самая распространенная метафора — вечеринка: сколько человек нужно пригласить на вечеринку, чтобы убедиться, что там будет либо группа из трех человек, которые будут знать друг друга, либо группа из трех человек, которые будут совершенно незнакомы?
Число Рамсея для 3 равно 6. И чтобы гарантировать, что на данной вечеринке будет группа из четырех друзей или четырех незнакомцев, вам нужно расширить список гостей до 18. Но каково число Рамсея для 5? Многие математики скажут вам, что оно лежит в пределе от 43 до 48. И по мере того, как числа становятся больше, проблема становится все более неразрешимой. Чем больше узлов в сети, тем больше возможных соединений и больше возможных структур для результирующего графа.
«Существует так много возможностей, что вы даже не можете их перебрать», — рассказал Марсело Кампос, соавтор исследования в рамках своей докторской степени в Институте чистой и прикладной математики (IMPA) в Бразилии.
Известно, что математик Пол Эрдёш однажды сказал, что если инопланетяне приземлятся на Землю и потребуют точное число Рамсея для 5, иначе они уничтожат планету, то человечество должно будет направить все свои вычислительные ресурсы на поиск ответа. Но если пришельцы потребуют назвать числа Рамсея для 6 — люди должны готовиться к войне.
Математики могут дать диапазон для любого заданного числа Рамсея. В 1935 году Эрдёш выяснил, что максимальное число Рамсея для заданного числа N равно 4 в степени N. В 1947 году он выяснил, что нижняя граница — это квадратный корень из 2 в степени N. Существует широкий диапазон между этими верхними и нижними границами, однако исследователи десятилетиями пытались сократить разрыв.
Но теперь Кампос и его коллеги добились прогресса в этой верхней границе: вместо 4 в степени N они теперь могут сказать, что максимальное число Рамсея для данной сети равно 3,993 в степени N.
Это может показаться не такой уж большой разницей, но это первый шаг вперед по верхней границе с 1935 года. Команда осуществила доказательство своей теории, разработав новый алгоритм, который ищет определенные подструктуры в графах узлов, называемых «книгами», которые затем помогают им найти группы связанных узлов или т.н. «клик».
Числа Рамсея не имеют конкретного применения в реальном мире; они находятся в области чистой математики. Но попытка их зафиксировать оказала влияние на реальный мир. Например, по словам Кампоса, в 1980-х годах математики исследовали теорию Рамсея с помощью концепции квазислучайности, которая включает в себя группы с определенными математическими свойствами. По словам Кампоса, квазислучайность теперь играет важную роль в компьютерных науках. «Каким-то образом сама проблема стала очень продуктивной», — отметил Конлон.
Новый метод может ужесточить верхний предел даже больше, чем Кампос и его команда показали в своей новой статье, которую они отправили в базу данных препринтов arXiv. Ученые планируют продолжить свою работу и надеются, что к ним подключатся и другие математики, чтобы наконец вывести точную формулу.