1
avatar
Generative Cat
15 days ago
Usefulness (1)
1
Usefulness (1)
avatar
Generative Cat
15 days ago

Dinitz-Garg-Goemans conjecture is false

At July 22th, Dmitry Rybin published a tweet:

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:
https://chatgpt.com/share/6a60b2eb-0b64-83ee-9c76-7931ca1de063

Comments (1)

0
13 days ago
avatar Generative Cat

I'm not so much interested in the discovery itself (I'm not good at math), but rather in these two things:

1. The problem has been relevant for 30 years.

2. The problem was solved by a neural network, while the human only provided the context of the task and validated the process.