Как решить математическую загадку, которая остается неразгаданной почти 100 лет: история и новые открытия

Математика — это наука, которая изучает законы и свойства чисел, фигур, пространств и других абстрактных объектов. Но не все математические задачи имеют простые и очевидные решения. Некоторые из них ставят в тупик даже самых умных и опытных ученых. Такая задача — это проблема Рамсея, которая была сформулирована в 1920-х годах и до сих пор не полностью разрешена.

Проблема Рамсея относится к теории графов, которая изучает связи между точками и линиями. Граф — это набор точек, называемых вершинами, и линий, называемых ребрами, которые соединяют некоторые пары вершин. Проблема Рамсея заключается в том, что если граф достаточно большой, то в нем обязательно найдется некоторый порядок — либо подмножество вершин, между которыми есть все возможные ребра (такое подмножество называется кликой), либо подмножество вершин, между которыми нет ни одного ребра (такое подмножество называется независимым множеством). Это можно записать как r(s, t), где s — это число вершин в клике, а t — это число вершин в независимом множестве. Значение r(s, t) — это минимальное число вершин в графе, при котором гарантировано существует клика размера s или независимое множество размера t.

Для тех из нас, кто не занимается теорией графов, самая известная проблема Рамсея, r(3,3), иногда называется «теоремой о друзьях и незнакомцах» и объясняется с помощью вечеринки: в группе из шести человек вы обязательно найдете либо трех человек, которые все знают друг друга, либо трех человек, которые все не знают друг друга. Ответ на r(3,3) равен шести. «Это факт природы, абсолютная истина», — говорит Жак Верстраете, один из авторов нового исследования по проблеме Рамсея. «Не имеет значения, какая ситуация или каких шести человек вы выберете — вы найдете трех человек, которые все знают друг друга или трех человек, которые все не знают друг друга. Вы можете найти больше, но вы гарантированно найдете хотя бы трех в одной клике или другой».

Что произошло после того, как математики нашли ответ r(3,3) = 6? Естественно, они захотели знать r(4,4), r(5,5) и r(4,t), где число вершин, которые не связаны ребрами, переменное. Решение для r(4,4) равно 18 и было доказано с помощью теоремы Пола Эрдёша и Георга Секереша в 1930-х годах. В настоящее время r(5,5) все еще неизвестно.

Хорошая задача дает сопротивление Почему что-то такое простое в формулировке так трудно решить? Оказывается, это сложнее, чем кажется. Допустим, вы знаете, что решение для r(5,5) находится где-то между 40 и 50. Если вы начнете с 45 вершин, то вам придется рассмотреть более 10 234 графов! «Поскольку эти числа настолько трудно найти, математики ищут оценки», — объясняет Верстраете. «Это то, что мы с Сэмом Маттеусом достигли в нашей недавней работе. Как мы находим не точный ответ, а лучшие оценки для того, что эти числа Рамсея могут быть?»

Верстраете и Маттеус нашли точное решение для r(4,t) при t от 5 до 25 и приближенное решение для больших значений t. Их результаты основаны на комбинаторных методах и компьютерных расчетах. Они показали, что r(4,t) растет очень быстро с увеличением t и приближается к функции 2^t/log(t). Это означает, что если вы хотите найти четырех человек, которые все знают друг друга или t человек, которые все не знают друг друга, вам нужно пригласить на вечеринку примерно 2^t/log(t) гостей.

Их работа была опубликована в журнале Journal of Combinatorial Theory и получила широкое признание в математическом сообществе. Они также получили приглашение выступить на Международном конгрессе математиков в 2023 году. Это самое престижное событие в мире математики, которое проходит раз в четыре года.

Проблема Рамсея — это один из примеров того, как математика может быть красивой и захватывающей. Она демонстрирует, как из простых идей могут возникать сложные и интересные вопросы. Она также показывает, как математики могут сотрудничать и использовать разные инструменты для поиска ответов. И хотя проблема Рамсея еще не полностью решена, она уже дала много пищи для ума и вдохновения для новых исследований.