Juego de pandillas

El juego de la camarilla es un juego de posición en el que dos jugadores eligen alternativamente aristas, intentando ocupar una camarilla completa de un tamaño determinado.

El juego se parametriza mediante dos enteros n > k . El tablero de juego es el conjunto de todas las aristas de un grafo completo con n vértices. Los conjuntos ganadores son todas las camarillas con k vértices. Existen varias variantes de este juego:

• En la variante posicional fuerte del juego, gana el primer jugador que consiga una k -clique. Si nadie gana, el juego termina en empate.
• En la variante Maker-Breaker , el primer jugador (Maker) gana si logra mantener una k -clique; de ​​lo contrario, gana el segundo jugador (Breaker). No hay empates.
• En la variante Evitador-Ejecutor , el primer jugador (Evitador) gana si logra no mantener una k -clique. De lo contrario, gana el segundo jugador (Ejecutor). No hay empates. Un caso especial de esta variante es Sim .

El juego de la camarilla (en su variante de posición fuerte) fue presentado por primera vez por Paul Erdős y John Selfridge , quienes lo atribuyeron a Simmons. ^{[ 1 ]} Lo llamaron el juego de Ramsey , ya que está estrechamente relacionado con el teorema de Ramsey (véase más abajo).

El teorema de Ramsey implica que, siempre que coloreemos un grafo con 2 colores, existe al menos una camarilla monocromática. Además, para cada entero k , existe un entero R(k,k) tal que, en cada grafo con${\displaystyle n\geq R_{2}(k,k)}$vértices, cualquier coloración de 2 colores contiene una camarilla monocromática de tamaño al menos k . Esto significa que, si${\displaystyle n\geq R_{2}(k,k)}$, el juego de camarillas nunca puede terminar en empate. Un argumento de robo de estrategia implica que el primer jugador siempre puede forzar al menos un empate; por lo tanto, si${\displaystyle n\geq R_{2}(k,k)}$, el creador gana. Sustituyendo los límites conocidos por el número de Ramsey obtenemos que el creador gana siempre que${\displaystyle k\leq {\log _{2}n \over 2}}$.

Por otro lado, el teorema de Erdos-Selfridge ^{[ 1 ]} implica que Breaker gana siempre que${\displaystyle k\geq {2\log _{2}n}}$.

Beck mejoró estos límites de la siguiente manera: ^{[ 2 ]}

• El creador gana siempre ${\displaystyle k\leq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-10/3+o(1)}$;
• Breaker gana siempre${\displaystyle k\geq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-1+o(1)}$.

En lugar de jugar en grafos completos, el juego de la camarilla también se puede jugar en hipergrafos completos de órdenes superiores. Por ejemplo, en el juego de la camarilla sobre tríos, el tablero de juego es el conjunto de tríos de enteros 1,..., n (por lo que su tamaño es${\displaystyle {n \choose 3}}$), y los conjuntos ganadores son todos conjuntos de tríos de k enteros (por lo que el tamaño de cualquier conjunto ganador en él es${\displaystyle {k \choose 3}}$).

Según el teorema de Ramsey sobre ternas, si ${\displaystyle n\geq R_{3}(k,k)}$, Maker gana. El límite superior actualmente conocido en${\displaystyle R_{3}(k,k)}$es muy grande,${\displaystyle 2^{k^{2}/6}<R_{3}(k,k)<2^{2^{4k-10}}}$. Por el contrario, Beck ^{[ 3 ]} demuestra que${\displaystyle 2^{k^{2}/6}<R_{3}^{*}(k,k)<k^{4}2^{k^{3}/6}}$, dónde ${\displaystyle R_{3}^{*}(k,k)}$es el entero más pequeño tal que Maker tiene una estrategia ganadora. En particular, si${\displaystyle k^{4}2^{k^{3}/6}<n}$Entonces, el juego es una victoria para el Creador.