arXiv:2611.23244v1 cs.LG

고망스의 분할 불가능 흐름 추측: AI 지원 반례 발견의 해부

Goemans's Unsplittable-Flow Conjecture: The Anatomy of AI-Assisted Counterexample Discovery

Jingwei Ge, Na Xie, Li Li, Jiayang Li

제출 2026-11-19

한국어 초록

고망스(Goemans)는 임의의 분수 단일 소스 흐름이 총비용을 증가시키지 않으면서, 어떤 호의 부하도 최대 수요량 이상으로 증가시키지 않고 분할 불가능 흐름으로 변환될 수 있다고 추측하였다. 최근 드미트리 리빈(Dmitry Rybin)은 ChatGPT와의 상호작용을 통해 찾은 7개 정점의 반례를 발표하여 이 오랜 추측을 반증하였다. 그러나 그 상호작용은 왜 이 특정한 위상과 그 수요, 분수 흐름, 비용의 선택이 함께 작동하는지, 이 예가 더 넓은 계열에 속하는지, 어떤 구조적 특징이 반례가 나타날 수 있는 위치를 결정하는지를 밝히지 못했다. 또한 이전의 인간의 노력이 실패한 곳에서 AI 지원 탐색이 왜 성공했는지도 불분명하게 남겼다. 본 논문에서는 순방향 반례 구성 파이프라인을 개발한다. 이는 실패가 불가능한 수지상 구조(arborescence)에서 출발하여 종단으로 들어가는 지름길 호를 추가한다. 그 결과로 나오는 부하 제약은 허용 가능한 경로 선택의 유한 집합을 정의하며, 그 볼록 껍질인 충돌 다면체는 수요, 분수 흐름, 비용에 대한 정확한 조건을 제공한다. 단순한 수지상 구조에서 시작하여 이 파이프라인은 리빈의 위상을 선택하고 그것이 뒷받침하는 모든 반례를 규명한다. 실험은 이 파이프라인의 이전 가능성도 보여준다. 초기 수지상 구조와 지름길 배치를 바꾸면서 이를 따르도록 지시했을 때, ChatGPT는 리빈의 것과 실제로 다른 위상에서 반례를 생성했고 93개의 다른 뿌리 있는 수지상 구조 형태에서 출발하여 유효한 구성을 찾았다. 이 이론은 또한 원래의 예가 무작위 열거로 발견하기 어려웠던 이유를 설명하고, 리빈의 상호작용이 무작위 열거와 이론 주도의 완전한 구성 사이에 놓여 있음을 시사한다.

원문 초록

Goemans conjectured that any fractional single-source flow could be converted into an unsplittable flow without increasing total cost and while increasing any arc load by at most the largest demand. Recently, Dmitry Rybin announced a seven-vertex counterexample found through an interaction with ChatGPT, which disproved this long-standing conjecture. However, the interaction did not reveal why this particular topology and its demand, fractional-flow, and cost choices work together, whether the example belongs to a broader family, or which structural features determine where counterexamples can occur. It also left unclear why the AI-assisted search succeeded where earlier human efforts had not. In this paper, we develop a forward counterexample construction pipeline. It starts from an arborescence on which failure is impossible and adds terminal-entering shortcut arcs. The resulting load constraints define a finite set of admissible route choices; their convex hull, the conflict polytope, yields exact conditions for demands, fractional flows, and costs. Starting from a simple arborescence, the pipeline selects Rybin's topology and characterizes all counterexamples it supports. Experiments further demonstrate the pipeline's transferability: when instructed to follow it while varying the initial arborescence and shortcut placement, ChatGPT produced counterexamples on topologies genuinely different from Rybin's and found valid constructions starting from 93 other rooted arborescence shapes. The theory also explains why the original example was difficult to discover through blind enumeration and suggests that Rybin's interaction lies between blind enumeration and a complete theory-guided construction.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.23244v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.