A threshold for the Maker-Breaker clique game
We study the Maker-Breaker k-clique game played on the edge set of the random graph G(n, p). In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G(n, p), until all the edges are claimed. Maker wins if he claims all the edges of a k-clique; Breaker wins otherwise. We determine that the threshold for the graph property that Maker can win this game is at , for all k > 3, thus proving a conjecture from Ref. [Stojakovi? and Szab, Random Struct Algor 26 (2005), 204223]. More precisely, we conclude that there exist constants such that when the game is Maker's win a.a.s., and when it is Breaker's win a.a.s.
clique game random graphs positional games