The Papamanthou-Tollis Conjecture on Parameterized st-Orientations
Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.
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.
Context
A conjecture from the Papamanthou-Tollis st-orientation papers, based on extensive experiments and standing since 2008.
People
Projects
Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.
Interest
Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.
Attempts
No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.
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.
Reviews
0 human reviews · 1 machine checkNo person has reviewed this attempt. 1 machine check below — a machine check is not human verification.
Machine check · not human verification
machine: correctscope 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.
No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.
Endorsements
0 endorsementsNo one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.
Discussion of this attempt
no comments
Discussion
Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.
Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.