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, it 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 to not 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).

Winning conditions

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

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)}$;
• Breaker wins whenever ${\displaystyle k\geq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-1+o(1)}$.

Ramsey game on higher-order hypergraphs

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}}$ ), 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}}$).

By Ramsey's theorem on triples, if ${\displaystyle n\geq R_{3}(k,k)}$, Maker wins. The currently known upper bound on ${\displaystyle R_{3}(k,k)}$ is very large, ${\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}}$, where ${\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}$ then the game is Maker's win.

References

1. Erdős, P.; Selfridge, J. L. (1973). "On a combinatorial game" (PDF). Journal of Combinatorial Theory . Series A. 14 (3): 298–301. doi: 10.1016/0097-3165(73)90005-8 . MR   0327313.
2. Beck, József (2002-04-01). "Positional Games and the Second Moment Method". Combinatorica. 22 (2): 169–216. doi:10.1007/s004930200009. ISSN   0209-9683.
3. Beck, József (1981). "Van der waerden and ramsey type games". Combinatorica. 1 (2): 103–116. doi:10.1007/bf02579267. ISSN   0209-9683.