On a Clique Game and the Erdős-Hajnal Problem on High-Chromatic High-Girth Subgraphs

For a fixed positive integer \(k\), two players, \(\textsf {Builder}\) and \(\textsf {Chooser}\), alternate turns playing the following game on a dynamically changing graph that is initially empty. In each round, \(\textsf {Builder}\) introduces a new vertex with edges to all previous vertices and then partitions the entire edge set into two subsets, after which \(\textsf {Chooser}\) deletes one of the two. \(\textsf {Builder}\) attempts to build a clique of size \(k\), while \(\textsf {Chooser}\) attempts to prevent that. We prove tower-type upper and lower bounds on how many rounds \(\textsf {Builder}\) needs to guarantee a \(k\)-clique.