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 (Maker) wins if he manages to hold a k-clique, otherwise the second player (Breaker) wins. There are no draws.
• In the Avoider-Enforcer variant, the first player (Avoider) wins if he manages not to hold a k-clique. Otherwise, the second player (Enforcer) wins. There are no draws. A special case of this variant is Sim.

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 ${\displaystyle n\geq R_{2}(k,k)}${\displaystyle n\geq R_{2}(k,k)} vertices, any 2-coloring contains a monochromatic clique of size at least k. This means that, if ${\displaystyle n\geq R_{2}(k,k)}${\displaystyle n\geq R_{2}(k,k)}, 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 ${\displaystyle n\geq R_{2}(k,k)}${\displaystyle n\geq R_{2}(k,k)}, Maker wins. By substituting known bounds for the Ramsey number we get that Maker wins whenever ${\displaystyle k\leq {\log _{2}n \over 2}}${\displaystyle k\leq {\log _{2}n \over 2}}.

On the other hand, the Erdos-Selfridge theorem^[1] implies that Breaker wins whenever ${\displaystyle k\geq {2\log _{2}n}}${\displaystyle k\geq {2\log _{2}n}}.

Beck improved these bounds as follows:^[2]

• Maker wins whenever ${\displaystyle k\leq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-10/3+o(1)}${\displaystyle k\leq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-10/3+o(1)};
• Breaker wins whenever ${\displaystyle k\geq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-1+o(1)}${\displaystyle k\geq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-1+o(1)}.

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 ${\displaystyle {n \choose 3}}${\displaystyle {n \choose 3}} ), and winning-sets are all sets of triplets of k integers (so the size of any winning-set in it is ${\displaystyle {k \choose 3}}${\displaystyle {k \choose 3}}).

By Ramsey's theorem on triples, if ${\displaystyle n\geq R_{3}(k,k)}${\displaystyle n\geq R_{3}(k,k)}, Maker wins. The currently known upper bound on ${\displaystyle R_{3}(k,k)}${\displaystyle R_{3}(k,k)} is very large, ${\displaystyle 2^{k^{2}/6}<R_{3}(k,k)<2^{2^{4k-10}}}${\displaystyle 2^{k^{2}/6}<R_{3}(k,k)<2^{2^{4k-10}}}. In contrast, Beck ^[3] proves that ${\displaystyle 2^{k^{2}/6}<R_{3}^{*}(k,k)<k^{4}2^{k^{3}/6}}${\displaystyle 2^{k^{2}/6}<R_{3}^{*}(k,k)<k^{4}2^{k^{3}/6}}, where ${\displaystyle R_{3}^{*}(k,k)}${\displaystyle R_{3}^{*}(k,k)} is the smallest integer such that Maker has a winning strategy. In particular, if ${\displaystyle k^{4}2^{k^{3}/6}<n}${\displaystyle k^{4}2^{k^{3}/6}<n} then the game is Maker's win.

• Positional games

• Articles with short description
• Short description matches Wikidata