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.