For every integer k≥ 2, every oriented graph G with minimum semidegree delta^0(G):=mindelta^+(G),delta^-(G)>k/2 contains, as a subgraph, every orientation of the path with k edges.

Stein’s conjecture on oriented paths

Stein’s 2020 conjecture asks whether every oriented graph $G$ with minimum semidegree $\delta^0(G)>k/2$ contains every orientation of the $k$ -edge path. The general conjecture remains unresolved.

Known results

Directed paths: Jackson, 1981.
Oriented graphs with no oriented $4$ -cycle: Stein and Trujillo-Negrete.
Alternating paths: minimum in- and out-degree greater than $5k/8$ .
Antipaths: minimum semidegree greater than $\frac{1}{2}(k-1+\sqrt{k-3})$ for $k\geq4$ .

September 2026 bipartite threshold

A newly reported paper proves a quantitative minimum-semidegree threshold for two-block paths in bipartite oriented graphs. This is claimed progress rather than a resolution: the general two-block case was already known, and arbitrary oriented paths remain unresolved.

Current status (as of September 2026): Several special cases, including two-block paths, are known, while Stein’s conjecture for arbitrary oriented paths remains open; the new bipartite threshold is unverified here.

Stein’s conjecture on oriented paths

Primary source

Additional references

Progress summary

Solutions 0