Игра Clique - Clique game

В кликовая игра это позиционная игра где два игрока поочередно выбирают ребра, пытаясь занять полный клика заданного размера.

Игра параметризована двумя целыми числами п > k. Игровая доска - это набор всех ребер полный график на п вершины. Выигрышные наборы - это все клики на k вершины. Есть несколько вариантов этой игры:

• в сильный позиционный вариант игры, первый игрок, имеющий k-клика побеждает. Если никто не выиграет, это ничья.
• в Вариант Maker-Breaker , первый игрок (Создатель) выигрывает, если ему удается удержать k-clique, иначе выигрывает второй игрок (Breaker). Ничьих нет.
• в Вариант Avoider-Enforcer, первый игрок (Избегающий) побеждает, если ему удастся нет держать k-clique, иначе побеждает второй игрок (Enforcer). Ничьих нет. Частным случаем этого варианта является Сим.

Групповую игру (в ее сильнопозиционном варианте) впервые представил Пол Эрдёш и Джон Селфридж, который приписал это Симмонсу.^[1] Они назвали это Рэмси игра, поскольку он тесно связан с Теорема Рамсея (Смотри ниже).

Условия выигрыша

Теорема Рамсея означает, что всякий раз, когда мы раскрашиваем граф в 2 цвета, существует по крайней мере одна монохроматическая клика. Более того, для любого целого числа k, существует целое число R (к, к) такой, что в каждом графе с ${\displaystyle n\geq R_{2}(k,k)}$ вершин, любая 2-раскраска содержит монохроматическую клику размером не менее k. Это означает, что если ${\displaystyle n\geq R_{2}(k,k)}$, игра кликов никогда не может закончиться вничью. а Аргумент кражи стратегии подразумевает, что первый игрок всегда может добиться хотя бы ничьей; следовательно, если ${\displaystyle n\geq R_{2}(k,k)}$, Maker побеждает. Подставляя известные оценки для числа Рамсея, мы получаем, что Maker выигрывает всякий раз, когда ${\displaystyle k\leq {\log _{2}n \over 2}}$.

С другой стороны, теорема Эрдоша-Селфриджа^[1] означает, что Брейкер выигрывает всякий раз, когда ${\displaystyle k\geq {2\log _{2}n}}$.

Бек улучшили эти оценки следующим образом:^[2]

• Создатель выигрывает всякий раз, когда ${\displaystyle k\leq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-10/3+o(1)}$;
• Breaker выигрывает всякий раз, когда ${\displaystyle k\geq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-1+o(1)}$.

Игра Рамсея на гиперграфах высокого порядка

Вместо того, чтобы играть на полных графах, в игру с кликами можно также играть на полных гиперграфах более высоких порядков. Например, в клике на тройках игровое поле представляет собой набор троек целых чисел 1, ...,п (так что его размер ${\displaystyle {n \choose 3}}$ ), а выигрышные наборы - это все наборы троек k целые числа (так что размер любого выигрышного набора в нем равен ${\displaystyle {k \choose 3}}$).

К Теорема Рамсея на троек, если ${\displaystyle n\geq R_{3}(k,k)}$, Maker побеждает. Известная в настоящее время верхняя граница ${\displaystyle R_{3}(k,k)}$ очень большой, ${\displaystyle 2^{k^{2}/6}<R_{3}(k,k)<2^{2^{4k-10}}}$. В отличие, Бек ^[3] доказывает, что ${\displaystyle 2^{k^{2}/6}<R_{3}^{*}(k,k)<k^{4}2^{k^{3}/6}}$, куда ${\displaystyle R_{3}^{*}(k,k)}$ - наименьшее целое число, при котором у Maker есть выигрышная стратегия. В частности, если ${\displaystyle k^{4}2^{k^{3}/6}<n}$ тогда игра - победа Создателя.

Рекомендации

1. Эрдеш, П.; Селфридж, Дж. Л. (1973). «О комбинаторной игре» (PDF). Журнал комбинаторной теории. Серия А. 14 (3): 298–301. Дои:10.1016/0097-3165(73)90005-8. МИСТЕР  0327313.
2. Бек, Йожеф (01.04.2002). «Позиционные игры и метод второго момента». Комбинаторика. 22 (2): 169–216. Дои:10.1007 / s004930200009. ISSN  0209-9683.
3. Бек, Йожеф (1981). "Ван дер Варден и игры типа Рэмси". Комбинаторика. 1 (2): 103–116. Дои:10.1007 / bf02579267. ISSN  0209-9683.