Tutte seminar - Maria Chudnovsky

Friday, December 2, 2011 3:30 pm - 4:30 pm EST (GMT -05:00)

Forcing large transitive subtournaments

Speaker: Maria Chudnovsky
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The Erdos Hajnal Conjecture states roughly that a graph with some induced subgraph excluded has a large clique or a large stable set. A similar statement can be formulated for tournaments (a tournament is an orientation of a complete graph), replacing cliques and stable sets by transitive subtournaments; and the two conjectures turn out to be equivalent. This talk will survey a number of recent results related to the latter conjecture. In particular, we will discuss a new infinite class of tournaments excluding which forces large transitive subtournaments; to the best of our knowledge this is the first such class not obtained by the so-called substitution operation.