Linkedness and Ordered Cycles in Digraphs

Given a digraph D, let delta(0)(D) := min{delta(+)(D), delta(-)(D)} be the minimum semi-degree of D. We show that every sufficiently large digraph D with delta(0)(D) >= n/2 + l - 1 is l-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis [17]. We also determine the smallest minimum semi-degree which ensures that a sufficiently large digraph D is k-ordered, i.e., that for every sequence s(1), ..., s(k) of distinct vertices of D there is a directed cycle which encounters s(1), ..., s(k) in this order. This result will be used in [16].