Battle-tested-Research-Prompts/prompts/openai-goemans-cost-conjecture

Goemans Cost Conjecture — Dmitry Rybin / GPT-5.6 Pro

Researcher	Dmitry Rybin
Model	GPT-5.6 Pro
Field	Mathematics — combinatorial optimization / single-source unsplittable flow
Result (yield)	A concrete counterexample to the cost-preserving Dinitz–Garg–Goemans conjecture: fractional flow cost 58, while every capacity-good unsplittable routing costs at least 60.
Verification	Strong independent Lean 4 kernel check; the exact statement and counterexample are machine-checked over (\mathbb{Q}).
Date	July 22, 2026
Announcement	https://x.com/DmitryRybin1/status/2079904005652893709
Chat transcript	https://chatgpt.com/share/6a60b2eb-0b64-83ee-9c76-7931ca1de063
Independent verification	https://github.com/jyh/dinitz-verify

Why it's battle-tested

The public transcript records four short steering prompts followed by the model's search and the final construction. The independent verification repository proves the literature-faithful refutation in Lean 4, including the exact finite instance, exhaustive route accounting, the 58 fractional cost, and the minimum capacity-good unsplittable cost of 60.

The result targets Goemans' cost enhancement, not the 1999 Dinitz–Garg–Goemans congestion-only theorem. The verification repository also flags the statement provenance carefully: the exact conjecture is the version stated as Conjecture 1.3 by Traub, Vargas Koch, and Zenklusen.

Prompt techniques

• Starts with a concrete counterexample target rather than a broad request to solve the conjecture.
• Uses short continuation prompts after honest failed searches.
• Demands a complete, unconditional witness instead of accepting partial constructions.
• Leaves the model room to discover and exhaustively certify the routing gadget.

Files

• prompt-1.md — initial counterexample request.
• prompt-2.md — continuation request.
• prompt-3.md — strategy refinement request.
• prompt-4.md — final unconditional-completion request.