Trees in tournaments

Speaker(s)

François Dross

Affiliation

University of Warsaw

Date

Oct. 31, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

A tournament is an orientation of a complete graph. A digraph is n-unavoidable if it is contained (as a subdigraph) in every tournament of order n. The unavoidability of a digraph D is the minimum integer n such that D is n-unavoidable. It is well-known that the transitive tournament of order n is 2^{n-1}-unavoidable and thus every acyclic digraph of order n is 2^{n-1}-unavoidable. However, for acyclic digraphs with few arcs better bounds are expected. In this talk we will focus on oriented trees. Sumner conjectured that every oriented tree of order n>1 is (2n-2)-unavoidable. An Arborescence is a rooted tree where either every edge is oriented from the root or every edge is oriented towards the root. We will first prove that every arborescence of order n with k leaves is (n+k-1)-unavoidable. We will then prove that every oriented tree of order n with k leaves is (3n/2+3k/2 -2)-unavoidable and (9n/2 -5k/2 -9/2)-unavoidable, and thus ((21/8)(n-1))-unavoidable, the best bound to date towards Sumner's conjecture. Finally, we will prove that every oriented tree of order n with k leaves is (n+ 144k^2 - 280k + 124)-unavoidable.

---