Всё течёт, всё опровергается: гипотеза Диница — Гарга — Гёманса

24 июля 2026 г.

Введение

В прошлый раз, рассказывая про контрпример к проблеме якобиана, я закончил пост вопросом: “Что дальше, коллеги?”

Ответ занял два дня.

22 июля Дмитрий Рыбин написал в X, что GPT 5.6 Pro опровергла гипотезу Диница — Гарга — Гёманса (Dinitz–Garg–Goemans conjecture) из теории потоков в графах. Гипотеза простояла с конца 1990-х; в статье 2025 года Swamy et al. всё ещё называли её “a famous conjecture” и писали, что даже существенно ослабленный вариант был бы прорывом.

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

Более того, контрпример оказался не просто верным, а очень интересно устроенным. Внутри него прячется известный в комбинаторной оптимизации объект — треугольник попарных конфликтов.

Давайте разберёмся, что такое делимые и неделимые потоки и в чём состояла гипотеза. Потом обсудим, почему она казалась естественной и почему её было так трудно доказать. Затем проверим контрпример, вытащим из него структурную идею и попробуем его уменьшить. А в конце, разумеется, посмотрим на промпты. Спойлер: там буквально написано “you should do a breakthrough”.

Потоки, которые можно и нельзя делить

Начнём с обычной транспортной сети. Есть ориентированный граф $G=(V,A)$ : вершины — перекрёстки или маршрутизаторы, дуги — дороги или каналы связи. У нас есть один общий источник $s$ , например склад, и несколько терминалов $t_1,\ldots,t_k$ , куда надо доставить грузы объёмов $d_1,\ldots,d_k$ .

У каждой дуги $a$ есть пропускная способность $u_a$ : больше этого количества груза одновременно по ней отправлять нельзя. Может быть и неотрицательная цена $c_a$ за перевозку одной единицы груза.

В более простой постановке задачи грузы можно делить, то есть, например, заказ объёма 10 разрешается разрезать на части: пять единиц поехали по одному пути, три по другому, две по третьему. Такой поток называется делимым или дробным (splittable, fractional flow). В каждой внутренней вершине выполняется закон сохранения: сколько потока вошло, столько и вышло; источник выпускает сумму всех заказов, а терминал $t_i$ поглощает ровно $d_i$ .

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

Но во многих задачах груз делить нельзя. Контейнер должен ехать целиком, сетевое соединение должно выбрать один маршрут, задачу на вычислительном кластере нельзя на 37% выполнить на одном сервере и на 63% на другом. Тогда для каждого терминала $t_i$ надо выбрать один путь $P_i$ из $s$ в $t_i$ и отправить по нему все $d_i$ единиц. Это неделимый поток (unsplittable flow).

Если через дугу $a$ проходят пути терминалов из множества $I$ , нагрузка на неё равна

$y_a = \sum_{i\in I} d_i.$

А полная стоимость маршрутизации равна

$\mathbf{c}^\top \mathbf{y} = \sum_{a\in A} c_a y_a.$

Очевидно, что разница между двумя постановками есть, и немалая. Представьте один заказ объёма 10 и две дороги, по которым дробный поток отправляет по пять единиц. После запрета деления придётся выбрать одну дорогу и положить на неё все десять. Нагрузка на выбранную дорогу вырастет скачком на пять.

Такое неизбежно происходит и в общем случае. Поэтому разумный вопрос здесь в том, насколько сильно придётся перегружать дуги. Обозначим максимальный размер заказа (demand, ещё переводят как “потребность” или “запрос”) через

$d_{\max}=\max_i d_i.$

Запас в один максимальный заказ выглядит естественно: если в процессе округления на дуге оказался один целый груз, хуже $d_{\max}$ он добавить не может. Именно это наблюдение превратилось в нашу сегодняшнюю гипотезу.

Теорема Диница — Гарга — Гёманса

Задачу о неделимом потоке из одного источника ввёл Джон Клейнберг в работе 1996 года. Даже решить, существует ли неделимая маршрутизация, соблюдающая все ёмкости, NP-трудно; как отмечают авторы современного обзора, уже на графе из двух вершин с параллельными дугами сюда сводятся Subset Sum и Bin Packing.

Но Ефим Диниц, Навин Гарг и Мишель Гёманс в работе “On the Single-Source Unsplittable Flow Problem” доказали важную теорему.

Теорема (Dinitz–Garg–Goemans, 1999). Пусть $\mathbf{x}$ — любой допустимый дробный поток. Тогда за полиномиальное время можно найти неделимый поток $<em>\mathbf{</em>y}$ , для которого на каждой дуге

$y_a \leq x_a + d_{\max}.$

Если исходный поток соблюдает ёмкости, $x_a\leq u_a$ , то, следовательно,

$y_a\leq u_a+d_{\max}.$

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

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

Гипотеза Гёманса. Если на дугах заданы неотрицательные цены $c_a$ , то неделимый поток $\mathbf{y}$ можно выбрать так, чтобы одновременно не слишком перегружались дуги,

$y_a \leq x_a+d_{\max}\quad\text{для всех }a,$

и не увеличивалась общая цена,

$\mathbf{c}^\top \mathbf{y}\leq \mathbf{c}^\top \mathbf{x}.$

Иногда её называют гипотезой Диница — Гарга — Гёманса по имени исходной теоремы, а иногда просто Goemans’ conjecture; важно, что теорема трёх авторов без стоимостей остаётся в силе, опровергнуто именно стоимостное усиление.

Почему в гипотезу верили и почему она была сложной

У гипотезы была очень убедительная вероятностная интуиция.

Разложим дробный поток каждого терминала по путям. Долю потока на пути можно воспринимать как вероятность выбрать этот путь целиком. Если независимо выбрать по одному пути для каждого терминала, то в среднем нагрузка на каждой дуге будет ровно $x_a$ , а средняя стоимость — ровно $\mathbf{c}^\top \mathbf{x}$ .

Значит, среди всех исходов точно есть хотя бы один со стоимостью не выше средней. С другой стороны, теорема Диница — Гарга — Гёманса гарантирует, что есть исход, в котором все нагрузки не превосходят $x_a+d_{\max}$ .

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

Конечно, здесь нет формального доказательства: из “существует дешёвый поток” и “существует поток без большой перегрузки” не следует, что существует поток одновременно дешёвый и без большой перегрузки. Именно так устроен новый контрпример.

Но до него эта надежда выглядела вполне разумной. Многие классические методы зависимого округления умеют сохранять линейную целевую функцию и одновременно контролировать ошибки в ограничениях. Для специальных случаев получались положительные результаты: например, Skutella (2002) доказал гипотезу, когда все заказы кратны друг другу, точнее, образуют цепочку делимости (см. также Morell, Skutella, 2022).

При этом прогресса в общем случае почти не было. В 2023 году Traub, Koch, Zenklusen писали, что не известно практически ни одного нетривиального класса графов, где точная гипотеза была бы доказана. Они получили важный результат для планарных графов, но только с вдвое большим запасом:

$y_a\leq x_a+2d_{\max},\qquad \mathbf{c}^\top \mathbf{y}\leq \mathbf{c}^\top \mathbf{x}.$

Даже в работе октября 2025 года вопрос, можно ли сохранять стоимость хотя бы с добавочной перегрузкой $O(d_{\max})$ в общих графах, назывался “широко открытым”, а его решение — потенциальным прорывом. Я нашёл только один (совсем недавний, 29 июня 2026!) результат Almoghrabi, Skutella & Warode, где гипотеза Гёманса доказывается для нетривиального класса: последовательно-параллельных ориентированных графов, причём даже в более общей многоисточниковой постановке.

Почему это вообще так сложно? Потому что дробный поток живёт в выпуклом многограннике и оптимизируется линейными методами, а неделимый поток — это дискретный выбор целого пути для каждого терминала. Один выбор меняет нагрузки сразу на всех дугах пути; разные терминалы связываются через длинные общие куски маршрутов, а ограничение в $d_{\max}$ не даёт усреднить ошибку по размеру графа. Надо одновременно попасть в тонкую полосу вокруг $x$ по каждой дуге и не испортить одну глобальную цену.

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

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

Тем любопытнее, что итоговый контрпример можно нарисовать на салфетке.

Семь вершин и девять дуг

Вот весь граф. Число $x$ на дуге — нагрузка дробного потока, $c$ — цена одной единицы; у непомеченных цен значение нулевое. Двойными кружками отмечены терминалы.

Заказы трёх терминалов равны

$d_1=15,\qquad d_2=10,\qquad d_3=15,$

поэтому $d_{\max}=15$ .

Сначала проверим, что нарисованные числа действительно задают дробный поток. Из источника выходит

$10+6+24=40=15+10+15.$

В трёх внутренних вершинах поток сохраняется:

$24=10+14,\qquad 14=5+9,\qquad 9=4+5.$

Наконец, в терминалы приходит ровно столько, сколько требуется:

$10+5=15,\qquad 6+4=10,\qquad 10+5=15.$

Стоимость положительна только на трёх оранжевых дугах:

$\mathbf{c}^\top \mathbf{x}=2\cdot10+3\cdot6+2\cdot10=58.$

Можно посмотреть на тот же поток отдельно для каждого терминала. У каждого груза есть ровно два пути — дорогой $E_i$ и бесплатный $Z_i$ :

$\begin{aligned}E_1&:s\to t_1, &Z_1&:s\to u\to v\to t_1,\\E_2&:s\to t_2, &Z_2&:s\to u\to v\to w\to t_2,\\E_3&:s\to u\to t_3, &Z_3&:s\to u\to v\to w\to t_3.\end{aligned}$

Обратите внимание, что $E_3$ тоже проходит по бесплатной дуге $s\to u$ , но платит на дуге $u\to t_3$ .

Дробный поток раскладывается так:

Каждый дорогой путь, если отправить по нему соответствующий груз целиком, стоит ровно 30:

$15\cdot2=30,\qquad 10\cdot3=30,\qquad 15\cdot2=30.$

Поэтому стоимость 58 можно пересчитать ещё одним способом:

$30\left(\frac{10}{15}+\frac6{10}+\frac{10}{15}\right)=30\left(\frac23+\frac35+\frac23\right)=58.$

А теперь запретим делить грузы. Для каждого терминала надо выбрать либо $E_i$ , либо $Z_i$ . Всего получается $2^3=8$ вариантов. И 58 превращается в 60 из-за трёх арифметических конфликтов.

Конфликт $Z_2$ и $Z_3$ . Если второй и третий грузы одновременно идут по бесплатным путям, на дугу $v\to w$ ложится

$10+15=25.$

Но гипотеза разрешает там не больше

$x_{vw}+d_{\max}=9+15=24.$

Перегрузка — одна единица.

Конфликт $Z_1$ и $Z_3$ . Эти два пути вместе дают на дуге $u\to v$

$15+15=30>14+15=29.$

Снова не хватает ровно одной единицы.

Конфликт $Z_1$ и $Z_2$ . Тут надо вспомнить, что третий груз проходит по дуге $s\to u$ на обоих своих путях, и дорогом, и бесплатном. Поэтому вместе с $Z_1$ и $Z_2$ нагрузка на $s\to u$ неизбежно равна

$15+10+15=40>24+15=39.$

И опять разность равна единице.

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

$30+30=60>58.$

Вот и всё опровержение.

Для полноты выпишем все восемь вариантов. Слово bad означает, что после разрешённой добавки $d_{\max}=15$ какая-то дуга всё равно перегружена:

E1 E2 E3   cost 90   good
E1 E2 Z3   cost 60   good
E1 Z2 E3   cost 60   good
Z1 E2 E3   cost 60   good
E1 Z2 Z3   cost 30   bad: v→w by 1
Z1 E2 Z3   cost 30   bad: u→v by 1
Z1 Z2 E3   cost 30   bad: s→u by 1
Z1 Z2 Z3   cost  0   bad: s→u by 1, u→v by 11, v→w by 1

Все четыре маршрутизации стоимостью меньше 60 нарушают ограничения, а все четыре, которые ограничения соблюдают, стоят 60 или 90.

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

Кстати, граф не только ацикличен, но и планарен. Если забыть направления и разгладить три вершины степени 2, получится вообще $K_4$ , полный граф на четырёх вершинах. Это тоже по-своему интересно, потому что по планарности могла бы проходить граница между верным и неверным утверждением, и Рыбин изначально просил найти контрпример для общего, непланарного случая, но GPT 5.6 в итоге нашёл и более сильный.

Всё это, разумеется, не противоречит планарному результату 2023 года. Там разрешён зазор $2d_{\max}$ , а не $d_{\max}$ , и при таком запасе в нашем примере можно отправить все три груза по бесплатным путям и получить стоимость ноль.

Что там происходит на самом деле

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

Введём переменную $z_i$ , равную 1, если терминал $i$ выбирает бесплатный путь $Z_i$ , и 0, если дорогой $E_i$ . Три конфликта говорят:

$z_1+z_2\leq1,\qquadz_1+z_3\leq1,\qquadz_2+z_3\leq1.$

Для нулей и единиц отсюда следует

$z_1+z_2+z_3\leq1.$

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

А какие значения $z_i$ соответствуют дробному потоку? Это доли грузов, отправленные по бесплатным путям:

$z_1=\frac5{15}=\frac13,\qquadz_2=\frac4{10}=\frac25,\qquadz_3=\frac5{15}=\frac13.$

Каждое попарное неравенство выполнено. Но сумма равна

$\frac13+\frac25+\frac13=\frac{16}{15}>1.$

Из-за этого неравенства и ломается гипотеза. Дробный поток живёт в обычной релаксации, где есть три попарных конфликта, но не видна их общая “треугольная” связь. Неделимая маршрутизация обязана удовлетворять более сильному неравенству суммы.

А цены на дугах — просто разделяющая гиперплоскость. Поскольку каждый дорогой выбор стоит 30, стоимость равна

$30\bigl((1-z_1)+(1-z_2)+(1-z_3)\bigr).$

У дробной точки получается 58, а у любой целой точки с $z_1+z_2+z_3\leq1$ — не меньше 60.

В таком виде контрпример уже не кажется случайным. GPT 5.6 не просто наткнулся на девять удачных чисел, а реализовал в маленьком ориентированном графе классический разрыв между дробным и целым многогранниками для треугольника.

Это заодно объясняет, почему двух терминалов для этого механизма недостаточно. У одного конфликтного ребра неравенство $z_1+z_2\leq1$ уже полностью описывает выпуклую оболочку допустимых точек. Первое недостающее ограничение возникает именно на треугольнике, то есть нужны три бесплатных варианта. Я не утверждаю, что семь вершин абсолютно минимальны среди всех мыслимых контрпримеров (для этого нужен отдельный перебор топологий, и его ещё никто вроде бы не сделал), но структурное ядро здесь действительно самое маленькое возможное.

Проверка, уменьшение контрпримера и граница $9/8$

Проверка. Главная опасность в проверке подобных конструкций — перебрать только заранее задуманные пути и забыть, что их куски можно склеить в новый маршрут. Судя по опубликованному диалогу, несколько ранних попыток GPT 5.6 именно на этом и сломались.

Поэтому в проверочном скрипте мы с тем же GPT 5.6 не задавали шесть путей руками, а перебирали все простые пути из $s$ в каждый терминал. Впрочем, здесь всё-таки негде ошибиться, получится именно шесть путей:

t1: s→t1
t1: s→u→v→t1
t2: s→t2
t2: s→u→v→w→t2
t3: s→u→t3
t3: s→u→v→w→t3

После этого декартово произведение трёх двухэлементных списков даёт восемь маршрутизаций из таблицы выше.

Можно ли уменьшить числа? Да. На последней странице сертификата выписано целое параметрическое семейство. Я перебрал его рациональные и целочисленные варианты и нашёл меньший целочисленный экземпляр на том же графе:

заказы $(9,7,9)$ , так что $d_{\max}=9$ ;
по бесплатным путям дробно идут $(2,4,2)$ единицы;
единичные цены трёх платных дуг равны $(7,9,7)$ .

Тогда каждый дорогой путь целиком стоит 63, дробная стоимость равна

$7\cdot7+3\cdot9+7\cdot7=125,$

а любая допустимая неделимая маршрутизация стоит хотя бы

$63+63=126.$

Три попарных конфликта снова превышают разрешённую границу ровно на единицу. В этой же семивершинной схеме, если требовать целые заказы и нагрузки и уравнять полную цену трёх дорогих выборов, $d_{\max}=9$ минимально; перебор меньших значений не даёт ни одного варианта, а при 9 решение $(9,7,9)$ единственно.

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

Рассмотрим ослабленную гипотезу, где разрешается

$y_a\leq x_a+\alpha d_{\max}.$

В исходном примере любая маршрутизация стоимостью не больше 58 должна выбрать хотя бы два бесплатных пути. Для каждого такого выбора на конфликтной дуге нагрузка превосходит $x_a$ на 16, то есть требуется

$\alpha\geq\frac{16}{15}.$

В уменьшенном примере требуется уже

$\alpha\geq\frac{10}{9}.$

А параметрическое семейство позволяет подойти ещё ближе к $9/8$ . Нормируем первый и третий заказы к 1, снова уравняем полную стоимость трёх дорогих путей и положим

$d_2=b=\frac34,\qquad r=\frac14,\qquad q=\frac12+\varepsilon,\qquad 0<\varepsilon<\frac16,$

где $b,q,r$ — доли трёх грузов на бесплатных путях. Их суммарная дробная масса равна $1+\varepsilon>1$ . Если каждый дорогой путь целиком стоит $C$ , дробная стоимость равна $C(2-\varepsilon)<2C$ , поэтому сохраняющая стоимость маршрутизация обязана выбрать хотя бы два бесплатных пути. В то же время любой такой выбор требует коэффициента

$\alpha=\frac98-\frac34\varepsilon.$

Беря положительное рациональное $\varepsilon$ сколь угодно малым, получаем контрпример для любого универсального коэффициента $\alpha<9/8$ .

Иными словами, для планарных графов естественный вопрос теперь звучит так: какой будет оптимальный “коэффициент невязки” между $9/8$ и 2? Верхняя граница 2 известна из работы 2023 года, нижняя $9/8$ получается уже из этой маленькой планарной конструкции.

Для общих графов картина ещё менее понятна: неизвестно даже, достаточно ли вообще какой-нибудь универсальной константы при $d_{\max}$ с одновременным сохранением стоимости. Так что хоть исходная гипотеза и пала, работа здесь ещё не вполне закончена.

Четыре промпта

Ну и наконец — как это было найдено.

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

You should do a breakthrough.

Модель долго исследовала разные конструкции, выдавала частичные результаты и несколько раз не доходила до корректного ответа. Рыбин отвечал коротко и не пытался даже разобраться в том, что модель писала, по существу. После “Research conclusion” идут несколько страниц текста, но дальше диалог продолжается так:

Двух промптов не хватило, и GPT 5.6 опять сдался (через полтора часа размышлений), но третий промпт всё ещё прямолинеен:

И даже трёх промптов и пяти часов размышлений — о ужас! — не хватило. Так что Дмитрий Рыбин потерял терпение и написал коротко и прямо:

Как видите, на четвёртый раз невод, pardon the pun, пришёл с золотою рыбкой. Всего четыре коротких сообщения, никакого “искусства промптинга”. Опять же, я так

Разумеется, из этого не следует, что математическая экспертиза больше не нужна. Чтобы вообще выбрать эту гипотезу, надо знать, что она важна и открыта и иметь некоторую интуицию о том, что именно она может оказаться неверной. Дмитрий Рыбин действительно много думал над задачей сам.

Но и преуменьшать роль модели здесь странно. Человек не подсказывал LLM граф, числа или даже идею треугольника конфликтов. Финальная конструкция появилась после нескольких часов самостоятельного поиска, а пользовательская обратная связь состояла из “продолжай” и “хватит частичных результатов”.

Заключение

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

GPT 5.6 Pro нашла планарный ациклический граф с тремя терминалами, где дробный поток стоит 58, а любой неделимый поток в разрешённых границах стоит не меньше 60. Сертификат состоит из девяти дуг и восьми строк полного перебора; я независимо проверил и арифметику, и отсутствие дополнительных путей.

Главная идея контрпримера — не сами числа, а треугольник конфликтов. Дробный поток использует три бесплатных выбора с суммарной массой $16/15$ , хотя целиком можно выбрать не больше одного. Цены лишь переводят недостающее неравенство $z_1+z_2+z_3\leq1$ в разрыв между 58 и 60.

Теорема Диница, Гарга и Гёманса без стоимостей остаётся верна. Планарный результат с запасом $2d_{\max}$ тоже остаётся верен. И теперь появляется некоторый зазор, который можно пытаться сокращать: как мы тут увидели, та же конструкция показывает, что любой новый универсальный коэффициент должен быть не меньше $\frac 98$ , то есть теперь можно сокращать расстояние между $\frac 98$ и $2$ .

За три последних поста мы увидели сначала двухстраничное доказательство гипотезы о двойном покрытии циклами, потом многочлен, помещающийся в твит, а теперь — контрпример в виде стандартного треугольника целочисленной оптимизации. Но каждый из этих кажущихся простыми результатов закрыл гипотезу, над которой действительно думало много живых математиков.

У меня нет сомнений, что если бы любой из этих результатов получил человек, он стал бы широко известен в узких кругах и всегда имел бы гарантированную профессорскую позицию в хорошем месте, даже если бы больше ничего великого не сделал и продолжал бы всю жизнь изучать следствия и расширения своего прорывного результата (таких примеров в науке много, это не что-то плохое). Так что вопрос о том, достигли ли AI-модели человеческого уровня в математике, кажется мне уже закрытым.

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

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

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