Forcing large transitive subtournaments
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1