Title: The Erdos-Hajnal Conjecture
Speaker: Krzysztof Choromanski, Columbia University
Date: Tuesday, October 2, 2012 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Undirected version of the Erdos-Hajnal Conjecture states that for any given undirected graph H there exists epsilon(H)>0 such that every undirected graph G, not containing H as an induced subgraph, contains either a clique or a stable set of size at least |G|^{epsilon(H)}. In its directed version (equivalent to the undirected one) undirected graphs are replaced by tournaments and cliques and stable sets by transitive subtournaments. The Conjecture is still open and in fact so far it was proved only for some very special cases. Some time ago Alon, Pach and Solymosi proposed a procedure that enabled to obtain bigger graphs satisfying the Conjecture from smaller ones. Recently Berger, Choromanski and Chudnovsky proved the Conjecture for a new infinite family of tournaments (so-called galaxies) that cannot be obtained by the procedure mentioned above. Even more recently Choromanski managed to replace this family by a larger one (so-called pseudogalaxies) that satisfies the Conjecture. For a given tournament H with at least three vertices the subset S of V(H) is called homogenous if for every w in V(H) - S either w is adjacent to every v in S or w is adjacent from every v in S. Besides we call it nontrivial if S contains at least two elements and not all the elements of V(H). Since the smallest counterexample to the Conjecture would be a tournament without nontrivial homogenous sets, those tournaments are of special interest. We call them basic tournaments. To the best of our knowledge so far the only basic tournaments for which the Conjecture is known are basic pseudogalaxies and few other tournaments (one 5-vertex tournament called C5 and few 6-vertex tournaments). In this talk I will show the sketch of the proof that pseudogalaxies satisfy the Conjecture. I will also show the sketch of the proof of the Conjecture for the tournament C5.
Finally I will show new upper bounds on coefficients epsilon(H) for basic H. Proofs of those bounds require the notion of the partitioning number of the tournament, an interesting parameter of the tournament.
Part of this talk is a joint work with Eli Berger and Maria Chudnovsky.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math