Rutgers Discrete Mathematics Seminar

Title: Tournament Heroes

Speaker: Maria Chudnovsky, Columbia University

Date: Wednesday, March 2, 2011 3:15 PM**

Location: Hill Center, Room 423, Rutgers University, Busch Campus, Piscataway, NJ **(NOTE: SPECIAL TIME AND PLACE)


The chromatic number of a tournament T is the smallest number of transitive tournaments that partition V(T). Let us say that a tournament S is a hero if for every tournament T not containing S, the chromatic number of T is at most a constant c(S). Recently, in joint work with Eli Berger, Krzysztof Choromanski, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour and Stephan Thomasse, we proved a theorem that gives a complete description of all heroes. This talk will describe the result, and survey some of the proof ideas.