Clique game

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

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.