Нажмите игру

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

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

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

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

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

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

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

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

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

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

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

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