Description
Consider the following simple game between Builder and Chooser. They start with an empty graph. In each round a new vertex is added to the current graph and connected to all other vertices. Then Builder partitions the edge set in two and Chooser picks one part to be the current graph. Builder wins if the current graph contains a k-clique (k is fixed before they start to play). Can Builder win? If so, how many rounds are needed for that?
In the talk we consider several variants of this simple game and its connection to the following Erdos-Hajnal conjecture: For every k and g there is n such that every n-chromatic graph has a k-chromatic subgraph of girth at least g. Spoiler alert: Rodl solved the g=4 (triangle-free) special case in 1977, but the rest is still wide open.
We cover related recent results, joint with Bartosz Walczak and Seth Pettie.