МатематикаПрепринтТеория3 мин чтения

ДОКАЗАТЕЛЬСТВО ИИ, ПЕРЕРИСОВАННОЕ ДЛЯ ЛЮДЕЙ

Нарисуйте несколько точек и соедините некоторые из них линиями. Математики называют это графом; точки — это вершины, линии — рёбра, а число линий, касающихся точки, — её степень. Дерево — это граф без циклов, который держится одним куском, как ветвистый прутик; у дерева с 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-страничная статья сохраняет центральное рассуждение ИИ с подсчётом, но меняет способ его изложения:

  1. Открывайте граф постепенно. Перечислите вершины в некотором порядке и открывайте их по одной вместе с рёбрами между уже показанными.
  2. Требуйте большего. Ищите не любую копию дерева, а такую, у которой выбранный «корень» стоит ровно на первой вершине. Более сильное требование облегчает доказательство.
  3. Считайте ранних соседей. Это соседи первой вершины, которые появляются до того, как возникнет такая копия. Сложите их по всем возможным порядкам.
  4. Ограничьте сумму. Переставляя вершины или целые блоки порядка — ходы, которые всегда можно отменить, — Каммингс показывает, что в среднем по всем порядкам ранних соседей не больше t − 2.

Последний шаг короток. Если бы граф не содержал копии дерева, каждый сосед первой вершины был бы ранним — в любом порядке. В среднем по всем порядкам это ровно средняя степень, которая по условию больше t − 2. Противоречие: дерево обязано быть в графе.

Доказательство использует лишь сумму степеней, а не то, как они распределены. Каммингс также приводит вероятностную версию и разбирает деревья с четырьмя и пятью вершинами на конкретных графах.

Доказательство в картинках

В статье 32 рисунка. Она завершается классическим следствием: раскрасьте все линии полного графа в q цветов — и один цвет всегда будет содержать заданное дерево, как только в графе будет q(t − 2) + 2 вершин. В заключительном заявлении Каммингс поясняет, что разработал текст в долгом диалоге с ChatGPT, что новые идеи изложения — ранние соседи, явные разбиения, рисунки — принадлежат ему и что он всё проверил и берёт на себя полную ответственность.

Он сравнивает своё изложение с другими недавними — Риордана и Скотта, Вуда и Фредериксона — и отмечает, что метод уже распространили на сети с направлениями и на «гиперграфы», причём часть этих обобщений тоже приписывается GPT-6 Astra. Его вклад, пишет он, — это «ориентированное на читателя наглядное изложение рассуждения, а не новое решение гипотезы».