ДОКАЗАТЕЛЬСТВО ИИ, ПЕРЕРИСОВАННОЕ ДЛЯ ЛЮДЕЙ
Нарисуйте несколько точек и соедините некоторые из них линиями. Математики называют это графом; точки — это вершины, линии — рёбра, а число линий, касающихся точки, — её степень. Дерево — это граф без циклов, который держится одним куском, как ветвистый прутик; у дерева с t точками всегда t − 1 линий.
В начале 1960-х Пал Эрдёш и Вера Т. Шош задали простой вопрос: сколько линий заставляет граф содержать каждое дерево заданного размера? Их ответ — гипотеза Эрдёша — Шош — звучит так:
Если средняя степень графа больше t − 2, он содержит каждое дерево с t вершинами.
Этот порог точен. Возьмите отдельные копии полного графа с t − 1 точками, где соединена каждая пара: у каждой точки ровно t − 2 соседа, но ни один кусок не настолько велик, чтобы вместить дерево из t точек. Трудность кроется в слове средняя. Если бы у каждой точки было не меньше t − 1 соседей, дерево можно было бы без труда уложить ветка за веткой. Но среднее ничего не говорит об отдельной точке: у одних могут быть сотни соседей, у других — почти никого.
Шестьдесят лет частичных ответов
Согласно изложенной в статье истории, задача восходит к 1962–1964 годам и стала центральной для раздела математики, изучающего, сколько рёбер вынуждает появление заданного узора. Частные случаи поддавались один за другим: звёзды, пути, двойные звёзды, деревья с небольшим числом ветвей. В начале 1990-х четверо математиков — Айтаи, Комлош, Шимонович и Семереди — объявили о доказательстве для очень больших деревьев, но в недавних работах отмечается, что полная рукопись так и не была опубликована. Новые частичные результаты появились в 2021, 2024 и 2026 годах. 4 сентября 2026 года Рид и Стейн выложили доказательство для больших плотных графов, которое, по их словам, было получено без ИИ.
Затем вышел отчёт. В сентябре 2026 года Том Адамчевски и Томас Блум в документе под названием FrontierMath Erdős приписали доказательство всей гипотезы предрелизной версии модели ИИ GPT-6 Astra. Исходное рассуждение с подсчётом опубликовано, а сопровождающий репозиторий фиксирует автономный поиск доказательства моделью и формальную проверку на языке проверки доказательств Lean. Авторы отчёта также призвали экспертов-людей написать более полные, традиционные изложения.
Открывать граф по одной точке
Джей Каммингс из Университета штата Калифорния в Сакраменто откликается на этот призыв. Его 27-страничная статья сохраняет центральное рассуждение ИИ с подсчётом, но меняет способ его изложения:
- Открывайте граф постепенно. Перечислите вершины в некотором порядке и открывайте их по одной вместе с рёбрами между уже показанными.
- Требуйте большего. Ищите не любую копию дерева, а такую, у которой выбранный «корень» стоит ровно на первой вершине. Более сильное требование облегчает доказательство.
- Считайте ранних соседей. Это соседи первой вершины, которые появляются до того, как возникнет такая копия. Сложите их по всем возможным порядкам.
- Ограничьте сумму. Переставляя вершины или целые блоки порядка — ходы, которые всегда можно отменить, — Каммингс показывает, что в среднем по всем порядкам ранних соседей не больше t − 2.
Последний шаг короток. Если бы граф не содержал копии дерева, каждый сосед первой вершины был бы ранним — в любом порядке. В среднем по всем порядкам это ровно средняя степень, которая по условию больше t − 2. Противоречие: дерево обязано быть в графе.
Доказательство использует лишь сумму степеней, а не то, как они распределены. Каммингс также приводит вероятностную версию и разбирает деревья с четырьмя и пятью вершинами на конкретных графах.
Доказательство в картинках
В статье 32 рисунка. Она завершается классическим следствием: раскрасьте все линии полного графа в q цветов — и один цвет всегда будет содержать заданное дерево, как только в графе будет q(t − 2) + 2 вершин. В заключительном заявлении Каммингс поясняет, что разработал текст в долгом диалоге с ChatGPT, что новые идеи изложения — ранние соседи, явные разбиения, рисунки — принадлежат ему и что он всё проверил и берёт на себя полную ответственность.
Он сравнивает своё изложение с другими недавними — Риордана и Скотта, Вуда и Фредериксона — и отмечает, что метод уже распространили на сети с направлениями и на «гиперграфы», причём часть этих обобщений тоже приписывается GPT-6 Astra. Его вклад, пишет он, — это «ориентированное на читателя наглядное изложение рассуждения, а не новое решение гипотезы».
