| Monday, January 21st, 2013 | 4pm-5pm | Burnside 1205 |
The celebrated Erdos-Hajnal Conjecture says that for every undirected graph H there exist ε(H), c(H) > 0 such that every undirected graph G that does not contain H as an induced subgraph contains either a clique or a stable set of size at least c(H)|G|ε(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 in the most general scenario. For a long time it was known only for a few small graphs. Some time ago Alon, Pach and Solymosi proposed a procedure that enables to obtain bigger graphs satsfying the Conjecture from the smaller ones that satisfy it. Recently Berger, Choromanski and Chudnovsky managed to prove the Conjecture for a new infinite family of tournaments that cannot be obtained in such a way (so-called galaxies). As a corollary they got that among all tournaments of at most 5 vertices all but at most one satisfy the Conjecture. The missing one was a 5-vertex tournament in which every vertex has outdegree 2 (tournament C5). However the Conjecture was also proven for this tournament (Choromanski). Even more recently Choromanski managed to extend the results for galaxies and proved the Conjecture for a larger family of tournaments, so-called constellations. We call a tournament prime if it does not have nontrivial homogeneous sets. Prime tournaments are important since if the Conjecture is not true then the smallest counterexample is prime. Until very recently the only prime tournaments for which the Conjecture was known were: prime constellations, tournament C5 and two six-vertex tournaments for which the Conjecture could be proven using methods analogous to those used in te proof of C5. However recently Choromanski proposed a new procedure that enables to construct bigger tournaments satisfying the Conjecture from the smaller ones (so-called gadgets). The smaller tournaments in fact have to satisfy a little bit stronger version of the Conjecture. An interesting property of the proposed procedure is that a tournament that is constructed using it does not necessarily have nontrivial homogeneous sets (which is always the case for the procedure proposed by Alon, Pach and Solymosi). As a corollary, the Conjecture was proven for many new infinite classes of prime tournaments. Some time ago the structural characterization of tournaments satisfying the Conjecture in the strongest, linear sense (i.e with ε(H)=1) was given (see: "Tournaments and coloring", Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott, Seymour, Thomasse). However the question whether there exist tournaments satisfying the Conjecture in almost linear sense (i.e for every 0<ε(H)<1 but not for ε(H)=1) remained open. This question was answered by Choromanski, Chudnovsky and Seymour who gave a complete structural characterization of all tournaments with this weird property (so-called pseudocelebrities).
This talk will summarize recent progress in working on the Conjecture. Part of the talk about galaxies is a joint work with Eli Berger and Maria Chudnovsky. Part of the talk about pseudocelebrities is a joint work with Maria Chudnovsky and Paul Seymour.