# Clique game

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Clique_game
> Markdown URL: https://mediated.wiki/source/Clique_game.md
> Source: https://en.wikipedia.org/wiki/Clique_game
> Source revision: 1202103612
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Positional game}}
The '''clique game''' is a [positional game](/source/positional_game) where two players alternately pick edges, trying to occupy a complete [clique](/source/Clique_(graph_theory)) 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](/source/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](/source/Strong_positional_game) 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](/source/Maker-Breaker_game), 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](/source/Avoider-Enforcer_game), 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](/source/Sim_(pencil_game)).

The clique game (in its strong-positional variant) was first presented by [Paul Erdős](/source/Paul_Erd%C5%91s) and [John Selfridge](/source/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](/source/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](/source/Ramsey's_theorem) (see below).

== Winning conditions ==
[Ramsey's theorem](/source/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](/source/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](/source/J%C3%B3zsef_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](/source/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](/source/J%C3%B3zsef_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

---
Adapted from the Wikipedia article [Clique game](https://en.wikipedia.org/wiki/Clique_game) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Clique_game?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.