Игра Clique - Clique game

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

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

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

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

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

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

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

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

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

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

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

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

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