Pith. sign in

REVIEW 2 major objections 6 minor 19 references

Long antipaths in oriented graphs

T0 review · 2 major / 6 minor · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every oriented graph with minimum pseudo-semidegree at least k contains an antidirected path of length 2k−1.

desk verdict Exact confirmation of Stein’s antipath conjecture via a clean two-sided blow-up counting argument; the only real residual risk is a long but checkable case analysis in Lemma 2.4. read the letter →

arxiv 2607.24738 v1 pith:UBY47QQ3 submitted 2026-07-27 math.CO

Yuping Gao , Allan Lo This is my paper · ORCID
classification math.CO MSC 05C2005C38
keywords antidirectedpathantipathminimumsemidegreepseudo-semidegreeorientedgraphSteinconjectureblow-up
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

An antidirected path (antipath) is a path in a directed graph where each vertex has only incoming or only outgoing edges along the path. This paper proves that any oriented graph in which every nonzero in- or out-degree is at least k must contain an antipath with 2k−1 edges. That bound is tight: there are examples with the same degree condition that have no antipath of length 2k. The result settles Stein’s conjecture for antipaths and thereby confirms the antipath case of a broader conjecture that every oriented graph should contain every orientation of a path of length 2δ⁰(G)−1. The argument works by taking a longest antipath, expanding its ends into independent sets (an “antipath blow-up”), and deriving a degree contradiction unless the path is already long enough.

What carries the argument

Antipath blow-up: a longest antipath whose two end vertices are replaced by independent sets V₀ and V_{2ℓ+1} of size at least 2, with all edges from V₀ into the next vertex and from the penultimate vertex into V_{2ℓ+1}. Counting edges between these ends and the internal path, together with surplus indices and non-adjacency lemmas, produces an upper bound that contradicts the minimum pseudo-semidegree unless the path already has length 2k−1.

What would settle it

Exhibit an oriented graph with minimum pseudo-semidegree at least k that has no antipath of length 2k−1, or find a flaw in the existence of a two-sided blow-up with both end-sets of size at least 2 (Lemma 2.4) or in the subsequent edge-counting contradiction.

Watch

Extended reading notes

Core claim

Every oriented graph G with minimum pseudo-semidegree δ̄⁰(G) ≥ k contains an antipath of length 2k−1. Equivalently, Stein’s Conjecture 1.2 is true, so the antipath case of Conjecture 1.1 also holds. The bound is best possible: for every k there exist oriented graphs with δ⁰ = δ̄⁰ = k that contain neither an antipath nor an anticycle of length 2k.

Load-bearing premise

The argument depends on two prior facts: that a longest antipath shorter than 2k−1 must have odd length, and that a short anticycle of even length forces an antipath of the same length; if either fails, the parity and blow-up counting collapse.

Editorial extensions

If this is right

  • Stein’s minimum-semidegree conjecture is settled for all antipaths.
  • The same bound is tight for both antipaths and anticycles of length 2k.
  • Directed paths and paths with one direction change were already known; only more mixed orientations remain open under the same degree hypothesis.
  • The blow-up-and-surplus counting method supplies a template for attacking other fixed orientations of paths.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The concluding remarks note that the pseudo-semidegree analogue fails for any orientation containing a directed path of length 2, so further progress on the full conjecture will need the stricter ordinary minimum semidegree.
  • A natural next test is whether the same blow-up technique can force antipaths of length roughly 2δ⁰ under weaker local degree conditions or in tournaments with restricted cycle types.
  • If the two external Klimošová–Stein lemmas can be strengthened to even lengths or to longer cycles, the blow-up argument might yield longer guaranteed antipaths in denser oriented graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The manuscript proves that every oriented graph G with minimum pseudo-semidegree δ̄⁰(G) ≥ k contains an antidirected path of length 2k−1, confirming Stein's Conjecture 1.2 and thereby Conjecture 1.1 for antipaths; Proposition 1.4 shows the bound is tight. The proof is by contradiction: assuming a longest antipath has length 2ℓ+1 < 2k−1 (parity via a lemma of Klimošová–Stein), the authors construct a two-sided "antipath blow-up" V₀v₁…v_{2ℓ}V_{2ℓ+1} with |V₀|, |V_{2ℓ+1}| ≥ 2 (Lemma 2.4, proved in Section 3), and then charge each "surplus" index i ∈ [ℓ−1] to adjacent non-surplus indices (Claim 2.5), giving e(V₀,V′)+e(V′,V_{2ℓ+1}) ≤ (ℓ+1)(|V₀|+|V_{2ℓ+1}|), while the degree condition forces the same quantity to be at least k(|V₀|+|V_{2ℓ+1}|). Since ℓ ≤ k−2, this is a contradiction. The core counting argument is clean, and the structural heavy lifting is confined to Lemma 2.3 (local forbidden configurations) and Lemma 2.4 (existence of the two-sided blow-up).

Significance. If correct, this settles Stein's Conjecture 1.2 (and hence Conjecture 1.1 for antipaths), closing a problem with a documented line of partial progress (Klimošová–Stein; Chen–Hou–Zhou; Skokan–Tyomkyn; Grzesik–Skrzypczyk), and the bound 2k−1 is shown best possible (Proposition 1.4). Strengths worth naming: the proof is self-contained modulo two published lemmas; it is parameter-free — no regularity, no ε's, no asymptotics — and yields the exact constant; the extremal construction in Proposition 1.4 is verified for all k; and the two-sided blow-up idea (Lemma 2.4 plus the charging scheme of Claim 2.5) is a genuine methodological advance over the one-sided blow-up of Grzesik–Skrzypczyk that powered all previous bounds. The result is definitive for its question and will likely be the reference point for the remaining cases of Conjecture 1.1.

major comments (2)
  1. [Section 3, proof of Lemma 2.4] Lemma 2.4, final displayed list of four antipath blow-ups (after Claim 3.5, p. 13, with Figure 3.5): the four cases are written in ellipsis notation, e.g. 'U v2i xi v2i+1 ... v2i0−1 v2ℓ ... v2i0 v2i−2 x v1 ... v2i−3'. The case split is i < i0 versus i > i0+1, but the degenerate near-boundary subcases (i = i0−1 and i = i0+2, where the '...' segments collapse to zero or one vertex) are not written out, and small ℓ (ℓ = 2 or 3, where [ℓ−1] and the ranges of I are nearly empty) are not separately discussed. My own index bookkeeping for these boundaries indicates the constructions remain valid — exactly one internal index is omitted while xi and x are inserted, preserving length 2ℓ+1 and alternation — but this is the load-bearing step of the whole paper, and the manuscript should not leave it to the reader. Please add a short verification of the boundary cases, or restructure the display so t
  2. [Claim 3.4 and Lemma 2.3(h)] The proofs of Lemma 2.3(h) and Claim 3.5 both estimate |N^-(v)\(V0 ∪ V')| by d^-(v) − d^-(v, V'\V_{2I}) − d^-(v, V_{2I}), and then lower-bound this using |V'\V_{2I}| − d^+(v, V'\V_{2I}). This step silently uses that for an oriented graph restricted to a fixed vertex set, d^-(v,W) + d^+(v,W) ≤ |W|, which is fine, but the arithmetic chain '≥ k − (2ℓ − |I| − k) − 1 = |I| + 2(k−ℓ) − 2' in Claim 3.4 (p. 11) deserves one line of justification, since the analogous computation appears three times (Lemma 2.3(h), Claim 3.4, Claim 3.5) with slightly different constants (−1 vs −2, |I|+3 vs |I|+2) and an off-by-one error here would propagate into the maximality contradictions |U| > |V0|. I checked the constants and believe they are consistent (the differing offsets come from d^-(v_{2j}, V_{2I}) ≤ 1 via Lemma 2.3(j) versus = 0 via (2.1)/(3.4)), but the manuscript should make the source of each offset
minor comments (6)
  1. [References] Reference [12]: 'R´edei, Ein kombinatoricher satz, Acta Lott. Szeged' should read 'Ein kombinatorischer Satz, Acta Litt. Sci. Szeged' (or Acta Sci. Math. (Szeged)) 7:39–43, 1934.
  2. [References] Reference [5] (Grzesik–Skrzypczyk) is cited only as an arXiv preprint; please update the bibliographic data if it has appeared, since Lemma 2.3(b) and Lemma 3.1 explicitly build on its Claim 12 and Lemma 10.
  3. [Claim 2.5(d)] In Claim 2.5(d), the bound '|N^+(v_{2i−3})\(V_{2ℓ+1} ∪ V')| ≥ 4 by Lemma 2.3(h) (applied to the reverse of G)' deserves a half-line of explanation: (h) gives |I|+3 where |I| counts surplus indices, and the ≥4 conclusion uses that i−2 itself contributes to that count. This is correct but not immediate.
  4. [Section 1.1] Notation §1.1: 'We simply write v for {v}' is used implicitly from Section 2 onwards (e.g. e(V0, v1)); consider stating explicitly that singletons are identified with their elements in e(·,·) and N±(·,·).
  5. [Abstract] The abstract and first sentence of Section 1 say 'minimum semidegree' while Theorem 1.3 is stated for minimum pseudo-semidegree δ̄⁰; the abstract should match the theorem, since the pseudo-semidegree formulation is strictly stronger and is the paper's actual contribution.
  6. [Figures] Figures 2.1–3.5 are helpful, but the vertices V0/V2ℓ+1 are drawn identically to singleton vertices in some panels; a brief caption note that U, W, W± denote sets while xi, x denote vertices would ease reading.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained combinatorial contradiction proof; external lemmas are independent published results, not definitional inputs.

full rationale

Theorem 1.3 is proved by contradiction via antipath blow-ups and a double-counting argument on surplus indices (Claim 2.5 and the subsequent sum bounding e(V0,V')+e(V',V2ℓ+1) ≤ (ℓ+1)(|V0|+|V2ℓ+1|), contradicting ¯δ0(G)≥k when ℓ≤k−2). The only external load-bearing ingredients are Klimošová–Stein Lemmas 2.1–2.2 (parity of longest antipaths and anticycle-to-antipath conversion), which are cited published results by other authors with stated hypotheses that do not include the target constant 2k−1. Lemma 2.4 and Lemma 2.3 are proved internally by rotation/extension case analysis in the same paper. There are no fitted parameters, no self-defining quantities, no uniqueness theorems imported from the present authors, and no renaming of a known bound as a new derivation. Background citations of partial bounds (Grzesik–Skrzypczyk, Chen–Hou–Zhou, etc.) are historical and not used to force the exact threshold. The derivation chain is therefore independent of its conclusion by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

Pure extremal graph theory. No free parameters. Background axioms are standard digraph definitions plus two published lemmas of Klimošová–Stein on parity and anticycles. The antipath-blow-up formalism is a proof device already present in weaker form in Grzesik–Skrzypczyk; it is not an ontological postulate.

assumptions (4)
  • domain assumption Klimošová–Stein Lemma 2.1: if a longest antipath in an oriented graph with δ̄⁰ ≥ k has length m < 2k−1, then m is odd.
    Invoked immediately after the statement of Theorem 1.3 to force m = 2ℓ+1; the whole surplus counting is built on odd length.
  • domain assumption Klimošová–Stein Lemma 2.2: an anticycle of length 2ℓ+2 < 2k−1 yields an antipath of length 2ℓ+2.
    Used throughout Lemma 2.3 to forbid closing edges that would create short anticycles.
  • standard math Standard definitions of oriented graph, in-/out-neighbourhood, minimum (pseudo-)semidegree, and antidirected path/cycle.
    Section 1.1 notation; no non-standard variants.
  • domain assumption Jackson’s theorem that every oriented graph contains a directed path of length 2δ⁰(G) (or a directed Hamilton cycle).
    Cited only for context; not used in the antipath proof.
invented entities (1)
  • Antipath blow-up V₀ v₁ … v_{2ℓ} V_{2ℓ+1}
    purpose: Encodes a family of longest antipaths sharing internal vertices so that endpoint degree conditions can be double-counted.
    Definitional proof tool (Section 2). A one-sided version already appears in Grzesik–Skrzypczyk; the two-sided version with simultaneous surplus control is new to this paper but remains a combinatorial device, not an external postulate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Long antipaths in oriented graphs." pith.science (2026). https://pith.science/paper/UBY47QQ3

@misc{pith2026260724738,
  author       = {Pith},
  title        = {Pith review of: Long antipaths in oriented graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UBY47QQ3}},
  note         = {Machine review of arXiv:2607.24738}
}
abstract

An antidirected path is an oriented path in which every vertex sees either just incoming or just outgoing edges. We prove that every oriented graph with minimum semidegree at least $k$ contains an antidirected path of length $2 k -1$. This confirms a conjecture of Stein.

Figures

Figures reproduced from arXiv: 2607.24738 by the authors.

Figure 2.1
Figure 2.1. antipaths considered in the proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p004_2_1.png] view at source ↗
Figure 2.2
Figure 2.2. antipaths considered in the proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p005_2_2.png] view at source ↗
Figure 2.3
Figure 2.3. anticycle and antipath considered in the proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p006_2_3.png] view at source ↗
Figures from the paper (7 more)
Figure 2.4
Figure 2.4. Figure 2.4: i and i ′ are V0-surplus and v2j ∈ N +(v2i) ∩ N +(v2i ′). Hence (h) holds. Let i be V0-surplus. By (c), V0 ⊆ N −(v2i+1). If v2iv2ℓ+1 ∈ E(G), then v1 . . . v2iv2ℓ+1 . . . v2i+1xv1 is an anticycle of length 2ℓ + 2 for all x ∈ V0 (see [PITH_FULL_IMAGE:figures/full_fig_…
Figure 2.5
Figure 2.5. Figure 2.5: antipaths considered in the proof of Claim [PITH_FULL_IMAGE:figures/full_fig_p008_2_5.png]
Figure 3.1
Figure 3.1. Figure 3.1: if p is odd. 3 Proof of Lemma 2.4 We first show that there exists an antipath blow-up V0v1 . . . v2ℓV2ℓ+1 such that at least one of V0 and V2ℓ+1 has size at least 2. This result has already been proved by Grzesik and Skrzypczyk [5, Lemma 10]. We include its proof as …
Figure 3.2
Figure 3.2. Figure 3.2: antipath blow-up considered in Claim 3.4. xi0 y x v1 v2i0−1v2i0 v2i0+1 v2ℓ [PITH_FULL_IMAGE:figures/full_fig_p012_3_2.png]
Figure 3.3
Figure 3.3. Figure 3.3: if i0 is V0-surplus. implies that v2ℓv2i0 ∈/ E(G). Therefore v2ℓv2i0−1 ∈ E(G). However, yv2i0 xi0 v1 . . . v2i0−1v2ℓ . . . v2i0+1x is an antipath of length 2ℓ + 2 (see [PITH_FULL_IMAGE:figures/full_fig_p012_3_3.png]
Figure 3.4
Figure 3.4. Figure 3.4: antipath blow-ups considered in Claim 3.5. Let U = N −(v2i) \ (V ′ ∪ V0). By Lemma 2.3(h) and (3.3), we have |U| ≥ |I| + 3 ≥ |V0| + 3. Recall that v2i0 v2i−2 ∈ E(G) or v2i−2v2i0 ∈ E(G). Then G contains an antipath blow-up of length 2ℓ + 1, namely Uv2ixiv2i+1 . . . v2…
Figure 3.5
Figure 3.5. Figure 3.5: antipath blow-ups considered in the proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p014_3_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 1 linked inside Pith

  1. [1]

    B. Chen, X. Hou, and X. Zhou. Long antipaths and anticycles in oriented graphs.Discrete Math., 348(5):Paper No. 114412, 6, 2025

    2025

  2. [2]

    B. Chen, X. Hou, and X. Zhou. Paths with two blocks in oriented graphs of large minimum semi- degree.Electron. J. Combin., 32(4):Paper No. 4.58, 13, 2025

    2025

  3. [3]

    G. A. Dirac. Some theorems on abstract graphs.Proc. London Math. Soc. (3), 2:69–81, 1952

    1952

  4. [4]

    Gr¨ unbaum

    B. Gr¨ unbaum. Antidirected Hamiltonian paths in tournaments.J. Combinatorial Theory Ser. B, 11:249–257, 1971

    1971

  5. [5]

    Grzesik and M

    A. Grzesik and M. Skrzypczyk. Antidirected paths in oriented graphs.arXiv:2506.11866v1

    arXiv

  6. [6]

    Havet and S

    F. Havet and S. Thomass´ e. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld’s conjecture.J. Combin. Theory Ser. B, 78(2):243–273, 2000. 13 U xix v1 v2i−3v2i−2 v2i v2i+1 v2i0 v2ℓ v2i−1 v2i0−1 (a) ifv 2i0 v2i−2 ∈E(G) andi < i0 U xix v1 v2i0−1 v2i−3v2i−2v2i−1 v2i v2i+1 v2ℓ v2i0 (b) ifv 2i0 v2i−2 ∈E(G) andi > i0 + 1 U xxi v1 v2i−2 v2i v2i+1 v2...

    2000

  7. [7]

    B. Jackson. Long paths and cycles in oriented graphs.J. Graph Theory, 5(2):145–157, 1981

    1981

  8. [8]

    Keevash, D

    P. Keevash, D. K¨ uhn, and D. Osthus. An exact minimum degree condition for Hamilton cycles in oriented graphs.J. Lond. Math. Soc. (2), 79(1):144–166, 2009

    2009

Show all 19 references
  1. [9]

    L. Kelly. Arbitrary orientations of Hamilton cycles in oriented graphs.Electron. J. Combin., 18(1):Pa- per 186, 25, 2011

    2011

  2. [10]

    Klimoˇ sov´ a and M

    T. Klimoˇ sov´ a and M. Stein. Antipaths in oriented graphs.Discrete Math., 346(9):Paper No. 113515, 6, 2023

    2023

  3. [11]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. A survey on Hamilton cycles in directed graphs.European J. Combin., 33(5):750–766, 2012

    2012

  4. [12]

    L. Redei. Ein kombinatoricher satz.Acta Lott. Szeged, 7:39–43, 1934

    1934

  5. [13]

    Rosenfeld

    M. Rosenfeld. Antidirected Hamiltonian paths in tournaments.J. Combinatorial Theory Ser. B, 12:93–99, 1972

    1972

  6. [14]

    Skokan and M

    J. Skokan and M. Tyomkyn. Alternating paths in oriented graphs with large semidegree.Electron. J. Combin., 32(4):Paper No. 4.31, 7, 2025. 14

    2025

  7. [15]

    M. Stein. Tree containment and degree conditions. InDiscrete mathematics and applications, volume 165 ofSpringer Optim. Appl., pages 459–486. Springer, Cham, 2020

    2020

  8. [16]

    M. Stein. Oriented trees and paths in digraphs. InSurveys in combinatorics 2024, volume 493 of London Math. Soc. Lecture Note Ser., pages 271–295. Cambridge Univ. Press, Cambridge, 2024

    2024

  9. [17]

    Stein and A

    M. Stein and A. Trujillo-Negrete. Oriented trees in digraphs without oriented 4-cycles.Discrete Math., 349(12):Paper No. 115288, 2026

    2026

  10. [18]

    Stein and C

    M. Stein and C. Z´ arate-Guer´ en. Antidirected subgraphs of oriented graphs.Combin. Probab. Com- put., 33(4):446–466, 2024

    2024

  11. [19]

    Thomason

    A. Thomason. Paths and cycles in tournaments.Trans. Amer. Math. Soc., 296(1):167–180, 1986. 15

    1986

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.