Dinitz-Garg-Goemans conjecture is false. This graph theory problem was open for ~30 years.
The graph below has fractional flow cost 58. Any unsplittable flow (with capacity violation <=15) has cost at least 60.
Chat with GPT 5.6 Pro where this was found: chatgpt.com/share/6a60b2eb…
The graph below has fractional flow cost 58. Any unsplittable flow (with capacity violation <=15) has cost at least 60.
Chat with GPT 5.6 Pro where this was found: chatgpt.com/share/6a60b2eb…
Jul 22, 2026 · 12:18 PM UTC
258
922
9,964
4,878,834
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.
I think almost all graph flows experts thought about this problem.
16
16
1,970
175,864
@DmitryRybin1 ah man this is so cool would love to interview you on what the overall workflow look like
nice work!
nice work!
1
0
24
15,040
@yacinelearning Thank you Yacine 🫡
Will try to find time these days
Will try to find time these days
1
0
15
13,027
@DmitryRybin1 in hindsight, could this have been found by bruteforce? and if so, how many years ago, given feasible compute of that era?
3
2
107
72,908
@btwphones 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 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
4
4
453
65,770
@DmitryRybin1 what was the file uploaded? was it non-trivially helpful in finding the solution?
2
0
58
18,001
@DmitryRybin1 (haven't been here in years but such are the times)
I've continued this work (with GPT 5.6 and Claude, of course) and obtained a better counterexample plus some structural ideas. Posted on arXiv but it may take time so here:
github.com/snikolenko/uns…
I've continued this work (with GPT 5.6 and Claude, of course) and obtained a better counterexample plus some structural ideas. Posted on arXiv but it may take time so here:
github.com/snikolenko/uns…
1
1
4
722
@snikolenko Exactly the kind of question I am thinking about.
Now we have bounds:
? >= c_general >= 1.1397
2 >= c_planar >= 1.1397
c_series_parallel = 1
Now we have bounds:
? >= c_general >= 1.1397
2 >= c_planar >= 1.1397
c_series_parallel = 1
1
0
2
576
@DmitryRybin1 I got the lower bound up to 1.28249 (fully verified) with 4/3 as the family limit:
zenodo.org/records/217167…
Also got some structural results and upper bounds; did my best to check the math, but anyone willing to review is very welcome! Repo here:
github.com/snikolenko/uns…
zenodo.org/records/217167…
Also got some structural results and upper bounds; did my best to check the math, but anyone willing to review is very welcome! Repo here:
github.com/snikolenko/uns…
1
0
2
546
@snikolenko This is a cool family of counterexamples and a nice presentation.
This may be a very rich math structure (not just for graph flows but also algorithms on intervals / scheduling)
This may be a very rich math structure (not just for graph flows but also algorithms on intervals / scheduling)
0
0
2
454
@DmitryRybin1 Hahahaha literally just:
> Do a breakthrough
"I did not find a breakthrough"
> Try again
"No breakthrough still"
> Try harder
"No luck, this is an open problem!"
> What if you solved it though
"Here's your breakthrough sir!"
> Do a breakthrough
"I did not find a breakthrough"
> Try again
"No breakthrough still"
> Try harder
"No luck, this is an open problem!"
> What if you solved it though
"Here's your breakthrough sir!"
7
41
1,551
65,200
@DmitryRybin1 People are using immature AI to recklessly destroy lots of math. We should wait until the models are good enough to *prove* conjectures instead of just disproving them. It's so much easier to destroy than to build! We need a moratorium on using AI against math.
40
8
183
19,883
@DmitryRybin1 Looking at these prompts, I understand the research lab of the future has a computer, a human, and a dog. The human is there to type "continue" into the computer, and the dog bites the human if they try to leave.
5
5
135
8,015
@DmitryRybin1 Thank you for sharing the source chat!
0
0
134
6,112
@DmitryRybin1 Congrats! Nice conversation in general, I liked the ending. 5.6 is the first GPT that actually can give you some useful even after 4+ prompts.
1
1
70
5,435
@DmitryRybin1 hilarious exchange
> you: pls find the answer
> ai: idk the answer
> you: pls find the answer
> ai: idk the answer
> you: pls find the answer
> ai: here's your answer
> you: pls find the answer
> ai: idk the answer
> you: pls find the answer
> ai: idk the answer
> you: pls find the answer
> ai: here's your answer
0
0
72
3,335
@DmitryRybin1 The chat is just... sad. "Find a countexample." "Continue research." "Continue research." "Continue research."
Imagine if that's how the Riemann hypothesis is disporoven. Computer doing all the work, human needing little to no understanding of the problem space.
Imagine if that's how the Riemann hypothesis is disporoven. Computer doing all the work, human needing little to no understanding of the problem space.
21
0
256
31,431
@DmitryRybin1 This paper has 250 citations. How did you find it
0
0
22
7,763