Combinatorics Seminar

When: Sunday, February 20, 10am Where: Schreiber 309 Speaker: Eli Berger, University of Haifa Title: Excluding tournaments

Abstract:

A tournament is a directed graph where between every two vertices there is an edge in exactly one of the two possible directions. Given a fixed tournament H we may look at the class of all tournaments not containing H as a subtournament, and ask questions like:

1) Do all graphs in this class have a big transitive subtournament?

2) Do they all have a bounded chromatic number (i.e., a partition of the vertices to a bounded number of sets, the edges on each being transitive)?

3) Do they have a bounded fractional chromatic number? A-priory, these are three distinct questions, however, recently, it was shown that they are equivalent.

In the talk I will explain why the three questions are equivalent, and what the answer is.

Joint work with Martin Loebl, Maria Chudnovsky, Paul Seymour, Krzysztof Choromanski, Stephan Thomasse, Alex Scott, Sang-Il Oum and Jacob Fox.