Trees in tournaments Original Research Article

A digraph is said to be n-unavoidable if every tournament of order n contains it as a subgraph. Let f(n) be the smallest integer such that every oriented tree is f(n)-unavoidable. Sumner (see (Reid and Wormald, Studia Sci. Math. Hungaria 18 (1983) 377)) noted that f(n)⩾2n−2 and conjectured that equality holds. Häggkvist and Thomason established the upper bounds f(n)⩽12n and f(n)⩽(4+o(1))n. Let g(k) be the smallest integer such that every oriented tree of order n with k leaves is (n+g(k))-unavoidable. Häggkvist and Thomason (Combinatorica 11 (1991) 123) proved that g(k)⩽2512k3. Havet and Thomassé conjectured that g(k)⩽k−1. We study here the special case where the tree is a merging of paths (the union of disjoint paths emerging from a common origin). We prove that a merging of order n of k paths is (n+32(k2−3k)+5)-unavoidable. In particular, a tree with three leaves is (n+5)-unavoidable, i.e. g(3)⩽5. By studying trees with few leaves, we then prove that f(n)⩽385n−6.