In contrast to Kerger’s 10-page effortprompt, Dmitry Rybin basically just said “do a breakthrough”.
I know counterexamples to old conjectures are becoming a meme at this point. But I really cared about this problem and spent many weeks thinking about it a while ago (in both directions, proof and disproof).
I think almost all graph flows experts thought about this problem.
Ben Stephens: in hindsight, could this have been found by bruteforce? and if so, how many years ago, given feasible compute of that era?
Dmitry: Not really.
I tried brute force search myself and with old LLMs too (o1/o3). The problem is there are many degrees of freedom: costs, flows, demands to nodes. so even tiny graphs have enormous number of combinations of these params
I don’t think that conjecture is too famous, so it shouldn’t be surprising given the past results from AI. I see it as (effort prompt → very difficult discovery) → (non effort prompt → somewhat difficult discovery)
GPT 5.6: “Recent papers explicitly call it a “famous conjecture,” but that fame is local to combinatorial optimization and approximation algorithms.”
Disproving the Dinitz-Garg-Goemans conjecture with GPT 5.6 Pro, a story in four acts:
In contrast to Kerger’s 10-page effortprompt, Dmitry Rybin basically just said “do a breakthrough”.
I don’t think that conjecture is too famous, so it shouldn’t be surprising given the past results from AI. I see it as (effort prompt → very difficult discovery) → (non effort prompt → somewhat difficult discovery)
GPT 5.6: “Recent papers explicitly call it a “famous conjecture,” but that fame is local to combinatorial optimization and approximation algorithms.”