| Let G be a finite simple directed graph on n vertices. Say G is m-free if it has no directed cycles of length at most m. In 1978, Caccetta and Haggkvist [3] conjectured that if G has minimum out-degree at least r, then G is not n/r -free. Finding upper bounds on the minimum out-degree in 3-free digraphs has been of particular interest in recent research. In this thesis, we present new results for several related problems in extremal directed graph theory.; Let beta(G) denote the size of the smallest subset X ⊆ E(G) such that GX has no directed cycles, and let g (G) be the number of non-edges of G. Fix an integer m ≥ 3; let G be m-free. For 3 ≤ m ≤ 5, we prove that beta( G) ≤ gG m-2 . One consequence when m = 3 was a new bound of .3530831| V(G)| on the minimum out-degree in 3-free digraphs [7, 21].; We conjecture that beta(G) ≤ 2m+1 m-2g (G) (this would be best possible if true), and prove this conjecture when V(G) is the union of two tournaments. Furthermore, whenG is a circular interval digraph (the vertices ofG can be arranged in a circle such that if distinct u, v, w are in clockwise order and uw is a directed edge, then so are both uv, vw), we show that beta(G) ≤ gG 2m-2 .; Another approach to Caccetta-Haggkvist has been studying relationships between being m-free and having a bounded number of directed t-vertex paths. We prove that in 3-free digraphs, the number of four-vertex directed paths is at most 475 |V(G)|4. Furthermore, Thomasse conjectures that ifG is 2-free, then G has at most (n - 1)n( n + 1)/15 induced three-vertex directed paths. We prove that in circular interval digraphs, an upper bound of n3/16 holds.; We also consider the tradeoff between minimum and average out-degree in 3-free digraphs. In particular, we prove that for 3-free G with average out-degree g n and minimum out-degree epsilonn, we have g ≤ min 21-2e 2-c,1-e2-c for any constant c > 0 so that all 3-free digraphs on n > 0 vertices have minimum out-degree at most cn. |
