Trees in tournaments

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) greater than or equal to 2n - 2 and conjectured that equality holds, Haggkvist and Thomason established the upper bounds f (n) less than or equal to 12n and f (n) less than or equal to (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. Haggkvist and Thomason (Combinatorica 11 (1991) 123) proved that g(k) less than or equal to 2(512k3). Havet and Thomasse conjectured that g(k) less than or equal to 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 + 3/2(k2 - 3k) + 5)-unavoidable. In particular, a tree with three leaves is (n + 5)-unavoidable, i.e. g(3) less than or equal to 5. By studying trees with few leaves, we then prove that f (n) less than or equal to 38/5 n - 6. (C) 2002 Elsevier Science B.V. All rights reserved.