Combinatorics Seminar

When: Sunday, November 8, 10am
Where: Schreiber 309
Speaker: Eoin Long, Tel Aviv University
Title: Large unavoidable subtournaments

Abstract:

Let D(k) denote the tournament on 3k vertices consisting of three disjoint vertex classes A,B and C of size k, where
  • each class A,B and C is oriented as a transitive subtournament, and
  • all edges are directed from A to B, from B to C and from C to A.

    Fox and Sudakov proved that given k and eps > 0, every sufficiently large tournament T which is eps-far from being transitive contains D(k) as a subtournament. They also conjectured a certain natural dependence on how large |T| must be as a function of k and eps. In this talk I'll discuss a proof of this conjecture.