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.