{{short description|Positional 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.<ref name="es">{{cite journal|last1=Erdős|first1=P.|last2=Selfridge|first2=J. L.|author2-link=John Selfridge|year=1973|title=On a combinatorial game|url=https://www.renyi.hu/~p_erdos/1973-10.pdf|journal=Journal of Combinatorial Theory|series=Series A|volume=14|issue=3|pages=298–301|doi=10.1016/0097-3165(73)90005-8|mr=0327313|author1-link=Paul Erdős|doi-access=free}}</ref> 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 <math>n \geq R_2(k,k)</math> vertices, any 2-coloring contains a monochromatic clique of size at least ''k''. This means that, if <math>n \geq R_2(k,k)</math>, 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 <math>n \geq R_2(k,k)</math>, Maker wins. By substituting known bounds for the Ramsey number we get that Maker wins whenever <math>k \leq {\log_2 n\over 2}</math>.
On the other hand, the Erdos-Selfridge theorem<ref name="es" /> implies that Breaker wins whenever <math>k \geq {2 \log_2 n}</math>.
Beck improved these bounds as follows:<ref name="Beck 2002">{{Cite journal|last=Beck|first=József|date=2002-04-01|title=Positional Games and the Second Moment Method|journal=Combinatorica|language=en|volume=22|issue=2|pages=169–216|doi=10.1007/s004930200009|issn=0209-9683}}</ref>
* Maker wins whenever <math>k \leq 2 \log_2 n - 2\log_2\log_2 n + 2\log_2 e - 10/3 + o(1)</math>; * Breaker wins whenever <math>k \geq 2 \log_2 n - 2\log_2\log_2 n + 2\log_2 e - 1 + o(1)</math>.
== 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 <math>{n \choose 3}</math> ), and winning-sets are all sets of triplets of ''k'' integers (so the size of any winning-set in it is <math>{k \choose 3}</math>).
By Ramsey's theorem on triples, if <math>n \geq R_3(k,k)</math>, Maker wins. The currently known upper bound on <math>R_3(k,k)</math> is very large, <math>2^{k^2/6} < R_3(k,k) < 2^{2^{4k-10}}</math>. In contrast, Beck<ref name="beck81">{{Cite journal|last=Beck|first=József|date=1981|title=Van der waerden and ramsey type games|journal=Combinatorica|language=en|volume=1|issue=2|pages=103–116|doi=10.1007/bf02579267|issn=0209-9683}}</ref> proves that <math>2^{k^2/6} < R^*_3(k,k) < k^4 2^{k^3/6}</math>, where <math>R^*_3(k,k)</math> is the smallest integer such that Maker has a winning strategy. In particular, if <math>k^4 2^{k^3/6} < n</math> then the game is Maker's win.
== References == {{reflist}}
Category:Positional games