Математики разгадали «задачу о незнакомцах», над которой ученые бились почти 100 лет

Решивший ее профессор искал ответ со студенческой скамьи.

Любой математический объект (например, компанию из шести человек) можно представить в виде графика: точек и линий, соединяющих их. Теория Рамсея, развившаяся из созданной в 1930 году теоремы, предполагает, что в произвольно формируемых математических объектах в итоге обязательно наблюдается закономерность: в графике всегда есть несколько (не обязательно все) точек, каждая из которых соединяется с каждой, или несколько точек, не соединенных друг с другом никакими линиями, пишет «Наука».

Пример: в компании из шести человек обязательно найдется как минимум три человека, которые друг с другом знакомы. Или же наоборот, как минимум три человека, которые друг друга не знают. То есть, 6 — это ответ на первую из задач Рамсея, условие которой выглядит как r(3,3).

Таких задач несколько, и они похожи по структуре: r(s,t), где s — соединенные между собой точки, а t — не соединяющиеся, и надо выяснить, при каком числе связи s или несвязанные t будут гарантированы. В 1930-х годах, почти сразу после обнародования теоремы Рамсея, была решена одна из них: r(4,4) = 18. Ответ для r(5,5) неизвестен. Но последняя, r(4,t), спустя почти 100 лет получила решение, об этом сообщает Калифорнийский университет в Сан-Диего (США).

Решить r(4,t) смогли профессор Жак Верстрете и постдокторант Сэм Маттеус. Сделать это, на самом деле, довольно трудно, ведь в отличие от предыдущих функций в этой — не конкретное число, а переменное t.

«Многие люди задумывались о r(4,t) — это загадка уже более 90 лет. Но я не делал эту задачу центром своей исследовательской работы, ведь все знают, что она сложная, и все пытались в ней разобраться. Так что без какой-то новой идеи нечего было и пытаться. На решение этой проблемы действительно ушли годы. И много раз случалось, что мы застревали и задавались вопросом, сможем ли мы вообще решить эту задачу. Но никогда не следует сдаваться», — сказал Верстрете.

Окончив университет (теорию Рамсея проходят в рамках университетской программы для математиков), Верстрете время от времени возвращался к загадке. В том числе, читал о ней в книге «Эрдёш о графиках: его наследие нерешенных задач».

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

Основываясь на находке Эрдёша Верстете около четырех лет назад вместе с коллегой из Университета Иллинойса-Чикаго (США) Дхрувом Мубайи обнаружил, что выборка из псевдослучайных графиков уточняет этот диапазон. В итоге удалось определить верхние и нижние его значения.

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

«Сэм был идеальным человеком, который мог прийти и помочь создать то, что нам было нужно [для поиска ответа]. Оказалось, что нужную нам псевдослучайную функцию можно найти в конечной геометрии», — рассказывает Верстрете.

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

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

Верстрете также сообщил, что после публикации решения с ним связался один из авторов книги «Эрдёш о графиках: его наследие нерешенных задач», который работает в том же университете, и сказал, что должен ему 250 долларов — столько Эрдёш обещал за ответ.