Stein's pseudo-semidegree conjecture for long antipaths

Less than 1 year old · traced to

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 2k−12k-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 2k−12k-1, but the supplied text does not state that the full pseudo-semidegree conjecture is resolved.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.