An oriented graph is a digraph without any selfloops, multiple arcs, or 2cycles. 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?
Outdegree $k2$ 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 outneighbours of $v_\ell$ are among $\{v_1, \dots, v_{\ell2}\}$. Since $v_\ell$ has at least $k2$ outneighbours, this gives a directed cycle of length at least $k$.
On the other hand, this bound cannot be improved too much. For example, outdegree $k$ is in general not strong enough to force a directed cycle of length $3k+1$. To see this, orient the complete multipartite graph $K_{k,k,k}$ in the obvious way. Note that this example also has minimum indegree $k$, so adding a minimum indegree condition will not help too much.

$\begingroup$ Wait... I don't get how the outneighbors of $P$ must be in the path. What if $P$ were a subgraph of a spanning tree of a nonHamiltonian graph? Then wouldn't there always be an outneighbor not in the path? $\endgroup$ – Elliot Gorokhovsky Dec 11 '16 at 5:27

$\begingroup$ Sorry, that was a typo. It should have read all outneighbours of $v_\ell$. I edited it. $\endgroup$ – Tony Huynh Dec 11 '16 at 7:57
