Dmitry Rybin (@DmitryRybin1)
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-0…
Jul 22, 2026 · 12:18 PM UTC
256
890
9,542
4,268,122
[](https://xcancel.com/DmitryRybin1/status/2079906232069177643#m)
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.
15
15
1,900
156,270
[](https://xcancel.com/DmitryRybin1/status/2079907499545919968#m)
The conjecture was based on absolutely stunning result of Dinitz, Garg, and Goemans: any fractional flow can be routed to unsplittable flow by violating graph capacities by at most max(demand). The chat with gpt pro here is an absolute meme
4
9
1,092
134,301
Sort replies: Relevant Recent Liked
[](https://xcancel.com/pranav%5Fso/status/2079981499823382807#m)
Replying to @DmitryRybin1
what was the file uploaded? was it non-trivially helpful in finding the solution?
2
50
10,619
[](https://xcancel.com/DmitryRybin1/status/2080343464235917814#m)
The file was this paper from arxiv
1
24
4,645
[](https://xcancel.com/btwphones/status/2080017509877682627#m)
Replying to @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
96
63,674
[](https://xcancel.com/DmitryRybin1/status/2080022912199766400#m)
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
4
4
411
57,437
[](https://xcancel.com/yacinelearning/status/2080277384226316684#m)
Replying to @DmitryRybin1
ah man this is so cool would love to interview you on what the overall workflow look like nice work!
12
5,911
[](https://xcancel.com/DmitryRybin1/status/2080323704593039867#m)
Thank you Yacine 🫡 Will try to find time these days
1
6
5,011
[](https://xcancel.com/phyrooo/status/2079920667936321674#m)
Replying to @DmitryRybin1
Please continue research and find a new conjecture to disprove.
2
125
12,920
[](https://xcancel.com/BA%5FWolf/status/2080010447672221859#m)
Replying to @DmitryRybin1
lol lmao even
112
8,249
[](https://xcancel.com/EttoreMariotti/status/2079966185093832820#m)
Replying to @DmitryRybin1
wake up babe, a new decades old problem have been solved by AI
1
79
8,193
[](https://xcancel.com/deanmckee757/status/2079944056021422333#m)
Replying to @DmitryRybin1 @srush\_nlp
Get wrecked, Dinitz, Garg, and Goemans
138
13,624
[](https://xcancel.com/Moritz%5F%5FGross/status/2080022148265996604#m)
Replying to @DmitryRybin1
average thesis advisor
5
312
11,392
[](https://xcancel.com/phelgo/status/2079957419610738785#m)
Replying to @DmitryRybin1
The future of Science, ladies and gentlemen.
6
80
1,644
74,405
[](https://xcancel.com/0xAvious/status/2080096856940347489#m)
Replying to @DmitryRybin1
the prompting is great but this 90 minute chain of thought is incredible
1
26
1,770
[](https://xcancel.com/jshobrook/status/2080079977400218107#m)
Replying to @DmitryRybin1
“Well since you asked politely…”
31
4,844
[](https://xcancel.com/felps%5Fbra/status/2079985409220645133#m)
Replying to @DmitryRybin1
lol
1
133
10,575
[](https://xcancel.com/KislayParashar1/status/2079957499558666395#m)
Replying to @DmitryRybin1
Thirty years of people trying to prove this and it breaks on a graph small enough to fit on a whiteboard, that's rougher than gpt finding it first honestly.
2
70
7,107
[](https://xcancel.com/android%5Fstern/status/2080047396843602026#m)
Replying to @DmitryRybin1
It was really that simple
3
135
5,249
[](https://xcancel.com/brayaON20/status/2080029519813988764#m)
Replying to @DmitryRybin1
The new scientific journal will be the LLMs sessions that showcase the conversation leading the proof of a result.
2
2
22
6,744
[](https://xcancel.com/ss04072012/status/2079911781821297134#m)
Replying to @DmitryRybin1
Woah that conversation is awesome .
38
8,397
[](https://xcancel.com/georgeramonov/status/2079948029671727246#m)
Replying to @DmitryRybin1 @srush\_nlp
do gaslight until breakthrough
1
39
11,281
[](https://xcancel.com/TimSweeneyEpic/status/2080060615310082535#m)
Replying to @DmitryRybin1
Thank you for sharing the source chat!
115
4,915
[](https://xcancel.com/thebitterlesson/status/2079981917269885039#m)
Replying to @DmitryRybin1
This approach remains undefeated
3
18
981
34,159
[](https://xcancel.com/wblazer%5F/status/2079944183360418272#m)
Replying to @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!"
7
41
1,527
60,380
[](https://xcancel.com/peeyuzz/status/2079975780764028932#m)
Replying to @DmitryRybin1
too much basedness for a next token predictor
1
20
1,387
41,275
[](https://xcancel.com/recurrentneural/status/2079943245224644877#m)
Replying to @DmitryRybin1
I am just lolling at the prompts. Hats off!
18
6,584
[](https://xcancel.com/kingofknowwhere/status/2079937763009511839#m)
Replying to @DmitryRybin1
This paper has 250 citations. How did you find it
22
7,333
[](https://xcancel.com/ShadowbanSlam/status/2079945962898751912#m)
Replying to @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.
19
246
29,710
[](https://xcancel.com/whocareslo4730/status/2079933196645355759#m)
Replying to @DmitryRybin1
that chat
3
29
1,096
52,338
[](https://xcancel.com/RighttoTryGuy/status/2080003730553098686#m)
Replying to @DmitryRybin1
4
11
387
22,865
[](https://xcancel.com/Archos%5FCasual/status/2080132491025813706#m)
Replying to @DmitryRybin1
Fun corollary: this same graph also kills the Morell–Skutella convex-combination conjecture. Each sink's zero-cost path is pinned by its terminal arc, so the "free ride" probabilities would sum to 1/3 + 2/5 + 1/3 = 16/15 — but the shared corridor allows at most one free rider. Can't have 107%. Verified by both my good friends Fable 5 and 5.6 Sol!
1
51
6,814
[](https://xcancel.com/Plinz/status/2080261834779639979#m)
Replying to @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.
29
4
110
10,593
[](https://xcancel.com/hankakuspace7/status/2080129573564657686#m)
Replying to @DmitryRybin1
I, too, have (likely) discovered a counterexample to a recent conjecture on line-graph inertia by using GPT 5.6! What makes this interesting is that the AI selected both the topic and the solution method; I do not even fully grasp the meaning of the problem itself.
1,502
[](https://xcancel.com/ing%5Fernesto%5Fgwu/status/2080002121370370297#m)
Replying to @DmitryRybin1
Ok. Enough please. Couldn't the President of Math please a bidaily summary briefing of the conjectures that have already been disproven in Twitter/X, so that we all VibeMathematicians know where to put our tokens to work?
[](https://xcancel.com/DmitryRybin1/status/2079904005652893709#m)
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-0…
1
2,460
[](https://xcancel.com/DmitryRybin1/status/2079904005652893709#m)