An oriented graph is a digraph without any self-loops, multiple arcs, or 2-cycles. What is the smallest minimum outdegree of an oriented graph on $n$ vertices that ensures there will always be a cycle of length at least $k$? Can the bound be improved if one includes the minimum indegree in the bound?



Lower bound on outdegree/indegree in oriented graph to guarantee cycle of length at least $k$
Out-degree $k-2$ is sufficient to force a directed cycle of length at least $k$. To see this, consider a longest directed path $P:=v\_1v\_2 \dots v\_\ell$. Since $P$ is a longest path and there are no $2$-cycles, all out-neighbours of $v\_\ell$ are among $\{v\_1, \dots, v\_{\ell-2}\}$. Since $v\_\ell$ has at least $k-2$ out-neighbours, this gives a directed cycle of length at least $k$. 


On the other hand, this bound cannot be improved too much. For example, out-degree $k$ is in general not strong enough to force a directed cycle of length $3k+1$. To see this, orient the complete multi-partite graph $K\_{k,k,k}$ in the obvious way. Note that this example also has minimum in-degree $k$, so adding a minimum in-degree condition will not help too much. 


