На протяжении десятилетий математики бьются над загадочным миром задач Рамсея, решение которых кажется практически невозможным. Однако исследователям Жаку Верстрате и Сэму Маттеусу из Калифорнийского университета в Сан-Диего удалось совершить прорыв. Они успешно решили r(4,t) - давнюю задачу Рамсея, которая озадачивает математическое сообщество с 1930-х годов.
Понимание проблемы Рамсея
Проще говоря, граф - это набор точек, соединенных линиями. Теория Рамсея предполагает, что в достаточно большом графе всегда будет присутствовать некоторый порядок. Этот порядок может проявляться либо в виде набора точек, между которыми нет линий, либо в виде набора точек со всеми возможными линиями, которые называются "кликами". Для представления таких графов используется обозначение r(s,t), где s - точки с линиями, а t - точки без линий.
Наиболее известную задачу Рэмси, r(3,3), часто называют "теоремой о друзьях и незнакомцах". Ее можно объяснить на примере вечеринки: в группе из шести человек всегда найдутся как минимум три человека, которые знают друг друга, или три человека, которые не знают друг друга. Решение r(3,3) равно шести.
Взлом кода
Верстрате подчеркивает, что этот феномен является абсолютной истиной, заявляя: "Это факт природы. Неважно, какова ситуация и какие шесть человек вы выберете - вы найдете трех человек, которые все знают друг друга, или трех человек, которые все не знают друг друга. Возможно, вы сможете найти и больше, но гарантированно, что в той или иной клике будет не менее трех человек".
После решения r(3,3) математики, естественно, обратили внимание на 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 возможных графиков для анализа.
"Поскольку такие числа, как известно, найти очень сложно, математики ищут оценки", - объясняет Верстрате. "Именно этого мы с Сэмом и добились в нашей недавней работе. Как найти не точный ответ, а наилучшие оценки того, какими могут быть эти числа Рэмси?"
