{"id":"e660ad90-c799-4ba3-9cfc-65904440546c","arxiv_id":"2506.11866","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every oriented graph with minimum pseudo-semidegree greater than (k-1+√(k-3))/2 contains an antidirected path of length k, asymptotically matching the conjectured k/2 threshold.","lead":"This paper proves that any oriented graph whose smallest in-degree or out-degree is above a certain threshold must contain an antipath, a zigzag path of length k. The threshold is within a square-root factor of the best possible value, asymptotically confirming two conjectures for this special case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main proof's 'by symmetry' reductions in Lemma 10 and Theorem 3 omit a dual case; assuming edge v1vm and then the first disjunct of Lemma 10 requires a converse-graph argument that is not supplied.","rationale":"I read the paper in good faith. The central counting argument is coherent and the claimed bound is plausible; the main theorem appears to follow if the two terse symmetry reductions are legitimate. The reader identified exactly these reductions as the weakest assumption, and I agree. The first reduction, from Claim 11 to an edge v1vm, is not a simple reversal because m is odd: the unique source endpoint of the antipath remains v0 when the vertex order is reversed, so the roles of 'second vertex' and 'penultimate vertex' do not obviously swap. The second reduction, assuming the first disjunct of Lemma 10 in Theorem 3, similarly omits the case where the conclusion is supplied by the penultimate vertex's out-neighbours. Both omissions are likely fixable by a dualisation: applying the whole argument to the converse oriented graph (with all edges reversed and the vertex order reversed) would exchange the two disjuncts and preserve the degree hypotheses. However, the paper does not state this, so the proof as written is incomplete in a load-bearing place. The proposed concrete test—writing the dual counting argument explicitly—would settle whether the symmetry is valid or whether a genuine case is missing. Since the concern is about exposition and completeness rather than a demonstrated false step, I do not change the reader's conditional verdict.","tokens_in":5388,"tokens_out":41600,"duration_ms":439448,"concrete_test":"Write out the dual of the main proof for the second disjunct of Lemma 10: define F as the set of at least δ¯±(G)−k/2+1 out-neighbours of v_{m−1} outside V(A) (plus v_m), prove the analogues of Claims 12 and 13 for edges from V(A) to F, and verify the final inequality. If the dual counting goes through, the symmetry reductions are valid and the paper only needs a clarifying sentence; if a step fails, exhibit a graph with m=3, k=4 satisfying the hypotheses where Claim 11 holds only via v0→P, to confirm the proof is incomplete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After Claim 11, the proof says 'By Claim 11 and symmetry, we may assume that G contains an edge v1vm.' This is not immediate: m is odd, so reversing the antipath does not interchange the start and end vertices; the source endpoint of a longest antipath stays the same under reversal. If Claim 11 holds only through the first disjunct (an edge v0→p with p∈P), the text gives no argument that some longest antipath has an edge from its second vertex to its last vertex. Similarly, Theorem 3 states 'By Lemma 10 and symmetry' and assumes the first disjunct of Lemma 10 (v1 has many in-neighbours outside V(A)); if instead only the second disjunct holds (v_{m−1} has many out-neighbours outside V(A)), no proof is provided. The rest of the theorem, including the edge count from F to V(A), depends on this case separation. The gap is repairable by applying the same argument to the converse graph (reverse all edges and relabel v_i→v_{m−i}), which swaps in/out and start/end and preserves pseudo-semidegree and antipath containment. But this dualisation is not stated, so the proof as written covers only one case.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every integer k >= 4, every oriented graph with minimum pseudo-semidegree greater than (1/2)(k - 1 + sqrt(k - 3)) contains every antidirected path of length k. It follows that every oriented graph on n vertices with more than (k - 1 + sqrt(k - 3))n edges contains every antipath of length k, asymptotically confirming the antipath case of conjectures of Stein, of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, and of Burr. The proof assumes a longest antipath of length m < k, uses two lemmas of Klimošová and Stein to force m odd and to control certain modifications of longest antipaths, then defines a set F of in-neighbours of the second vertex of the antipath and obtains a contradiction by counting edges from F to the antipath: a lower bound from pseudo-semidegree and an upper bound from maximality through two structural claims.","tokens_in":5622,"tokens_out":46272,"duration_ms":489989,"significance":"If the proof is correct, this is a substantial advance: it improves the best known minimum pseudo-semidegree threshold forcing antipaths from 5k/8 to k/2 + O(sqrt(k)), matching the conjectured constant up to the square-root error term. The edge-density corollary and the chromatic corollary are immediate and give asymptotic resolutions of the antipath versions of well-known conjectures. The argument is elementary, self-contained apart from two cited lemmas, and produces a sharp numerical contradiction; it also has no free parameters and no fitting to the conclusion. The main caveat is that two 'by symmetry' reductions are not spelled out and, as written, appear to cover only one of two possible cases.","major_comments":[{"comment":"The two 'by symmetry' steps are load-bearing and are not justified in the text. In Lemma 10, Claim 11 yields either an edge v0p with p in P or an edge svm with s in S, and the proof then asserts 'by Claim 11 and symmetry, we may assume that G contains an edge v1vm'. Since m is odd, reversing the antipath does not interchange the source and sink endpoints, so this is not a reversal symmetry. If only the first disjunct of Claim 11 holds, the edge v1vm need not exist in G at all; the reduction requires passing to the converse graph G^op, where the reversed antipath (suitably relabelled) has an edge from its second vertex to its last vertex. The same converse-graph step is needed in Theorem 3 to assume the first alternative of Lemma 10, because the two alternatives in Lemma 10 are interchanged by reversing all edges. As written, the proof covers only one case. This is repairable by adding a short paragraph noting that the hypotheses and the conclusion are invariant under reversing all edges, so one may replace G by G^op when necessary; please add this or supply a direct argument.","section":"Lemma 10, after Claim 11; Theorem 3, after Lemma 10"}],"minor_comments":[{"comment":"The cases m ≡ 3 mod 4 and m ≡ 1 mod 4 implicitly assume m ≥ 3. The case m = 1 is impossible under the hypothesis because δ̄ ≥ 2 already forces an antipath of length 2, but this is not stated; a short justification would remove the ambiguity.","section":"Proof of Theorem 3, edge count"},{"comment":"The expression 'k−4/4' in the line 'This means that k−4/4 ≥ ...' should be parenthesised as '(k−4)/4' to avoid confusion.","section":"Proof of Theorem 3, displayed inequality"},{"comment":"The sentence describing what Claim 12 forbids is difficult to parse; it would be clearer to state directly that Claim 12 forces every other vertex to have at most one out-neighbour in Q.","section":"Claim 13, first paragraph"},{"comment":"The phrase 'By symmetry, we may assume that v0v1 ∈ E(G)' is really a labelling convention: in an odd antipath one of the two endpoints is a source, and the path can be labelled so that the first edge leaves it. Consider rephrasing to avoid implying a symmetry that is not used.","section":"Lemma 10, opening paragraph"}],"recommendation":"major_revision","confidential_remarks":"The theorem is significant and the argument is likely correct once the converse-graph reduction is added. The omitted dualisation is easy to supply and does not require reworking the main counting argument, but it is a genuine gap in the written proof because the current text covers only one of two possible configurations. If the authors add the missing paragraph, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the real thing, with one repairable gap in exposition. The theorem improves the best known pseudo-semidegree threshold for forcing an antipath from 5k/8 to k/2+O(√k), asymptotically matching Stein's conjecture. The proof is a longest-antipath argument with a block-counting claim (Claims 12–13) that appears original and does not reduce to earlier bounds. The edge count from F to V(A) and the final numerical contradiction check out.\n\nThe soft spot is exactly where the stress-test points. In Lemma 10, after Claim 11, the text says 'By Claim 11 and symmetry, we may assume that G contains an edge v1vm.' Reversing the antipath does not do this for odd length, because the source end stays the source end; you need the converse graph to swap in/out and relabel the reversed order. That dualisation is not stated. Similarly, in Theorem 3, the proof assumes the first disjunct of Lemma 10 without saying that the second disjunct can be handled by applying the argument to the converse graph. These are not fatal — the converse graph preserves pseudo-semidegree and antipath containment, so the symmetry is real — but as written the proof only treats one case explicitly. A referee should ask the authors to spell these two sentences out. The proof of Claim 13 is also compressed, though the counting seems sound.\n\nThe citation pattern is fine; the paper builds on Klimošová–Stein lemmas and correctly cites Skokan–Tyomkyn and the conjectures. Self-citation is not an issue here. The concluding remark about k ≤ 11 is a nice check.\n\nWho this is for: people working on oriented graph containment and semidegree threshold problems. It deserves a serious referee and, with the symmetry gaps filled, publication. My recommendation: send it out.","headline":"Genuine asymptotic improvement on the antipath threshold, with a repairable but real gap in the 'by symmetry' reductions that a referee should ask to be spelled out.","tokens_in":6169,"tokens_out":15297,"would_cite":true,"duration_ms":163134,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every integer $k\\ge 4$, every oriented graph whose minimum pseudo-semidegree exceeds $\\frac{1}{2}(k-1+\\sqrt{k-3})$ contains each antipath of length $k$, and the corresponding edge-density statement follows.","keywords":["antidirected path","oriented graph","minimum pseudo-semidegree","minimum semidegree","extremal graph theory","path containment","antipath"],"falsifier":"Search for a counterexample to Theorem 3: for some $k\\ge 12$, construct an oriented graph with minimum pseudo-semidegree greater than $\\frac{1}{2}(k-1+\\sqrt{k-3})$ and no antipath of length $k$. A finite brute-force enumeration over oriented graphs with the required pseudo-semidegree could test this for small $k$, and any graph found would disprove the theorem.","tokens_in":5197,"feed_emoji":"🔀","tokens_out":16303,"duration_ms":177662,"temperature":0.7,"pith_summary":"This paper establishes a near-optimal condition for forcing alternating paths in oriented graphs. For any integer $k\\ge 4$, if an oriented graph has minimum pseudo-semidegree greater than $\\frac{1}{2}(k-1+\\sqrt{k-3})$, then it contains every antidirected path of length $k$. Consequently, any oriented graph on $n$ vertices with more than $(k-1+\\sqrt{k-3})n$ edges contains every such antipath. These thresholds differ from the conjectured $\\frac{1}{2}k$ and $(k-1)n$ values only by $O(\\sqrt{k})$, so the paper asymptotically confirms the antipath cases of two standing conjectures on path containment in oriented graphs.","feed_headline":"Antipaths forced by pseudo-semidegree above (k-1+√(k-3))/2","feed_subtitle":"Asymptotically matches the conjectured k/2 semidegree threshold for alternating paths.","key_machinery":"The central object is the minimum pseudo-semidegree $\\bar{\\delta}^{\\pm}(G)$, the largest integer $d$ such that every vertex has out-degree either $0$ or at least $d$, and in-degree either $0$ or at least $d$. The argument uses a longest antipath $A$ in a hypothetical counterexample and the set $F$ of in-neighbours of the second vertex of $A$ that lie outside $A$; each $w\\in F$ starts a new antipath, so no edge can leave $F$. Claims 12 and 13 then constrain the edges from $F$ into $A$ by forbidding pairs of edges that would splice together a longer antipath, and these constraints are counted over blocks of four vertices of $A$. The final contradiction compares the upper bound $\\frac{k}{2}|F|+\\frac{k-4}{4}$ on edges from $F$ to $V(A)$ with the lower bound $\\bar{\\delta}^{\\pm}(G)|F|$ forced by the pseudo-semidegree condition.","core_discovery":"The central claim, on the paper's own terms, is that the minimum pseudo-semidegree threshold for forcing every antipath of length $k$ is at most $\\frac{1}{2}(k-1+\\sqrt{k-3})$. The proof takes a hypothetical graph that satisfies the pseudo-semidegree bound yet has no antipath of length $k$, fixes a longest antipath $A=v_0v_1\\ldots v_m$, and studies the set $F$ of in-neighbours of $v_1$ outside $A$. Every vertex of $F$ can serve as the first vertex of an antipath through $A$, so no edge of $G$ may leave $F$; the pseudo-semidegree condition then forces many edges from $F$ to $V(A)$. A block-counting argument shows that too many such edges would create a longer antipath, while the pseudo-semidegree lower bound requires even more of them, a contradiction.","pith_inferences":["The $\\sqrt{k}$ gap to the conjectured $\\frac{1}{2}k$ threshold likely comes from the block averaging in the edge count rather than from a genuine extremal construction, so sharper accounting may close it.","Since Lemma 9 already links long anticycles to antipaths, the same block-counting over a longest antipath may yield an analogous pseudo-semidegree threshold for anticycles of length $k+1$."],"forward_implications":["Every oriented graph on $n$ vertices with more than $(k-1+\\sqrt{k-3})n$ edges contains every antipath of length $k$.","Every $(2k+2\\sqrt{k-3})$-chromatic oriented graph contains every antipath of length $k$.","For $k\\le 11$, the arguments also verify the exact conjectured threshold $\\frac{1}{2}k$ for pseudo-semidegree.","Because the pseudo-semidegree is always at least the ordinary semidegree, the same antipath guarantee holds under the stronger semidegree hypothesis."],"supporting_citations":[{"why":"Supplies Lemmas 8 and 9, which fix the parity of a longest missing antipath and convert an anticycle of length $m+1$ into an antipath; both lemmas are imported into the proof of Theorem 3.","marker":"[7]"},{"why":"Establishes the conversion from an edge count above $cn$ to a subgraph with pseudo-semidegree above $c/2$, which yields Corollary 5 from Theorem 3.","marker":"[10]"},{"why":"Formulates the minimum-semidegree conjecture whose antipath case Theorem 3 asymptotically settles.","marker":"[9]"},{"why":"Formulates the edge-density conjecture for antidirected trees whose antipath case Corollary 5 asymptotically settles.","marker":"[1]"},{"why":"Supplies the previous $5k/8$ pseudo-semidegree bound that the new threshold improves.","marker":"[8]"}],"fun_headline_variants":["Pseudo-semidegree > (k-1+√(k-3))/2 forces every antipath of length k","Antipath forcing: pseudo-semidegree above (k-1+√(k-3))/2 works","Tight semidegree condition for antipaths: (k-1+√(k-3))/2","Pseudo-semidegree threshold yields antipaths of length k"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is an unproved symmetry reduction in Lemma 10: from a longest antipath the proof assumes, without showing the symmetry, that the antipath can be chosen so that its second vertex has many in-neighbours outside the path; if that reduction ever fails, the edge-counting contradiction does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Pseudo-semidegree > (k-1+√(k-3))/2 forces every antipath of length k","Antipath forcing: pseudo-semidegree above (k-1+√(k-3))/2 works","Tight semidegree condition for antipaths: (k-1+√(k-3))/2","Pseudo-semidegree threshold yields antipaths of length k"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000961,"raw_usage":{"total_tokens":4040,"prompt_tokens":839,"completion_tokens":3201,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":455,"completion_tokens_details":{"reasoning_tokens":3096}},"tokens_in":455,"tokens_out":3201,"duration_ms":28628,"temperature":1.0,"reasoning_tokens":3096,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T01:04:57.696544+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a counterexample to Theorem 3: for some $k\\ge 12$, construct an oriented graph with minimum pseudo-semidegree greater than $\\frac{1}{2}(k-1+\\sqrt{k-3})$ and no antipath of length $k$. A finite brute-force enumeration over oriented graphs with the required pseudo-semidegree could test this for small $k$, and any graph found would disprove the theorem.","supporting_citations":[{"cited_title":"Klimošová and M","cited_arxiv_id":null,"evidence_quote":"Supplies Lemmas 8 and 9, which fix the parity of a longest missing antipath and convert an anticycle of length $m+1$ into an antipath; both lemmas are imported into the proof of Theorem 3."},{"cited_title":"Stein and C","cited_arxiv_id":null,"evidence_quote":"Establishes the conversion from an edge count above $cn$ to a subgraph with pseudo-semidegree above $c/2$, which yields Corollary 5 from Theorem 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formulates the minimum-semidegree conjecture whose antipath case Theorem 3 asymptotically settles."},{"cited_title":"Addario-Berry, F","cited_arxiv_id":null,"evidence_quote":"Formulates the edge-density conjecture for antidirected trees whose antipath case Corollary 5 asymptotically settles."},{"cited_title":"Alternating paths in oriented graphs with large semidegree","cited_arxiv_id":"2406.03166","evidence_quote":"Supplies the previous $5k/8$ pseudo-semidegree bound that the new threshold improves."}],"review_version":1}