Игра в клики
Позиционная игра

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ ab Erdős, P. ; Selfridge, JL (1973). "О комбинаторной игре" (PDF) . Журнал комбинаторной теории . Серия A. 14 (3): 298– 301. doi : 10.1016/0097-3165(73)90005-8 . MR  0327313.
  2. ^ Бек, Йожеф (2002-04-01). «Позиционные игры и метод второго момента». Combinatorica . 22 (2): 169– 216. doi :10.1007/s004930200009. ISSN  0209-9683.
  3. ^ Бек, Йожеф (1981). «Игры типа Ван дер Вардена и Рэмси». Комбинаторика . 1 (2): 103–116 . doi : 10.1007/bf02579267. ISSN  0209-9683.
Взято с "https://en.wikipedia.org/w/index.php?title=Clique_game&oldid=1202103612"