派閥ゲーム

クリークゲームは、2 人のプレイヤーが交互にエッジを選択し、指定されたサイズの クリークの完全占有を試みる位置ゲームです。

このゲームは2つの整数n > kによってパラメータ化されます。ゲームボードは、n頂点の完全グラフのすべての辺の集合です。勝利集合は、 k頂点のすべてのクリークです。このゲームにはいくつかのバリエーションがあります。

• 強ポジショナルバリアントでは、最初にkクリークを獲得したプレイヤーが勝利します。誰も勝利しない場合は引き分けとなります。
• メイカー・ブレーカーバリアントでは、最初のプレイヤー（メイカー）がkクリークを保持できれば勝ち、そうでなければ2番目のプレイヤー（ブレーカー）が勝ちます。引き分けはありません。
• 回避者-執行者バリアントでは、最初のプレイヤー（回避者）がkクリークを保有しなかった場合、勝利します。そうでない場合は、2番目のプレイヤー（執行者）が勝利します。引き分けはありません。このバリアントの特殊なケースとして、Simがあります。

クリークゲーム（その強ポジショナルな変種）は、ポール・エルデシュとジョン・セル​​フリッジによって初めて提示され、彼らはそれをシモンズに帰した。^{[1]彼らはそれを}ラムゼーの定理（下記参照） と密接に関連していることから、ラムゼーゲームと呼んだ。

勝利条件

ラムゼーの定理によれば、グラフを2色で彩色するときは必ず、少なくとも1つの単色クリークが存在する。さらに、任意の整数kに対して、任意の頂点を持つグラフにおいて、任意の2色彩色に少なくともkの大きさの単色クリークが含まれるような整数R(k,k)が存在する。これは、 の場合、クリークゲームが引き分けで終わることは決してないことを意味する。戦略窃盗の議論によれば、最初のプレイヤーは常に少なくとも1回の引き分けを強制できるため、 の場合、メーカーが勝つ。ラムゼー数に既知の境界を代入すると、 の場合は必ずメーカーが勝つことがわかる。 ${\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}}$

ラムゼーの三つ組 定理によれば、 ならばMaker が勝ちます。現在知られている の上限は非常に大きく、 です。対照的に、 ベック^[3]は が で あることを証明しています。ここで はMaker が勝利戦略を持つ最小の整数です。特に、 ならば、ゲームはMakerの勝ちです。 ${\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}$

参考文献

1. Erdős, P. ; Selfridge, JL (1973). 「組合せゲームについて」(PDF) . Journal of Combinatorial Theory . Series A. 14 (3): 298– 301. doi : 10.1016/0097-3165(73)90005-8 . MR  0327313.
2. Beck, József (2002-04-01). 「ポジショナルゲームと第二モーメント法」. Combinatorica . 22 (2): 169– 216. doi :10.1007/s004930200009. ISSN  0209-9683.
3. ベック、ヨーゼフ (1981)。 「ファン・デル・ワールデンとラムジータイプのゲーム」。コンビナトリカ。1 (2): 103–116。土井:10.1007/bf02579267。ISSN  0209-9683。