The Papamanthou-Tollis Conjecture on Parameterized st-Orientations
Statement
On the basis of experiments up to 5000 nodes, Papamanthou and Tollis conjectured a relation between the longest paths produced by their MaxSTN and MinSTN algorithms for -orientations of biconnected graphs. A counterexample refutes it.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
construction · #1
Charalampos Papamanthou, using Claude Sonnet 4.6That credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.
The paper devotes a section to this and it is worth reading in full, because the headline line is the least of it. Claude Sonnet 4.6 read the earlier paper and wrote the Python st-orientation code quickly, and the authors say no code was written by a human. But the loop mattered: the authors caught and fed back three specific bugs, cut vertices being treated as eligible, the sink block not being excluded, and the timestamp overwrite rule implemented incorrectly. The model ran exhaustive tests for , declined as computationally infeasible, then later suggested a resource that would have made it possible. It also produced counterexamples that external validation confirmed were wrong, and drew conclusions the authors state they did not verify, including an exhaustive-search claim over the biconnected graphs on five and six vertices. The counterexample that survived is the model's; so is a quantity of discarded work. The author is one of the two who posed the conjecture, so this is someone refuting their own with a model.
Recorded elsewhere on #1 · not checked here
recorded: correctVibeMathed site checkscope Reproduction by the VibeMathed site
The refutation is an explicit graph, so it reduces to running the two named algorithms on it, and that part stands on its own. The surrounding computational claims deserve less weight: in the same section the authors record that the model produced counterexamples later confirmed wrong, and that they did not verify its claim to have exhaustively searched the biconnected graphs on five and six vertices. arXiv note, not peer-reviewed.
Repeated from the source; nothing was checked here.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.