Ученые раскрыли секрет чисел Рэмси - тайну, которая десятилетиями озадачивала математиков

На протяжении десятилетий математики бьются над загадочным миром задач Рамсея, решение которых кажется практически невозможным. Однако исследователям Жаку Верстрате и Сэму Маттеусу из Калифорнийского университета в Сан-Диего удалось совершить прорыв. Они успешно решили 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 возможных графиков.

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