Directed Graphs Without Short Cycles

For a directed graph G without loops or parallel edges. let beta(G) denote the size of the smallest feedback arc set, i.e., the smallest subset X subset of E(G) such that G \ X has no directed cycles. Let gamma(G) be the number of unordered pairs of vertices of G which are not adjacent. We prove that every directed graph whose shortest directed cycle has length at least r >= 4 satisfies beta(G) <= c gamma(G)/r(2), where c is an absolute constant. This is tight up to the constant factor and extends a result of Chudnovsky, Seymour and Sullivan. This result can also be used to answer question of Yuster concerning almost given length cycles in digraphs. We show that for any fixed 0 < 0 < 1/2 and sufficiently large n, if G is a digraph with n vertices and beta(G) >= 0n(2), then for any 0 <= m <= 0n - o(n) it contains a directed cycle whose length is between m and m + 60(-1/2). Moreover, there is a constant C such that either G contains directed cycles of every length between C and 0n - o(n) or it is close to a digraph G' with a simple structure: every strong component of G' is periodic. These results are also light up to the constant factors.