Всё течёт — и кое-что даже доказывается: неделимые потоки

Введение

Пост про гипотезу Диница — Гарга — Гёманса я закончил словами “А что ещё дальше, коллеги?..”. Сегодня могу отчитаться, что было дальше: три недели, три препринта, один merged pull request от внешнего контрибьютора и мои первые сабмиты на VibeMathed.

Если коротко, то из твита Дмитрия Рыбина выросла целая исследовательская программа. Сначала мы с моделями опускали планку снизу:

Часть I, “A Planar Lower Bound 1.1397… > 9/8 for Cost-Preserving Single-Source Unsplittable Flows”, подняла нижнюю оценку с $9/8$ до $1.1397\ldots$ ,
Часть II, “Deletion-Star Ceilings and a 1.28249 Lower Bound for Cost-Preserving Single-Source Unsplittable Flows” — до $1.2825\ldots$ ; потом сообщество в лице Альфредо де ла Фуэнте докрутило её до $1.2826\ldots$ прямым pull request’ом в мой репозиторий.

А потом произошёл поворот, ради которого я и пишу этот пост:

в Части III, “Exact-Mean Decompositions for Cost-Preserving Single-Source Unsplittable Flows: Demand Scales and Local Interaction Structure” появились первые положительные результаты — точные константы и первые конечные оценки для неограниченных классов задач.

При этом константы наших же контрпримеров из первых двух частей оказались не просто какими-то случайными контрпримерами, а точными значениями для соответствующих классов задач.

Здесь, правда, речь уже не про один гигачад-промпт “you should do a breakthrough”. Это была долгая совместная работа с LLM, с десятками промптов, неудачных попыток, провалившихся экспериментов и так далее. Ошибки тоже регулярно встречались, хотя честно скажу, что хоть я и проверил всё, что происходит в финальном тексте, но лично я не нашёл ни одной дырки — все ошибки, которые были в доказательствах, находились на этапе перекрёстной проверки другими LLM.

Мне кажется, именно так в ближайшие месяцы (а может, и годы) будет выглядеть заметная часть математики, поэтому расскажу всё по порядку — от контрпримеров до теорем, без технических выкладок, но с главными идеями.

Напоминание: гипотеза и треугольник

Кратко напомню постановку задачи; подробности есть в прошлом посте.

Рассмотрим ориентированный граф с источником $s$ , терминалами $t_1,\ldots,t_k$ и заказами $d_1,\ldots,d_k$ ; на дугах могут быть неотрицательные цены $c_a$ . Дан дробный поток $\mathbf{x}$ , который можно делить по путям как угодно. Мы хотим получить неделимый поток $\mathbf{y}$ : один путь на терминал, так что весь заказ идёт целиком по этому пути. Теорема Диница — Гарга — Гёманса (1999) говорит, что всегда можно добиться на каждой дуге выполнения условия

$y_a\le x_a+d_{\max},\qquad d_{\max}=\max_i d_i,$

а гипотеза Гёманса утверждала, что одновременно можно сохранить и цену, $\mathbf{c}^\top\mathbf{y}\le\mathbf{c}^\top\mathbf{x}$ .

22 июля 2026 года GPT 5.6 Pro по запросу Дмитрия Рыбина построила контрпример с семью вершинами: любой неделимый поток, укладывающийся в добавку $d_{\max}$ , имеет здесь цену минимум 60 при дробной цене 58.

Семивершинный контрпример к гипотезе Диница — Гарга — Гёманса: дробный поток стоимости 58

Мы подробно обсуждали этот пример в прошлом посте. Внутренний механизм этого контрпримера — треугольник попарных конфликтов: три “бесплатных” пути, любые два из которых вместе перегружают какую-то дугу. Дробный поток набирает по бесплатным путям суммарную массу $\tfrac{16}{15}>1$ , а неделимый может позволить себе не больше одного бесплатного выбора.

Треугольник конфликтов бесплатных путей в контрпримере

В том же посте мы видели, что параметрическое семейство на той же схеме из 7 вершин доводит нижнюю оценку до любого $\alpha<\tfrac 98$ : если разрешать перегрузку $y_a\le x_a+\alpha\, d_{\max}$ и требовать сохранения цены, то должно выполняться $\alpha\ge \tfrac 98$ . Сверху же для планарных графов известна константа 2 (Traub, Vargas Koch, Zenklusen, 2023). Так что в начале пути у нас был зазор между $\tfrac 98$ и $2$ для планарных графов, а для произвольных верхней оценки не было вовсе.

Первый естественный вопрос: может быть, тот же треугольник, но с другими числами, даст больше $\tfrac 98$ ?

Это была как раз первая теорема всей серии: $\tfrac 98$ — точная верхняя граница для всего шаблона “у каждого из трёх терминалов есть дешёвый и дорогой путь, конфликты попарные”. Ни для каких заказов, долей и цен константу выше $\tfrac 98$ на этом механизме не получить. Значит, для более сильной нижней оценки нужен структурно новый пример.

Хребты и терминалы с парой выходов

Новый пример нашёлся в виде, который потом оказался центральным для всей истории. Берём ориентированную цепочку $v_0\to v_1\to\cdots\to v_5$ (“хребет” графа) и в каждый терминал отправляем ровно два выхода с хребта: ранний и поздний. Вот пример такого графа:

Значит, к любому терминалу из $v_0$ ровно два пути; назовём их “ранний” (красный на картинке выше) и “поздний” (синий). Переключение терминала $i$ с раннего пути на поздний добавляет $d_i$ на дугах хребта, которые лежат в интервале $[l_i,r_i]$ , и получается, что вся комбинаторика такого примера описывается семейством интервалов:

Хребтовая цепочка с ранними и поздними выходами и четырьмя пересекающимися интервалами

Контрпример из части I был основан на четырёх терминалах с интервалами $[0,2]$ , $[0,4]$ , $[1,4]$ , $[2,3]$ :

Оптимизация по заказам и долям даёт нижнюю оценку

$C\;\ge\;\frac{299-41\sqrt{41}}{32}\;=\;1.13974707\ldots\;>\;\frac98=1.125,$

причём с точным алгебраическим сертификатом. Есть и целочисленное подсемейство с константами $182359/160000-1/n$ , так что всё можно реализовать и на рациональных данных (в целом это и так очевидно). И важно, что конструкция здесь планарная, так что зазор для планарных графов сузился до $[1.1397\ldots,\,2]$ .

Важная техническая деталь: у каждого терминала в этих конструкциях ровно два простых пути, так что верификацию можно вести буквально полным перебором, и проверяющая программа не может ничего пропустить или забыть. Ту же константу независимо и раньше получил Matthew Protti (23 July 2026); тогда я об этом не знал, но потом во введении Части III расставил все известные мне ссылки.

Число $(299-41\sqrt{41})/32$ больше $9/8$ , но это не всё, что о нём можно сказать; оно ещё вернётся в этой истории с совершенно другой стороны.

Часть II. Семнадцать терминалов с общим ребром

Естественным продолжением этой работы было бы попробовать обобщить и продолжить действие такого же механизма с попарными переключениями и системами интервалов.

И действительно, обобщить удалось: в Part II мы предъявляем пример, в котором уже сразу 17 терминалов, поздние пути которых все проходят через одно общее ребро.

На этом графе, конечно, чёрт ногу сломит (и очевидно, что он не планарный), но вот соответствующая ему система интервалов со всеми числами. На картинке ниже $d$ — это спрос, а $f$ — доля дробного потока, которая отправляется на поздний путь; во всех случаях ранний выход к терминалу $i$ стоит $\tfrac 1{d_i}$ , а поздний выход бесплатный:

Оптимизация (уже довольно нетривиальная) дала рекорд

$C\;\ge\;1.282494797984843521\ldots$

Заметим здесь одну закономерность, к которой вернёмся позже: во всех рекордных примерах заказы попарно не делят друг друга и лежат в узкой полосе, внутри одного “двойного окна” $[n,2n]$ , то есть никакое значение не превосходит удвоенного другого. Все семнадцать заказов в рекордном примере укладываются в одно двойное окно. Это не совпадение, и мы ниже объясним, почему так.

В Части II появились и первые верхние оценки: на классе таких вот конструкций (два пути на терминал, пересекающиеся по одному ребру интервалы) метод не может дать оценку больше $3/2$ . Это, конечно, верхняя оценка только на очень конкретный класс графов, то есть ограничение метода, а не какая-то интересная теорема сама по себе.

Потом случилось очень крутое событие, которое меня изрядно вдохновило продолжать. Я выложил репозиторий с сертификатами и верификаторами, и Альфредо де ла Фуэнте (Alfredo De la Fuente) прислал pull request: транспонировать правые концы двух интервалов и переоптимизировать заказы. Его сертификат прошёл все наши проверки, и текущий рекорд теперь community-contributed:

$C\;\ge\;\frac{160325086265636045340018727271}{125000000000000000000000000000}\;=\;1.28260069012508836\ldots$

Мне очень понравилось, что задача вызвала интерес у сообщества. На Vibemathed мой пост с этими результатами тоже получил довольно много по меркам этого сайта комментариев. В частности, конечно, меня ткнули носом в том, что Matthew Protti был первым с оценкой, близкой к $\tfrac98$ .)

Лестница рекордов по числу терминалов $k$ выглядела так: $k=4$ : $1.13975$ , $k=5$ : $1.16798$ , $k=6$ : $11-4\sqrt6$ , $k=7$ : $13/2-2\sqrt7$ , $k=8$ : $\approx1.2148$ , $k=17$ : $1.2826$ .

Запомните и её — к ней мы тоже вернёмся.

А нельзя ли чего-нибудь доказать?

К этому моменту у константы $C$ было уже довольно много нижних оценок и удручающе мало верхних. Хуже того: для общих графов и произвольных заказов было неизвестно, существует ли вообще конечная константа $C$ , то есть неизвестно, конечна ли она в принципе. С этого вопроса и началась Часть III.

Вспомним, почему в гипотезу Гёманса верили: доли дробного потока по путям выглядят как вероятности, и независимый выбор путей даёт в среднем и нужные нагрузки, и нужную цену. Контрпример показал, что независимое округление разваливается. Но сам вероятностный язык можно было использовать и дальше.

Вот главный принцип, на котором стоит вся Часть III: раскладываем ошибку на множители, сохраняя среднее. Иначе говоря, мы ищем не один поток (маршрутизацию, routing), а распределение на потоках, у которого

математическое ожидание нагрузок равно дробному потоку $\mathbf{x}$ в точности, на каждой дуге, и при этом
каждый атом распределения заключён в “ящике”: $\mathbf{Y}\le\mathbf{x}+CD\mathbf{1}$ почти наверное.

Точное среднее маршрутизаций внутри ограничивающей коробки

Если такое распределение есть, то сохранение цены получается автоматически: средняя цена равна $\mathbf{c}^\top\mathbf{x}$ , значит, какой-то атом стоит не дороже. После этого цены рёбер вообще исчезают из задачи, и остаётся чистая “геометрия” (ну, не настоящая геометрия, конечно): какого размера нужен “ящик”, чтобы $\mathbf{x}$ смог стать точным средним целых маршрутизаций?

Это нехитрая интуиция, и так люди уже думали о потоках. Первым интересным (и, насколько я могу судить, новым) результатом Части III стало то, что это не просто удобный приём, а приём достаточный. Для любого класса графов, замкнутого относительно удаления дуг (а это все естественные классы: планарные, последовательно-параллельные, деревья…), выполняется равенство: оптимальная константа сохранения цены в точности равна минимальному радиусу ящика для точных средних.

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

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

Арифметика: делимость бесплатно, несравнимость нет

В этой науке есть классический результат Skutella (2002): если заказы образуют цепочку делимости (каждый делит следующий), гипотеза Гёманса верна как есть, с константой 1. На языке точных средних это “локальный закон”: внутри цепочки делимости мы можем явно построить нужное распределение.

Часть III превращает это в общий принцип факторизации:

разобьём множество значений заказов на цепочки делимости,
построим распределение в каждой цепочке независимо,
перемножим полученные распределения.

При этом точные средние складываются, радиусы складываются, и каждая цепочка платит один раз своим максимумом. И получается, что

$C\;\le\;\frac{\text{sum of divisibility chain maxima}}{D},$

где $D$ — максимальное значение одного заказа, а оптимальное покрытие цепочками считается за полиномиальное время через паросочетание максимального веса.

Если быть точным, то результат говорит, что ключевым объектом для нас является разбиение $\mathcal{P}$ мультимножества заказов (множества терминалов) на цепочки делимости $B$ . Мы сможем построить нужный “ящик” радиуса

$S(\mathcal{P})=\sum_{B\in \mathcal{P}}\max_{i\in B}d_i,$

то есть любой дробный поток $\mathbf{x}$ будет выпуклой комбинацией “опорных маршрутизаций” (support routings) $\mathbf{y}$ с точно совпадающим средним и радиусом $S(\mathcal{P})$ :

$|\mathbf{y}-\mathbf{x}|\le S(\mathcal{P})\mathbf{1}.$

Например, можно разбить заказы на множества по значениям, т.е. если $\mathcal{V}=\{d_i\}$ именно как множество, без повторов, и если $R=\sum_{v\in\mathcal{V}}v$ , то

$\textbf{x}\in\mathrm{conv}\bigl\{\textbf{y}:\ \textbf{y}\text{ is a support routing},\ |\textbf{y}-\textbf{x}|\le R\textbf{1}\bigr\},$

а значит, в частности, аддитивная константа на этом примере не превышает $\frac RD$ (константу ещё на максимальное значение заказа нужно разделить).

Рассмотрим маленький пример: пусть у нас заказы $\{6,3,2\}$ . Наивная сумма даёт $C\le(6+3+2)/6=11/6$ , но $3\mid 6$ , поэтому покрытие $\{6,3\},\{2\}$ стоит $(6+2)/6$ , и $C\le 4/3$ . Добавление значения 1 ничего не меняет — единица прицепится к любой цепочке бесплатно. А вот для попарно несравнимых $\{6,5,4\}$ никакое покрытие не побьёт простую сумму.

Именно поэтому в контрпримерах всё время появляются попарно не делящие друг друга заказы в узкой полосе. Теперь это не эмпирическое наблюдение, а теорема о том, где метод работает, а где не очень.

Немедленные следствия:

если значений всего два, $d < D$ , то $C\le 1+d/D\le2$ (это константа Морелла — Скутеллы, теперь доказанная для всех примеров с двумя значениями);
если в каждой диадической полосе $(2^{-(j+1)}D,2^{-j}D]$ не больше одного значения, то $C\le 2$ (достаточно их все просуммировать как $1+\frac12+\frac14+\frac18+\ldots$ );
если в примере конечное множество значений, то у него будет конечная константа.

Последнее утверждение, конечно, не означает глобальной конечной константы, но все наши контрпримеры в Частях I–II использовали не больше девяти различных значений, так что для всех них можно теперь какую-то общую верхнюю оценку получить (не очень интересную).

Давайте разберём ещё чуть более содержательный пример, чтобы увидеть, как это суммирование оценок работает. Вот он:

Здесь терминал $t_1$ (спрос $d_1=6$ ) использует общую дугу с весом $\tfrac 13$ , терминал $t_2$ (спрос $d_2=5$ ) с весом $\tfrac 12$ , так что нагрузка получается $x_e=6\cdot\frac13+5\cdot\frac12=\frac92$ .

В этом примере четыре целочисленных маршрутизации; назовём их 00, 01, 10, 11: первый бит показывает, идёт ли через $e$ путь в $t_1$ , а второй — в $t_2$ . И если рассмотреть веса как независимые вероятности, то получатся вероятности как на картинке и ожидание

$\mathbb{E}Y_a = \frac16\cdot 6 + \frac13\cdot 5 + \frac16\cdot 11 = \frac 92,$

то есть при таком разложении сохраняется точное среднее. А радиусы просто складываются и получается $6+5=11$ .

На этом месте хочется, конечно, сказать: а давайте округлим значения заказов вверх до какого-то общего значения или одной цепочки делимостей, разложим увеличенный поток, а потом восстановим изначальные результаты. Но так не работает (это тоже один из результатов): общее разложение не будет знать, какой путь ведёт к какому терминалу, а это будет необходимо для восстановления; не буду вдаваться в детали, но про это у нас тоже есть небольшой раздел.

А вот округление вниз работает, если срезанная часть заказа сначала удаляется из самых дорогих путей. Здесь тоже вдаваться в детали не буду, но, в общем, получается целое семейство оценок, параметризованное основанием $b$ и глубиной сетки $m$ . Две первые его точки давно известны — это оценки Скутеллы

$\mathbf{y}\le2\,\mathbf{x}+D\,\mathbf{1},\qquad \mathbf{y}\le\sqrt2\,\mathbf{x}+\Bigl(1+\tfrac1{\sqrt2}\Bigr)D\,\mathbf{1},$

а дальше кривая продолжается на все $m$ , с пределом в чистом сдвиге и полезным следствием для потоков ограниченной нагрузки:

Семейство shifted-chain оценок и следствие для ограниченной нагрузки

Вся задача свелась к одному окну $[n,2n]$

Самый концептуальный результат на этом арифметическом пути — редукция слияния (merger reduction). Определим “оконную константу” $K^\ast$ : наилучшую аддитивную ошибку точного среднего для примеров, все заказы которых лежат в одном “двойном окне” вида $[n, 2n]$ . Тогда мы доказали, что

$C_{\mathrm{opt}}\;\le\;K^\ast\;\le\;2\,C_{\mathrm{opt}}.$

Иными словами, универсальная конечная константа существует тогда и только тогда, когда конечна $K^\ast$ , и вся общность задачи по сути свелась к вопросу об одном окне значений $[n,2n]$ .

Например, все заказы рекорда с $k=17$ сами лежат в одной такой полосе $(\frac12, 1]$ , и более точное рассуждение о выпуклых оболочках показывает, что этот пример даёт

$K^\ast\;\ge\;2\,C_{17}\;=\;2.565201380250176725\ldots$

То есть слить одно окно “почти бесплатно” (с $K<2.565$ ) невозможно — нижние оценки бьют и по этой цели. Полный точный профиль рекордного потока (все пятнадцать сегментов его релаксированной границы) мы тоже посчитали и выложили:

Точная граница relaxed-merger для 17-терминального потока

Геометрия: пары бесплатны, первый враг — треугольник

Теперь вторая ось частичных результатов. На арифметической оси мы ограничивали значения заказов, а граф и взаимодействие путей оставляли произвольными; здесь всё наоборот: заказы любые, но ограничена геометрия взаимодействия путей. Отправная точка — общее свойство всех наших контрпримеров: в них к каждому терминалу ведут ровно два простых пути. Назовём такие примеры двухпутевыми (two-path instances) и посмотрим, во что превращается задача.

Когда путей ровно два, маршрутизация — это просто вектор битов $\mathbf{z}\in\{0,1\}^k$ : $z_i=1$ , если терминал $i$ идёт по одному из своих путей (назовём его “поздним”, $P^1_i$ ), и $z_i=0$ , если по другому (“раннему”, $P^0_i$ ). Дробный поток превращается в набор долей $f_i\in[0,1]$ : с какой “вероятностью” терминал $i$ выбирает поздний путь. А весь граф сворачивается в матрицу разностей маршрутов $g$ : положим $g_{ai}=+1$ , если дуга $a$ лежит только на позднем пути терминала $i$ , $g_{ai}=-1$ , если только на раннем, и $g_{ai}=0$ , если она лежит на обоих или ни на одном. Смысл этой матрицы в том, что ошибка любой маршрутизации на любой дуге записывается одной формулой:

$Y_a-x_a=\sum_i d_ig_{ai}(z_i-f_i).$

В хребтовых примерах матрица выглядит совсем наглядно: в строке дуги хребта $+1$ стоят напротив интервалов, которые её накрывают. Переключение такого терминала на поздний путь добавляет на этой дуге $d_i$ ; строка раннего частного выхода терминала $i$ — одинокая $-1$ , позднего — одинокая $+1$ . В произвольных направленных ациклических графах знаки внутри одной строки могут смешиваться.

Число ненулевых элементов строки назовём её арностью: это число терминалов, чьё переключение вообще затрагивает данную дугу.

На этом этапе граф можно выбросить, и остаётся чистая комбинаторная задача: по знаковым строкам, заказам и долям найти распределение на булевом кубе, у которого маргиналы в точности равны $f_i$ (это и даёт точное среднее), а ошибки всех строк на всех атомах не превосходят $CD$ . Интуитивно чем меньше арности строк, тем легче; строки арности 1 тривиальны: их ошибка $d_i(z_i-f_i)$ никогда не превосходит $D$ по модулю.

Но есть и неприятный сюрприз: на абстрактном уровне уже пары, то есть строки арности 2, могут стоить больше $D$ . Пример из статьи: два терминала с единичными заказами, доли $(f_1,f_2)=(3/5,4/5)$ и две строки со знаками $(+,+)$ и $(+,-)$ . У первой строки состояние $00$ имеет ошибку $-7/5$ , так что радиус $1$ требует $p_{00}=0$ ; у второй за ящик вылезает состояние $10$ с ошибкой $6/5$ , то есть нужно ещё и $p_{10}=0$ . Вместе с маргиналами это несовместно: обозначив $t=p_{11}$ , получаем $p_{00}=t-2/5$ и $p_{10}=3/5-t$ , и первое условие требует $t=2/5$ , а второе — $t=3/5$ . Лучший достижимый радиус здесь $6/5$ .

Столько же, $6/5$ , даёт и “нечётная дыра” — цикл длины пять из всюду положительных парных строк, главный подозреваемый ещё со времён абстрактного анализа Части I. Если бы такие знаковые узоры реализовывались потоками, ни о какой “бесплатности пар” речи бы не шло.

Первая структурная теорема Части III: они не реализуются. Начнём с самого простого случая: у двухпутевого потока для любой пары терминалов $\{i,j\}$ произведение знаков $g_{ai}g_{aj}$ одинаково на всех дугах, где оба сомножителя ненулевые. Доказательство — симпатичная графовая склейка, которую я здесь не буду объяснять в деталях:

На самом деле верно гораздо больше: вся матрица $g$ (после удаления нулевых строк) — это сетевая матрица (network matrix), матрица знаковых инциденций путей в некотором дереве, и в частности она вполне унимодулярна. Идея доказательства: в носителе двухпутевого потока в каждую вершину можно прийти из источника не более чем двумя способами — третий способ немедленно дал бы третий путь какому-нибудь терминалу.

Вершины, достижимые одним способом, образуют дерево, а компоненты, достижимые двумя, — это общие “хвосты” пар путей, которые в разности всё равно сокращаются. После некоторых преобразований разность путей каждого терминала превращается в обычный путь между двумя листьями одного общего дерева, а матрицы путей в дереве — это и есть сетевые матрицы.

На теорему о сетевых матрицах можно ещё посмотреть так: для любого двухпутевого примера существует дерево $T$ , в котором каждый терминал $i$ представлен путём $Q_i$ между двумя листьями, а каждая строка матрицы разностей — ребром $e$ этого дерева, причём носитель строки (множество терминалов с ненулевым знаком) — это в точности множество путей, проходящих через $e$ . То есть словарь: такой: терминалы — пути в дереве, строки — рёбра дерева, арность строки — нагрузка ребра (сколько путей через него идёт).

И можно рассмотреть гиперграф взаимодействия — матрицу $g$ , прочитанную по строкам: вершины — терминалы, гиперребро ребра $e$ — это $S_e=\{i:e\in Q_i\}$ . При этом взгляде мы забываем знаки и величины и смотрим лишь на носители строк; к этому гиперграфу мы вернёмся в следующем разделе.

Из теоремы сразу получается и общее правило чётности: если несколько парных строк образуют “чистый цикл” длины $n$ , произведение всех их знаков обязано равняться $(-1)^n$ , иначе нашёлся бы минор с определителем $\pm2$ . Цикл из примера выше и всюду положительный 5-цикл это правило нарушают.

Теперь можно собрать положительный результат — обещанную бесплатность пар. Пусть все строки имеют арность не выше 2. Посмотрим на одну парную строку, для определённости со знаками $(+,+)$ , и на четыре угла булева квадрата. Смешанные углы хороши всегда: скажем, в угле $10$ ошибка равна $d_i(1-f_i)-d_jf_j$ и по модулю не превосходит $D$ . Плохим может оказаться только угол $11$ (сверху) или угол $00$ (снизу), причём не оба сразу: их ошибки различаются ровно на $d_i+d_j\le2D$ .

Числовой пример из статьи: единичные заказы, доли $(1/5,1/5)$ ; ошибки в состояниях $00,10,01,11$ равны $-2/5$ , $3/5$ , $3/5$ , $8/5$ , и плох только угол $11$ . Плохой угол отрезается одним целочисленным неравенством — здесь $z_i+z_j\le1$ , — дробная точка ему удовлетворяет, и хорошие вершины дают готовую смесь с точным средним:

$(1/5,\,1/5)\;=\;\tfrac35\,(0,0)+\tfrac15\,(1,0)+\tfrac15\,(0,1).$

Осталось проделать это одновременно по всем строкам: пересечём единичный куб со всеми неравенствами, отрезающими плохие углы. Нормали этих неравенств — строки самой матрицы $g$ (с точностью до знака), правые части целые, и вполне унимодулярность гарантирует, что получившийся многогранник целочисленный. Значит, точка долей $(f_i)$ раскладывается в выпуклую комбинацию его булевых вершин, и каждая такая вершина обходит все запрещённые углы всех строк сразу. Итого получается теорема.

Теорема. У двухпутевого примера, все строки которого имеют арность не выше 2, точный радиус равен ровно $D$ — при любой цикличности взаимодействий.

В обозначениях, которые пригодятся ниже: локальная константа арности два $E(2)=1$ . Меньше единицы не бывает уже на одном терминале: если доля одного из путей стремится к нулю, любая смесь с точным средним обязана давать этому пути его положительную массу, и перегрузка соответствующего атома стремится к $D$ .

Обратите внимание, как всё это ломает исходную интуицию: казалось, что главная опасность — циклы конфликтов, а оказалось, что циклы попарных конфликтов не стоят вообще ничего. Препятствие надо искать не в цикличности, а в арности.

Итак, первый настоящий враг — строки арности 3. И минимальный живой пример нам давно знаком — “тернарное ядро”, тот самый треугольник: хребет из трёх дуг и три интервала $[0,1]$ , $[0,2]$ , $[1,2]$ , дающие строки $110$ , $111$ , $011$ :

Тернарное ядро взаимодействий со строками 110, 111 и 011

И здесь Часть III доказывает точное значение: локальная константа тройного ядра равна ровно $9/8$ . Не “не меньше”, как в контрпримере, а ровно: верхняя оценка теперь тоже есть, с явным экстремальным семейством решений. Треугольник Рыбина оказался не случайной находкой, а точным локальным экстремумом общей теории.

Дальше — четыре колонки. Существует ровно пять максимальных носителей взаимодействия четырёх терминалов (с точностью до перестановок; эта классификация тоже нетривиальная и тоже доказывается в статье):

Пять нормальных форм взаимодействия четырёх терминалов

Форма 0 — это интервальное ядро Части I, и её точная локальная константа равна

$E(4)\;=\;\frac{299-41\sqrt{41}}{32},$

в точности константе нашего контрпримера; остальные четыре формы дают ровно $9/8$ . Доказательство верхней границы для $E(4)$ — самое тяжёлое место статьи: 2015 граничных клеток, закрытых вручную выписанными покрытиями, проекциями и одним аргументом типа Хелли, без численных переборов (численный поиск использовался только чтобы найти граничные клетки, ни одно его решение в доказательство не входит).

Его мы, конечно, пропустим, зато теперь можно показать всю лестницу целиком:

Лестница доказанных локальных констант и рекордных значений

Синие квадраты — теоремы с точными оценками: $E(2)=1$ , $E(3)=9/8$ , $E(4)=(299-41\sqrt{41})/32$ . Оранжевые кружки — рекорды из Части II, которые мы теперь считаем гипотетическими следующими ступенями той же лестницы. Пунктир — гипотеза Части II о супремуме $4/3$ для этого класса. Первые две нетривиальные ступени лестницы совпали с константами контрпримеров: нижние оценки Частей I–II, найденные задолго до всей этой теории, оказались точными значениями экстремальных задач, о существовании которых мы тогда не подозревали. По-моему, это крутой сюжетный поворот.

Раскраски, Property B и первый ответ для неограниченного класса

Локальные ядра — это хорошо, но что делать с глобальной системой, где троек много и они переплетены? Здесь помогает классическая комбинаторика.

Строки взаимодействия арности $\le2$ бесплатны (один $D$ -ящик). Значит, для системы с арностью $\le3$ достаточно раскрасить терминалы в два цвета так, чтобы ни одна тройная строка не стала одноцветной: внутри каждого цвета арность упадёт до двух, каждый цвет заплатит один $D$ -ящик, итого $2D$ . Здесь мы пользуемся нашим свойством композиции, складывая радиусы частей графа.

И теперь можно вспомнить гиперграфы из предыдущего раздела: их мы как раз и раскрашиваем. Оказывается, свойство “гиперграф двураскрашиваем без одноцветных рёбер” — это классическое Property B (в честь Бернштейна, название Миллера, 1937). Сам я о таких комбинаторных понятиях, разумеется, ни разу не слышал, пока мы с LLM не занялись этой задачей.

В общем случае Property B может не выполняться. Минимальный контрпример арности 3 — плоскость Фано, семь точек и семь прямых.

Но есть и другой факт: плоскость Фано не реализуется путями в дереве. Инцидентности семи путей и семи рёбер дерева не могут образовать Фано — после стягивания всё упирается в диаметр-3 и двойную звезду, и одна прямая должна была бы лежать во всех семи тройках. Классическое препятствие исключается самой геометрией деревьев.

А положительная сторона доказывается через рёберные раскраски: пути в дереве с нагрузкой не выше $\Delta$ на ребро можно правильно раскрасить в $\lfloor3\Delta/2\rfloor$ цветов (это теорема Притчарда — Ротвосса, в основании которой лежит теорема Шеннона о рёберной раскраске мультиграфов). Для $\Delta=3$ берём четыре цвета и сливаем их в два блока $\{1,2\}$ и $\{3,4\}$ : три пути на одном ребре имеют три разных цвета, значит, ни одна тройка не окажется в одном блоке. Итого:

Теорема. В двухпутевых графах, если арность взаимодействия не превышает 3, то радиус не превышает $2D$ .

У нас получилась первая конечная константа для класса, в котором ограничена только локальная арность, а всё остальное произвольное: и число терминалов, и цикличность, и значения заказов.

Более того, для произвольной арности $m$ тот же приём даёт $\lceil\lfloor3m/2\rfloor/2\rceil\cdot D$ . Это, опять же, глобальная оценка для класса графов с некоторым ограниченным локальным свойством; кажется, что это естественное свойство в данном случае. Но всё-таки нельзя забывать, что во всём “геометрическом” подходе речь шла исключительно про двухпутевые графы.

Классы графов и новый планарный рекорд

Теперь можно свести результаты о классах графов в единую таблицу:

исходящие деревья: $C=0$ (всё тривиально маршрутизируется);
двухслойные “хабы” (источник — склады — клиенты): $C=1$ , это известный результат; а мы ещё подпёрли его нижней границей $1-1/m$ , которую получили из классического семейства “m+1 работ”;
последовательно-параллельные графы (series-parallel): $C\le1$ (Almoghrabi, Skutella, Warode, 2026);
внешнепланарные двухвыходные интервальные хребты: $C=1$ ровно, и константа 1 здесь достигается уже одним терминалом.

А для планарных графов мы подняли нижнюю оценку. Построили новый интервальный пример с шестью терминалами, полным перебором $64$ маршрутизаций, точной смесью из семи атомов и сертификатом планарности через систему вращений:

У него

$C_{\text{planar}}\;\ge\;\frac{58676765987259}{50000000000000}\;=\;1.17353531974518,$

и мы знаем классическую верхнюю оценку 2. Забавно, что дальше по лестнице рекордов планарность немедленно заканчивается: уже пятитерминальная рекордная геометрия непланарна.

Как проверяли и как шёл процесс

Стандарт проверки во всех работах был один и тот же: каждое числовое утверждение проверяется в точной рациональной арифметике программой, которая пересобирает пример из списка дуг: заново находит все простые пути поиском в глубину, заново перечисляет маршрутизации, заново решает задачи линейного программирования. У каждого сертификата есть вторая, независимо написанная реализация проверки. Финальные доказательства классов и локальных констант все solver-free, то есть численный поиск разрешён только на стадии открытия новых примеров, и ни одно решение солвера не входит в доказательство как посылка. Все 37 новых сертификатов Части III лежат в репозитории, и приложение статьи объясняет по пунктам, что именно проверяет каждый файл.

И об ошибках, потому что они тоже были, и это нормально. За время проекта adversarial-проверки (вторая модель против первой, кампания против теоретика) поймали довольно много ошибок, в том числе “тождество” $C=1+\Delta$ , которое при внимательном взгляде оказалось одним и тем же неравенством, записанным дважды; красивое “следствие” про нечётные дыры, опровергнутое затем теоремой о сетевых матрицах; целое доказательство через округление вверх, и много чего другого.

В общем, доказательства от LLM безусловно нужно проверять, но конкретно в этом исследовании оказалось достаточно проверять их другой LLM: Claude ловил ошибки GPT и наоборот, и после пары таких раундов я уже никаких ошибок больше не находил (но всё равно искал! это важно!).

Теперь о процессе, потому что вопрос “как вы работаете с моделями” мне задают чаще, чем вопросы о потоках.

Работали три модели в разных ролях. GPT 5.6 Sol гоняла экспериментальные “кампании”: я (вместе с Claude) писал подробный бриф — какие гипотезы проверить, какие сертификаты сгенерировать, в каком формате отчитаться, — а Sol возвращалась с результатами, часто неожиданными. Claude Fable 5 и Claude Opus 5 занимались теорией, проверкой и текстом: верифицировали каждый раунд, доказывали, что доказывается вручную, ловили ошибки (свои, мои и чужие) и собирали статью.

Таких циклов “кампания — верификация — теория — новый бриф” было примерно восемь. Ключевые идеи — точные средние, сетевые матрицы, редукция к окну, четырёхцветное слияние — в основном предлагали модели; я выбирал направления, закрывал тупиковые ветви исследований, лично перепроверил и переписал все доказательства и, разумеется, несу ответственность за все оставшиеся ошибки.

В отличие от истории Рыбина, это не был one-shot tour de force; это был именно длинный совместный проект, и, кстати, чертовски интересный! Присоединяйтесь!

Что осталось открытым

Разумеется, мы не вполне всё закончили.

Существует ли конечная универсальная $C$ ? Главный вопрос стоит как стоял, но теперь он эквивалентен конечности оконной константы $K^\ast$ , и известно, что $K^\ast\ge2.5652$ .
Гипотеза $4/3$ : лестница рекордов двухпутевого класса, кажется, стремится к $4/3$ ; доказать (или опровергнуть) сходимость — самая близкая открытая цель.
Глобальная арность 3: локально $9/8$ , глобально доказано $2D$ ; правда где-то между.
Планарные графы: теперь $C\in [1.17353\ldots,\,2]$ , и обе границы выглядят улучшаемыми.
$E(5)$ и дальше: совпадут ли следующие ступени лестницы рекордов с точными локальными константами, как это случилось с $E(3)$ и $E(4)$ ?

Заключение

Месяц назад эта история начиналась с семи вершин и твита. Сейчас у неё три препринта, большая таблица рекордов с внешними контрибьюторами, репозиторий с машинно-проверяемыми сертификатами и ряд интересных верхних оценок для разных классов графов, причём константы контрпримеров оказались точными значениями в новой теории.

В постах про двойное покрытие циклами, якобиан и Диница — Гарга — Гёманса я писал про молниеносные результаты: одна гипотеза — один промпт — один документ. Этот пост — про другой, более прозаический и наверняка куда более массовый жанр: LLM как полноценные соавторы в долгом проекте, с разделением ролей, взаимной проверкой и накоплением результатов.

А что дальше, коллеги?

Сергей Николенко

P.S. Прокомментировать и обсудить пост можно в канале «Sineкура»: присоединяйтесь!

Всё течёт — и кое-что даже доказывается: неделимые потоки

Введение

Напоминание: гипотеза и треугольник

Хребты и терминалы с парой выходов

Часть II. Семнадцать терминалов с общим ребром

А нельзя ли чего-нибудь доказать?

Арифметика: делимость бесплатно, несравнимость нет

Вся задача свелась к одному окну

Геометрия: пары бесплатны, первый враг — треугольник

Раскраски, Property B и первый ответ для неограниченного класса

Классы графов и новый планарный рекорд

Как проверяли и как шёл процесс

Что осталось открытым

Заключение

Comments

Leave a Reply Cancel reply

More posts

Всё течёт — и кое-что даже доказывается: неделимые потоки

35MM и 7th Sector: игры Сергея Носкова

Tiny Bookshop: книжная лавка на колёсах

Былина

Вся задача свелась к одному окну $[n,2n]$