Кликовая игра

Позиционная игра

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

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

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

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

Условия победы

Теорема Рамсея подразумевает, что всякий раз, когда мы раскрашиваем граф в два цвета, существует хотя бы одна одноцветная клика. Более того, для каждого целого числа k существует целое число R(k,k) такое, что в каждом графе с вершинами любая 2-раскраска содержит одноцветную клику размера не менее k . Это означает, что если , кликовая игра никогда не может закончиться вничью. Аргумент кражи стратегии подразумевает, что первый игрок всегда может добиться как минимум ничьей; следовательно, если , выигрывает Создатель. Подставив известные границы числа Рэмси, мы получим, что Создатель выигрывает всякий раз, когда . ${\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}}$

С другой стороны, теорема Эрдоша-Селфриджа ^[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)}$
• Брейкер всегда побеждает . ${\displaystyle k\geq 2\log _{2}n-2\log _{2}\log _{2}n+2\log _{2}e-1+o(1)}$

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

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

По теореме Рэмси о тройках, если , выигрывает Мейкер. Известная в настоящее время верхняя граница очень велика: . Напротив, Бек ^[3] доказывает, что , где – наименьшее целое число такое, что у Мейкера есть выигрышная стратегия. В частности, если тогда игра является победой Мейкера. ${\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}$

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

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