Математики раскрыли секрет задачи Рамсея спустя почти 100 лет
Математики из Калифорнийского университета (UC) в Сан-Диего Жак Верстрете и Сэм Маттеус решили загадочную теоретическую задачу Рамсея (Рэмси), которая не получила большого прогресса с тех пор, как великий Пал Эрдеш совершил несколько прорывов в 1937 году.
Уместно отметить, что довольно сложная теория Рамсея – ветвь игры чисел, связанная с порядком внутри структур, названная в честь британского математика и философа Фрэнка Рамсея (Frank Ramsey) – чаще всего описывается в контексте вечеринки.
Самая известная задача в этом разделе математики, посвященном теории графов, r(3,3), часто называемая теоремой о друзьях и незнакомцах, предполагает, что в группе из шести человек вы найдете по крайней мере трех человек, которые все знают друг друга, или трех, которые все друг друга не знают.
«Это природный факт, абсолютная истина», — сказал Жак Верстрете. «Неважно, какова ситуация или какие шесть человек вы выберете — вы найдете трех человек, которые все друг друга знают, или трех человек, которые не знают друг друга. Возможно, вы сможете найти больше, но гарантировано, что в той или иной группе будет по крайней мере трое».
Как только r(3,3) было найдено, математические умы попытались ответить на следующие проблемы: r(4,4), r(5,5) и r(4,t), где количество несвязанных точек варьируется.
Что произошло после того, как математики обнаружили, что ответом на r(3,3) является 6? Естественно, они хотели знать r (4,4), r (5,5) и r (4, t), где количество точек, которые не соединены, является переменным. Ученые в прошлом веке обнаружили, что ответ на r(4,4) был 18. Между тем, r(5,5) пока неизвестен.
«Многие люди задумывались о r(4,t) – это открытая проблема уже более 90 лет», – сказал Жак Верстрете. «Но это не было тем, что было в центре внимания наших исследований. Все знают, что это сложно, и все пытались это понять, поэтому, если у вас нет новой идеи, вы вряд ли чего-нибудь добьетесь».
Хотя на первый взгляд может показаться, что это не та проблема, на решение которой потребовалось бы почти 100 лет, в теории графов внешний вид обманчив. Например, при решении r (5,5), если бы вы знали, что ответ находится где-то между 40 и 50, и вы начали с 45 точек на графике, вам нужно было бы исследовать 10 234 графика.
«Поскольку эти числа чрезвычайно трудно найти, математики ищут оценки», — объяснил Жак Верстрете. «Это то, чего мы с Сэмом достигли в нашей недавней работе. Как нам найти не точный ответ, а наилучшие оценки того, какими могут быть эти числа Рамсея?»
Жак Верстрете впервые узнал о r (4, t) в книге Эрдеша «О графах: его наследие нерешенных задач», написанной профессорами Калифорнийского университета в Сан-Диего Фан Чангом и покойным Роном Грэмом. Проблема — это предположение Эрдеша, который предложил 250 долларов первому человеку, который сможет ее решить. Можно предположить, что предложение в размере 250 долларов в 1930-х годах могло быть более «выгодным», чем в 2023 году.
В то время как Жак Верстрете некоторое время держал r (4, t) в голове, только около четырех лет назад, работая над другой задачей с другим математиком, он совершил прорыв в отношении псевдослучайных графов, который вывел его на путь решения головоломки Рамсея.
В 2019 году он и математик Дхрув Мубайи, решили r (3, t), но это было все, что у них получилось. Только когда он объединился с Сэмом Маттеусом, который имеет опыт работы в области конечной геометрии, мечта о решении следующей задачи начала казаться реальностью.
«Оказалось, что нужный нам псевдослучайный граф можно найти в конечной геометрии», — говорит Жак Верстрете. «Сэм был идеальным человеком, который пришел и помог создать то, что нам было нужно».
На это все равно ушел почти год, но решение для r (4, t) было найдено: по сути, чтобы устроить вечеринку, где всегда будут четыре человека, которые все знают друг друга, или t человек, которые все друг друга не знают, потребуется присутствие примерно t3 человек. (Приблизительно, потому что это не совсем три.)
«Нам действительно потребовались годы, чтобы решить эту проблему», — говорит Жак Верстрете. «И было много случаев, когда мы застревали и задавались вопросом, сможем ли мы вообще решить эту проблему. Но никогда не следует сдаваться, сколько бы времени это ни заняло».
Математики не сказали, появилось ли сейчас значение r (5,5) на доске, поскольку они ждут, пока их исследование пройдет экспертную оценку и будет принято.
“Мне позвонила фанатка и сказала, что она должна мне 250 долларов”, — добавил Жак Верстрете. При этом, плата за поиск решения в 1930-х годах не была скорректирована с учетом инфляции.
Исследование рецензируется для журнала Annals of Mathematics.