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: The clique game (in its strong-positional variant) was first presented by Paul Erdős and John Selfridge, who attributed it to Simmons.
[1] They called it the Ramsey game, since it is closely related to Ramsey's theorem (see below).
Ramsey's theorem 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(k,k) 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[1] implies that Breaker wins whenever
Beck improved these bounds as follows:[2] Instead of playing on complete graphs, the clique game can also be played on complete hypergraphs of higher orders.
For example, in the clique game on triplets, the game-board is the set of triplets of integers 1,...,n (so its size is
), and winning-sets are all sets of triplets of k integers (so the size of any winning-set in it is
By Ramsey's theorem on triples, if
, Maker wins.
The currently known upper bound on
In contrast, Beck[3] proves that
is the smallest integer such that Maker has a winning strategy.
then the game is Maker's win.