On degree thresholds of cycles in oriented graphs
McGill University

Motivated by Caccetta-Haggkvist conjecture, Kelly, Kuhn and Osthus initiated the study of minimum out-degree and semi-degree conditions that force an oriented graph to contain an oriented cycle of a given length. In particular, they proved for every $l\geq 4$ that if $G$ is a sufficiently large $n$-vertex oriented graph with semi-degree $> n/3$, then $G$ contains an oriented cycle of length $l$. It is easy to show that the bound is sharp for every $l$ not divisible by 3. However, they conjectured that for $l\geq 4$ which is a multiple of 3, one can always do better. The smallest open case, which has drawn quite some attention and was a few times mentioned in open problem sessions by Kuhn and Osthus, is the one when $l=6$.

In this talk, we will prove for every $l \geq 6$ which is a multiple of 3 that if $G$ is a sufficiently large $n$-vertex oriented graph with semi-degree $> n/4$, then $G$ contains an oriented cycle of length $l$. The bound $n/4$ is again sharp, since blow-ups of oriented 4-cycle contain no cycle of length divisible by 3.

This is a joint work with Roman Glebov and Andrzej Grzesik