Antidirected paths in oriented graphs

An antidirected path is an orientation of a path such that for each vertex v we have either d^-(v)=0 or d^+(v)=0. In this talk I will show that for any integer k > 3, every oriented graph with minimum semidegree bigger than k/2+\sqrt{k}/2 contains an antidirected path of length k. Consequently, every oriented graph on n vertices with more than (k+\sqrt{k})n edges contains an antidirected path of length k. This asymptotically proves the antidirected path version of a conjecture of Stein and of a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, respectively.

This is joint work with Andrzej Grzesik.