Clique game
The clique game is a positional game where two players alternately pick edges, trying to occupy a complete clique of a given size.
The game is parameterized by two integers n > k. The game-board is the set of all edges of a complete graph on n vertices. The winning-sets are all the cliques on k vertices. There are several variants of this game:
- In the strong positional variant of the game, the first player who holds a k-clique wins. If no one wins, the game is a draw.
- In the Maker-Breaker variant, the first player wins if he manages to hold a k-clique, otherwise the second player wins. There are no draws.
- In the Avoider-Enforcer variant, the first player wins if he manages not to hold a k-clique. Otherwise, the second player wins. There are no draws. A special case of this variant is Sim.
Winning conditions
implies that, whenever we color a graph with 2 colors, there is at least one monochromatic clique. Moreover, for every integer k, there exists an integer R such that, in every graph with vertices, any 2-coloring contains a monochromatic clique of size at least k. This means that, if, the clique game can never end in a draw. a Strategy-stealing argument implies that the first player can always force at least a draw; therefore, if, Maker wins. By substituting known bounds for the Ramsey number we get that Maker wins whenever.On the other hand, the Erdos-Selfridge theorem implies that Breaker wins whenever.
Beck improved these bounds as follows:
- Maker wins whenever ;
- Breaker wins whenever.
Ramsey game on higher-order hypergraphs
By Ramsey's theorem on triples, if , Maker wins. The currently known upper bound on is very large,. In contrast, Beck proves that, where is the smallest integer such that Maker has a winning strategy. In particular, if then the game is Maker's win.