REVIEW 1 major objections 4 minor 2 cited by
Antidirected paths in oriented graphs
T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [Lemma 10, after Claim 11; Theorem 3, after Lemma 10] 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.
minor comments (4)
- [Proof of Theorem 3, edge count] 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.
- [Proof of Theorem 3, displayed inequality] The expression 'k−4/4' in the line 'This means that k−4/4 ≥ ...' should be parenthesised as '(k−4)/4' to avoid confusion.
- [Claim 13, first paragraph] 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.
- [Lemma 10, opening paragraph] 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.
Circularity Check
No circularity: external lemmas and explicit contradiction; unproved 'symmetry' reductions are a completeness concern, not circular.
full rationale
The derivation is self-contained in the relevant sense: Theorem 3 is proved by contradiction from an assumed longest antipath of length m<k plus an edge-counting argument, and no parameter is fitted to data nor is the conclusion used as an input. The only external lemmas (Lemma 8 and Lemma 9) are quoted from Klimošová and Stein [7], a published source by different authors, so the reliance is independent rather than a self-citation chain. The averaging bound and the final contradiction are explicit inequalities, not renamed versions of the claim. The proof does contain two unelaborated 'by symmetry' reductions: in Lemma 10 ('By Claim 11 and symmetry, we may assume that G contains an edge v1vm') and in Theorem 3 ('By Lemma 10 and symmetry, let A=... with v1 having many in-neighbours'). These are potential completeness gaps—likely repairable by passing to the converse graph and relabelling—but they are not instances of defining X in terms of Y, fitting a parameter to the target, or importing an unverified uniqueness claim from the authors' own prior work. Consequently, no circular step is present and the score is 0.
Assumptions & free parameters
assumptions (2)
- domain assumption Lemma 8 of Klimošová and Stein: if δ̄±(G) ≥ k/2 and a longest antipath has length m < k, then m is odd.
- domain assumption Lemma 9 of Klimošová and Stein: if δ̄±(G) > k/2 and G has an anticycle of length m+1 with m < k, then G has an antipath of length m+1.
Cite this review
Pith. "Pith review of Antidirected paths in oriented graphs." pith.science (2026). https://pith.science/paper/QVJETXLD
@misc{pith2026250611866,
author = {Pith},
title = {Pith review of: Antidirected paths in oriented graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/QVJETXLD}},
note = {Machine review of arXiv:2506.11866}
}
abstract
We show that for any integer $k \ge 4$, every oriented graph with minimum semidegree bigger than $\frac{1}{2}(k-1+\sqrt{k-3})$ contains an antidirected path of length $k$. Consequently, every oriented graph on $n$ vertices with more than $(k-1+\sqrt{k-3})n$ edges contains an antidirected path of length $k$. This asymptotically proves the antidirected path version of a conjecture of Stein and of a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomass\'e, respectively.
Figures
Forward citations
Cited by 2 Pith papers
-
Long antipaths in oriented graphs
Every oriented graph with minimum pseudo-semidegree at least k contains an antidirected path of length 2k−1, confirming Stein’s conjecture.
-
On the supersaturation of oriented Tur\'an problems
Oriented graphs that exceed the oriented Turán density contain a positive fraction of the possible copies of the forbidden oriented subgraph, with explicit bounds for transitive tournaments and antidirected complete b...
Reference graph
Works this paper leans on
-
[1]
L. Addario-Berry, F. Havet, L. Linhares Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs.Discrete Mathematics, 313:967–974, 2013. 6
work page 2013
-
[2]
S. A. Burr. Subtrees of directed graphs and hypergraphs. InProceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Congr. Numer, volume 28, pages 227–239, 1980
work page 1980
-
[3]
B. Chen, X. Hou, and H. Zhou. Long antipaths and anticycles in oriented graphs. Discrete Mathematics, 348:114412, 2025
work page 2025
-
[4]
G. A. Dirac. Some theorems on abstract graphs.Proceedings of The London Mathe- matical Society, 2:69–81, 1952
work page 1952
-
[5]
P. Erdős and T. Gallai. On maximal paths and circuits of graphs.Acta Mathematica Academiae Scientiarum Hungarica, 10:337–356, 1959
work page 1959
-
[6]
B. Jackson. Long paths and cycles in oriented graphs.Journal of Graph Theory, 5:145–157, 1981
work page 1981
-
[7]
T. Klimošová and M. Stein. Antipaths in oriented graphs.Discrete Mathematics, 346:113515, 2023
work page 2023
-
[8]
Alternating paths in oriented graphs with large semidegree
J. Skokan and M. Tyomkyn. Alternating paths in oriented graphs with large semide- gree.arXiv:2406.03166, 2024
work page Pith review arXiv 2024
Show all 10 references
-
[9]
M. Stein. Tree containment and degree conditions.Discrete Mathematics and Appli- cations, 165:459–486, 2020
2020
-
[10]
Stein and C
M. Stein and C. Zárate-Guerén. Antidirected subgraphs of oriented graphs.Combi- natorics, Probability and Computing, 33:1–21, 2024. 7
2024
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.