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

Математики нашли новый способ навести порядок в хаосе в виде ответа на задачу, которая озадачивала их почти столетие, — так называемую задачу Рамсея, известную как r(4,t).

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

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

Числа Рамсея можно представить как границы беспорядка. И, как известно, вычислить их нелегко.

С тех пор как в конце 1920-х годов математик Фрэнк Рамсей доказал теорему Рамсея, не прекращались споры о конкретной проблеме, которую наконец-то решили Сэм Маттеус и Жак Верстрате из Калифорнийского университета в Сан-Диего.

«Многие задумывались о r(4,t) — эта проблема остается открытой уже более 90 лет, — говорит Верстрате.

»На решение этой проблемы у нас действительно ушли годы. И было много моментов, когда мы заходили в тупик и сомневались, сможем ли мы вообще её решить".

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

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

«Это естественный факт, абсолютная истина. Не имеет значения, какова ситуация или каких шестерых человек вы выберете – вы найдете трех человек, которые все знают друг друга, или трех человек, которые все друг друга не знают», — говорит Верстраете.

«Возможно, вы сможете найти больше, но гарантированно, что в той или иной клике их будет не менее трех».

Задачи Рамсея традиционно решаются с использованием случайных графов. Например, где s изображается в виде точек с синими линиями между ними, а t — в виде точек с красными линиями. Если граф достаточно большой, вы найдете порядок, но он быстро усложняется.

Почти бесконечное число возможных решений задач Рамсея делает их трудноразрешимыми.

Почти бесконечное число возможных решений задач Рамсея делает их трудноразрешимыми.

Математики продемонстрировали это в 1930-х годах. В 1930-х годах математики продемонстрировали теорему, из которой впоследствии следовало, что ответ на вопрос r(4, 4) равен 18. А с 1995 года мы знаем, что r(4,5) = 25. Поэтому ограничьте свой список гостей цифрой 24, если хотите сохранить возможность не приглашать ни четырех знакомых, ни пятерых незнакомцев.

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

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

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

«Поскольку эти числа, как известно, найти очень трудно, математики ищут оценки», — поясняет Верстрате. «Как найти не точный ответ, а наилучшие оценки того, какими могут быть эти числа Рамсея?»

Обнаружив, что оценки могут быть уточнены с использованием псевдослучайных графов, Верстраете и и математик Дхрув Мубаи из Университета Иллинойс-Чикаго успешно решили задачу r(3,t) в 2019 году.

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

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

Спустя почти год и несколько математических препятствий они обнаружили, что r(4,t) близко к кубической функции t. Для вечеринки с четырьмя людьми, которые все друг друга знают, или несколькими людьми, которые не знают друг друга, необходимо t3 человека.

Как отмечают исследователи, это наилучшая оценка, t3 очень близко к точному ответу. Если вам интересно, то математически их результат можно выразить так:

r(4,t) = Ω(t3/log4t ) при t → ∞.

Команда считает, что их подход будет полезен и для других чисел Рамсея и может помочь в оценке других математических функций.

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

Препринт исследования доступен на сайте arXiv, и в настоящее время оно находится на рецензировании в журнале Annals of Mathematics.
 

Первоисточник: www.sciencealert.com

Источник перевода: newsstreet.ru