ПРЕДЕЛ ДЛЯ СЕТЕЙ ТЕПЕРЬ ДОКАЗАН ДЛЯ ЛЮБОГО РАЗМЕРА

Возьмите несколько точек и соедините некоторые их пары линиями. Математики называют это графом: точки — его вершины, линии — его рёбра, а расстояние между двумя вершинами — наименьшее число рёбер, которое нужно пройти от одной до другой. Теперь добавьте два правила. Каждая пара вершин должна находиться на расстоянии не больше 2 — соединяться напрямую или через общего соседа. И ни одно ребро не может быть лишним: удалите любое одно, и какая-то пара окажется больше чем в двух шагах друг от друга. Такой граф называется диаметрально 2-критическим (diameter-2-critical). Сколько рёбер он может иметь?

Потолок Мантеля и более смелая догадка

В 1907 году Мантель доказал, что граф на n вершинах без треугольников — без трёх вершин, попарно соединённых между собой, — имеет не более ⌊n²/4⌋ рёбер: n в квадрате, делённое на четыре и округлённое вниз до целого. Достигает этого потолка лишь один граф — сбалансированный полный двудольный граф: две группы, как можно более равные по размеру, каждая вершина одной соединена с каждой вершиной другой, и ни одного ребра внутри группы.

Каждый граф без треугольников, в который нельзя добавить ещё одно ребро, не создав треугольника, является диаметрально 2-критическим. Обратное неверно: некоторые диаметрально 2-критические графы содержат треугольники.

Диаметрально 2-критический граф с 7 вершинами и 9 рёбрами, содержащий треугольник v1v3v5. Удаление v1v3 уничтожает единственный двухшаговый путь между v2 и v3; удаление ребра вне треугольника оставляет его концы без двухшагового пути. — Рисунок 1, Das & Fox (2026), arXiv:2610.39032.

Догадка состояла в том, что треугольники ничего не дают: диаметрально 2-критический граф на n вершинах всё равно имеет не более ⌊n²/4⌋ рёбер, и сбалансированный полный двудольный граф по-прежнему единственный, кто этого достигает. Теорема Мантеля следовала бы как частный случай. Для 7 вершин на рисунке потолок равен 12 рёбрам.

Башня из двоек

По словам Эрдёша, как сообщает Золтан Фюреди (Zoltán Füredi), вопрос восходит к работам Оре 1960-х годов. Ян Плесник (Ján Plesník) сформулировал оценку числа рёбер как гипотезу в 1975 году; Мурти и Саймон предложили её независимо и добавили, что сбалансированный полный двудольный граф — единственный экстремальный случай, — отсюда название гипотеза Мурти — Саймона. В 1970-х и 1980-х годах оценки вида c·n² постепенно снижались, а c всё ближе подходило к 1/4.

В 1992 году Фюреди доказал гипотезу для всех достаточно больших n с помощью методов регулярности — инструментов, выведенных из леммы Семереди о регулярности. Ценой стал начальный размер: n должно было быть не меньше башни из двоек высотой примерно 10¹⁴, то есть 2 в степени 2 в степени 2…, вычисляемое сверху вниз — каждая двойка возводится в степень всего, что стоит над ней, — с примерно 10¹⁴ двойками в стопке. Ниже этого размера были решены лишь особые семейства графов.

Рёбра против отсутствующих рёбер

Новое доказательство Санджаны Дас (Sanjana Das) и Джейкоба Фокса (Jacob Fox) с математического факультета Стэнфордского университета работает для каждого n начиная с 3. Оно использует максимальное паросочетание: множество рёбер, никакие два из которых не имеют общей вершины, к которому нельзя добавить ещё одно ребро так, чтобы два из них не встретились. Паросочетание на n вершинах содержит не более ⌊n/2⌋ рёбер.

Ключевая лемма: в диаметрально 2-критическом графе для любого максимального паросочетания рёбер вне паросочетания никогда не больше, чем не-рёбер — пар вершин, которые не соединены. Остальное — арифметика. Удвоенное число рёбер не превышает число пар плюс размер паросочетания. При 10 вершинах: 45 пар плюс не более 5 рёбер паросочетания дают 50, значит, рёбер не более 25. Для каждого n эта сумма равна ровно удвоенному потолку Мантеля.

Сама лемма — это тщательная бухгалтерия. Не-ребро называется критическим, если его концы соединяет единственный двухшаговый путь, как у всех двенадцати не-рёбер на рисунке 1. Авторы привязывают каждое критическое не-ребро к двум рёбрам его пути и разбивают получившуюся паутину на связные куски. В куске не более чем на одно ребро больше, чем критических не-рёбер, и за каждый кусок с таким избытком должно расплачиваться некритическое не-ребро. Чтобы найти их, авторы используют выходы через замену (switch exits): берут ребро или критическое не-ребро куска и заменяют один из его концов на партнёра этого конца по паросочетанию. Каждое некритическое не-ребро востребовано не более двух раз, каждый кусок с избытком делает не менее двух заявок, и счёт сходится.

Кто что нашёл

«Это доказательство в основном найдено ИИ, а именно GPT-5.6 Sol 11 августа 2026 года», — пишут авторы в коротком заявлении об использовании ИИ. Модель нашла полное доказательство оценки ⌊n²/4⌋, которое авторы упростили. Для чётного числа вершин она также доказала, что сбалансированный полный двудольный граф — единственный экстремальный случай, опираясь на доказанный Самнером (Sumner) факт о графах, в которых каждое максимальное паросочетание совершенное, то есть покрывает все вершины.

При нечётном числе вершин совершенных паросочетаний нет, и у многих графов каждое максимальное паросочетание пропускает ровно одну вершину: рассуждение модели не удалось адаптировать. Авторы нашли другое доказательство случая равенства, справедливое для каждого n, и написали статью сами; заключительный проход через GPT-6 Astra привёл к «нескольким мелким правкам». Статья — препринт, ещё не прошедший рецензирование, и в ней не упоминается версия рассуждения, проверенная компьютером.

Назад в 1907 год

Если граф достигает потолка, ключевое неравенство обращается в равенство для каждого максимального паросочетания. Хитро выбирая паросочетания, авторы показывают, что такой граф — либо звезда (одна вершина, соединённая со всеми остальными, и больше ничего), либо вообще не имеет критических не-рёбер. В диаметрально 2-критическом графе каждое ребро треугольника лежит на каком-нибудь критическом пути, поэтому отсутствие критических не-рёбер означает отсутствие треугольников; у звезды их тоже нет. Следовательно, граф, достигающий потолка, не содержит треугольников, и последний шаг — та самая теорема, которую гипотеза стремилась усилить: результат Мантеля 1907 года, оставляющий на потолке один лишь сбалансированный полный двудольный граф.