クリックゲーム

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

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

• このゲームの強力な位置的変種では、 k個のクリークを最初に保持したプレイヤーが勝利する。誰も勝たなかった場合は引き分けとなる。
• メーカー・ブレーカー方式では、最初のプレイヤー（メーカー）がk個のクリークを維持できれば勝利となり、そうでなければ2番目のプレイヤー（ブレーカー）が勝利となる。引き分けはない。
• 回避者-執行者バリアントでは、最初のプレイヤー（回避者）がk-クリークを保持しない場合に勝ちます。そうでない場合は、2番目のプレイヤー（執行者）が勝ちます。引き分けはありません。このバリアントの特殊なケースはSimです。

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

ラムゼーの定理は、グラフを 2 色で彩色すると、少なくとも 1 つの単色クリークが存在することを示唆している。さらに、任意の整数kに対して、ある整数R(k,k)が存在し、すべてのグラフにおいて、${\displaystyle n\geq R_{2}(k,k)}$頂点数 が 1 の場合、任意の 2 彩色には少なくともkのサイズの単色クリークが含まれます。これは、${\displaystyle n\geq R_{2}(k,k)}$、この派閥ゲームは引き分けで終わることは決してない。戦略盗用論証は、最初のプレイヤーが常に少なくとも引き分けを強制できることを意味する。したがって、もし${\displaystyle n\geq R_{2}(k,k)}$、Maker が勝ちます。Ramsey 数に既知の境界を代入すると、Maker が勝つのは、$\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の三つ組の集合です(したがってそのサイズは${\displaystyle {n \choose 3}}$)、勝利セットはすべてk個の整数の三つ組の集合です (したがって、その中の勝利セットのサイズは${\displaystyle {k \choose 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}}}$対照的に、 ベック^{[ 3 ]} は、${\displaystyle 2^{k^{2}/6}<R_{3}^{*}(k,k)<k^{4}2^{k^{3}/6}}$、 どこ ${\displaystyle R_{3}^{*}(k,k)}$は、Makerが勝利戦略を持つ最小の整数である。特に、${\displaystyle k^{4}2^{k^{3}/6}<n}$そうなると、ゲームはメーカーの勝利となる。