Combinatorics Seminar

When: Sunday, October 26, 10am Where: Schreiber 309 Speaker: Raphy Yuster, University of Haifa Title: Unavoidable tournaments

Abstract:

A basic result in Ramsey theory states that any tournament contains a "large" transitive subgraph. Since transitive tournaments contain only transitive subgraphs, it is natural to ask which subgraphs must appear in any large tournament that is "far" from being transitive. One result of this type was obtained by Fox and Sudakov, who characterized the tournaments that appear in any tournament that is epsilon-far from being transitive. Another result of this type was obtained by Berger et al., who characterized the tournaments that appear in any tournament that cannot be partitioned into a bounded number of transitive sets.

In this talk we consider the common generalization of the above two results, namely the tournaments that must appear in any tournament that is epsilon-far from being the union of a bounded number of transitive sets. Our main result is a precise characterization of these tournaments.

Joint work with A. Shapira.