5 ноя 2023 2 758

Задача, ставившая математиков в тупик почти столетие, наконец решена

Задача Рамсея одна из самых сложных и древних проблем в комбинаторике, разделе математики, изучающем способы выбора и распределения объектов. Она связана с поиском порядка и регулярности в хаотичных и случайных структурах, таких как графы, числа или геометрические фигуры. Одним из примеров такой задачи является вопрос: сколько человек нужно пригласить на вечеринку, чтобы гарантированно найти четырех человек, которые знакомы друг с другом или четырех человек, которые незнакомы ни с кем? Это число называется числом Рамсея и обозначается как r (4,4).

Числа Рамсея очень трудно найти, так как они растут очень быстро с увеличением количества людей или групп. Например, известно, что r (3,3) 6, то есть на вечеринке из шести человек всегда найдутся три человека, которые знакомы между собой, или три незнакомых ни с кем человека. Также известно, что r (4,4) 18, то есть на вечеринке из 18 человек всегда найдутся четыре человека, которые знают друг друга, или четыре человека, которые не знают друг друга. Однако r (5,5) до сих пор неизвестно, и его значение лежит где-то между 43 и 49.

Два математика из Сан-Диего, Жак Верстраете и Сэм Маттеус, сделали значительный прогресс в решении одной из вариаций задачи Рамсея, которая называется r (4, t). Эта задача спрашивает: сколько человек нужно пригласить на вечеринку, чтобы гарантированно найти четырех человек, которые знакомы, или t гостей, которые не знают друг друга? Эта задача была предложена в 1930-х годах венгерским математиком Полем Эрдешем, который обещал приз в 250 долларов за ее решение.

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

Многие ученые более 90 лет ломали голову над проблемой r (4, t). Однако эта задача не была центральной темой нашего исследования. Все знают, что это сложная задача, и все пытаются в ней разобраться. Но если у вас нет свежей идеи, вряд ли вы добьетесь какого-либо прогресса

—Жак Верстраете.

На первый взгляд кажется, что решение задачи заняло практически век, однако, когда речь идет о теории графов, внешность может быть обманчивой. Например, при решении r (5,5) при известном диапазоне ответов от 40 до 50, если начать с 45 точек на графе, потребуется целых 10 234 комбинации.

Задачи Рамсея, такие как r(4,5), сформулировать просто, но, как показано на этом графе, возможные решения почти безграничны.

Так как точные числа очень сложно найти, математики работают с оценками. В этом направлении мы достигли прогресса в нашей последней работе. Мы пытаемся найти не точный ответ, а лучшие оценки для чисел Рамсея

— Жак Верстраете.

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