Non-antidirected paths at semidegree k/2

Question 5.1 · arXiv:2503.23191

arXiv Question high confidence— first stated 2025-03-29

Authors: Irena Penev, S Taruni, Stéphan Thomassé, Ana Trujillo-Negrete, Mykhaylo Tyomkyn

Status open high confidence

Question 5.1 asks whether every oriented graph G with δ°(G) ≥ k/2 contains every orientation of the k-edge path except the antidirected ones; the source paper proves this for two-block paths but the general case remains open. A June 2025 preprint (arXiv:2506.11866) asymptotically proves Stein’s conjecture for the antidirected case (the excluded class), and a December 2025 preprint (arXiv:2512.04423) confirms Stein’s conjecture (δ° > k/2) for two-block paths, but no paper found resolves the full Question 5.1 at the exact threshold δ° ≥ k/2 for all non-antidirected orientations.

Cited literature (2)

partial Antidirected paths in oriented graphs (2025)

unknown · arXiv preprint · arXiv:2506.11866

Asymptotically proves the antidirected path version of Stein’s conjecture (and of Addario-Berry–Havet–Linhares Sales–Reed–Thomassé), showing oriented graphs of minimum semidegree ≥ (3k-2)/4 contain an antidirected path of length k; addresses the excluded class in Question 5.1 but does not resolve whether δ° ≥ k/2 forces all non-antidirected orientations.
partial Paths with two blocks in oriented graphs of large minimum semi-degree (2025)

unknown · arXiv preprint · arXiv:2512.04423

Confirms Stein’s conjecture (δ° > k/2) for two-block oriented paths of length k; closely related to the source paper’s main result but addresses the strict-threshold Stein conjecture rather than the exact-threshold Question 5.1.

Reviewer notes. No paper found that directly resolves Question 5.1. Two related 2025 preprints address adjacent problems: antidirected paths asymptotically (2506.11866) and Stein’s conjecture for two-block paths at the strict threshold (2512.04423). The conjecture is recent (≤ 1 year) and a wide search returned no resolution, supporting high-confidence open status.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Is it true that every oriented graph $G$ with $\delta^{0}(G)\geq k/2$ contains every orientation of the $k$-edge path, save for the antidirected orientations?

Context

The tightness of Stein's conjecture for the antidirected orientation is witnessed by the $k/2$-blowup of the directed triangle. More generally, a regular tournament $T$ on $k+1$ vertices has $\delta^{0}(T)=k/2$ and, by Havet–Thomassé, contains every oriented $k$-arc path except (with three small exceptions) the antidirected one, suggesting that antidirected paths may be the only obstruction at the threshold $\delta^{0}(G)=k/2$.

Source paper

Two-block paths in oriented graphs of large semidegree
Irena Penev, S Taruni, Stéphan Thomassé, Ana Trujillo-Negrete, Mykhaylo Tyomkyn · 2025-03-29
https://arxiv.org/abs/2503.23191