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 the Builder partitions the edge set into two, and the 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.