Stein's pseudo-semidegree conjecture for long antipaths

From papers

Let GG be an oriented graph. Its minimum pseudo-semidegree δˉ0(G)\bar{\delta}^0(G) is the minimum among all non-zero in-degrees and out-degrees of its vertices; equivalently, it is the maximum kk such that every vertex has either out-degree 00 or at least kk, and either in-degree 00 or at least kk. Stein's pseudo-semidegree conjecture. If δˉ0(G)k\bar{\delta}^0(G)\geq k, then GG contains an antipath of length 2k12k-1. Here an antipath is an oriented path in which every vertex has in-degree 00 or out-degree 00. The paper investigates this conjecture for antipaths and proves that every oriented graph with minimum semidegree at least kk contains an antipath of length 2k12k-1, but the supplied text does not state that the full pseudo-semidegree conjecture is resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yuping Gao and Allan Lo, “Long antipaths in oriented graphs”, arXiv:2607.24738 (2026).

Solutions 0

No solutions have been posted yet.