Juego de camarilla

Juego posicional

El juego de camarilla es un juego posicional en el que dos jugadores eligen bordes alternativamente, intentando ocupar una camarilla completa de un tamaño determinado.

El juego está parametrizado por dos enteros n > k . El tablero de juego es el conjunto de todas las aristas de un grafo completo en n vértices. Los conjuntos ganadores son todas las camarillas en k vértices. Existen varias variantes de este juego:

• En la variante posicional fuerte del juego, el primer jugador que tenga una k -clique gana. Si nadie gana, el juego es un empate.
• En la variante Maker-Breaker , el primer jugador (Maker) gana si logra mantener un k -clique, de lo contrario gana el segundo jugador (Breaker). No hay empates.
• En la variante Avoider-Enforcer , el primer jugador (Avoider) gana si logra no tener una k -clique. En caso contrario, gana el segundo jugador (Enforcer). No hay empates. Un caso especial de esta variante es Sim .

El juego de camarilla (en su variante posicional 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 (ver más abajo).

Condiciones de victoria

El teorema de Ramsey implica que, siempre que coloreamos un grafo con 2 colores, hay al menos una camarilla monocromática. Además, para cada entero k , existe un entero R(k,k) tal que, en cada grafo con vértices, cualquier 2-coloración contiene una camarilla monocromática de tamaño al menos k . Esto significa que, si , 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 , Maker gana. Al sustituir límites conocidos por el número de Ramsey obtenemos que Maker gana siempre que . ${\displaystyle n\geq R_{2}(k,k)}$ ${\displaystyle n\geq R_{2}(k,k)}$ ${\displaystyle n\geq R_{2}(k,k)}$ ${\displaystyle k\leq {\log _{2}n \over 2}}$

Por otra parte, 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 que ; ${\displaystyle k\leq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-10/3+o(1)}$
• Breaker gana siempre que . ${\displaystyle k\geq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-1+o(1)}$

Juego de Ramsey sobre hipergrafos de orden superior

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

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

Referencias

1. Erdős, P. ; Selfridge, JL (1973). "Sobre un juego combinatorio" (PDF) . Journal of Combinatorial Theory . Serie A. 14 (3): 298–301. doi : 10.1016/0097-3165(73)90005-8 . MR  0327313.
2. Beck, József (1 de abril de 2002). "Juegos posicionales y el método del segundo momento". Combinatorica . 22 (2): 169–216. doi :10.1007/s004930200009. ISSN  0209-9683.
3. Beck, József (1981). "Juegos tipo Van der waerden y ramsey". Combinatoria . 1 (2): 103–116. doi :10.1007/bf02579267. ISSN  0209-9683.