Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 15.12.2014 at 12:20 in S1, there is the following noon lecture:

Excluding pairs of tournaments

Krzysztof Choromanski

Abstract

The celebrated Erdos-Hajnal Conjecture states that for any given undirected graph H there exists epsilon(H)>0 such that every H-free n-vertex undirected graph has a clique or stable set of size at least n^{epsilon(H)}. In the equivalent directed version, undirected graphs are replaced by tournaments and cliques/stable sets by transitive subtournaments. The Conjecture is still open. This is the case for most graphs H also for its weaker version when one forbids both a graph H and its complement H^{c}.

In this talk we will describe some recent techniques that enabled us to prove the weaker version of the Conjecture for several new tournaments H. We will also explain how those techniques may be potentially used to prove the Conjecture for the remaining six vertex tournament for which it is still open.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010