Не могли найти ответ 100 лет: математики решили знаменитую задачу

Исследователи из Калифорнийского университета в Сан-Диего, Жак Верстрете и Сэм Маттеус, разгадали головоломку для математиков, с которой они боролись в течение десятилетий - задачу Рамсея. Об этом пишет "ua.news". Суть задачи Рамсея заключается в нахождении комбинаторного порядка, в котором среди множества точек и линий можно гарантированно выявить определенную структуру.

Эта структура представляет собой набор точек, соединенных линиями или несоединенных. Такие наборы называются "кликами" и обозначаются как r(s, t), где s - количество точек с линиями, а t - количество точек без линий. Самая известная проблема Рамсея, r(3,3), иногда называется "теоремой о друзьях и незнакомцах".

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

Но более сложная проблема r(5,5) оставалась нерешенной. Почему эта задача, казалось бы, простая в формулировке, оказалась такой сложной? Дело в том, что поиск решения усложняется экспоненциальным ростом вариантов. Исследователи Верстрете и Маттеус прибегли к использованию псевдослучайных графов, которые оказались более эффективными при приближении к решению сложных задач Рамсея.

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