欲張りクリーク列 (Greedy clique sequences) は、Harvey Friedman が 2010年に定義した、グラフ理論による3つの急増加する関数を生み出す概念である[1]。フリードマンが定義した関数の中では最強の部類である。
定義
用語と記法
- クリーネ閉包を使って、\(\mathbb{Q}^*\) はすべての有理数のタプル、すなわちQ組 (Q-tuple) の集合を意味するものとする。タプルに1からインデックスをつけて下付き文字で記す。
- タプルの連結を角括弧であらわす。たとえば\(\langle (0,1), (2,3) \rangle = (0,1,2,3)\) である。
- \(a \in \mathbb{Q}^*\) に対して、\(a\) の上シフト \(\text{us}(a)\) を、\(a\) のすべての負ではない要素に1を加えたものであると定義する[2]。
- \(a,b \in \mathbb{Q}^*\) に対して、2項演算 \(\preceq\) と \(\prec\) を \(a \preceq b \Leftrightarrow \max(a) \leq \max(b)\) 及び \(a \prec b \Leftrightarrow \max(a) < \max(b)\) によって定義する。
- \(a,b \in \mathbb{Q}^*\) が順序等価 (order equivalent) であるとは、\(a\) と \(b\) が同じ長さであり、かつすべての \(i\) と \(j\) に対して \(a_i < a_j \Leftrightarrow b_i < b_j\) であることを意味する。
- 集合 \(E \subseteq \mathbb{Q}^*\) が順序不変 (order invariant) であるとは、すべての順序等価な \(x\) と \(y\) に対して \(x \in E \Leftrightarrow y \in E\) であることを意味する。
- \(H\) を \(\mathbb{Q}^*\) の要素を頂点に持つグラフとする。集合 \(E\) を、すべての \(H\) の辺 \((x,y)\) に対して、その連結 \(\langle x, y \rangle\) を \(E\) の要素とするような集合とする。\(E\) が順序不変であるとき、\(H\) は順序不変であるとする。\(H\) が順序不変のとき、\(H\) は無限の辺を持つ。
- 無向グラフ \(G\) の部分グラフ \(A\) が \(G\) のクリークであるとは、すべての \(x,y \in A\) に対して、\((x, y)\) が \(G\) の辺であるという意味である。
- 有向グラフ \(G\) の部分グラフ \(A\) が \(G\) の下降クリークであるとは、すべての \(x \succ y\) を満たす \(x,y \in A\) に対して、\((x, y)\) が \(G\) の辺であるという意味である[2]。
欲張りクリーク列とスレッド
タプルの集合 \(S \subseteq \mathbb{Q}^*\) に対して、列 \(\mathbf{x}\) をタプル \(x_i \in S\) に対する空ではないタプル \((x_1, x_2, \ldots, x_n)\) とする。これは \(\mathbb{Q}\) のタプルではなく、\(\mathbb{Q}\) のタプルのタプルである。
\(S\) の要素を頂点に持つ単純グラフ \(G\) の上シフト欲張りクリーク列 (upper shift greedy clique sequence を略して USGCS) \(\mathbf{x}\) は、以下のすべてが成立している列である。
- \(x_1\) は 0 のみである。
- \(m\) を \(2 \leq 2m \leq n - 1\) を満たす正の整数であるとする。\(Y\) を\(\langle x_1,x_2,\ldots, x_{2m-1}\rangle\) の連結とし、\(y = (Y_m, Y_{m+1}, \ldots, Y_{m+k-1})\) とする (\(k \in \mathbb{N}\))。
- \(x_{2m} \preceq y\) かつ \((y, 2m)\) は \(G\) の辺ではない。
- \(x_{2m + 1} = \text{us}(x_{2m})\)
- \(\{x_2, x_3, \ldots, x_n\}\) が \(G\) のクリークである。
\(S\) の要素を頂点に持つ有向グラフ \(G\) の上シフト欲張り下降クリーク列 (upper shift greedy down clique sequence を略して USGDCS) \(\mathbf{x}\) は、以下のすべてが成立している列である。
- \(x_1\) は 0 のみである。
- \(m\) と \(y\) を上と同様に定義する。
- 「\(x_{2m} = y\)」あるいは「\(x_{2m} \prec y\) かつ \((y, 2m)\) は\(G\) の辺ではない」
- \(x_{2m+1} = \text{us}(x_{2m})\)
- \(\{x_2, x_3, \ldots, x_n\}\) が \(G\) の下降クリークである。
\(\mathbf{x}\) のスレッドは、\((1,2,...,n)\) の部分列 \((u_1, u_2, \ldots, u_r)\) で、以下のように帰納的に定義される。
- \(u_1 = 1\)
- \(u_i\) が定義されている時に、\(u_{i+1}\) を次のように決める。\(j \in [u_i, 2^{u_i}]\) の中で、\(x_j \prec x_{u_i}\) が成立するような \(j\) を選ぶ（そのような \(j\) が存在しなければ \(u_{i+1}\) は定義されない）。そのような \(j\) が複数あるときには、その中で \(\max(x_j)\) が最大の \(j\) を選ぶ。そのような \(j\) が複数あるときには、その中で最大の \(j\) を選ぶ。そして、\(u_{i+1} = j\) とする。
スレッド \(u\) について \(2^{u_r} \leq n\) の時に、そのスレッドは開いたスレッドであるとする。つまり、\(u_{r+1}\) を \(j \in [u_r, 2^{u_r}]\) の範囲でフルに探したけれどみつからなかった、ということである。
- \(G\) の上シフト欲張りクリーク列 \(\mathbf{x}\) が、開いたスレッド \(u\) を持つ時に、\(\mathbf{x}\) は \(G\) の開放上シフト欲張りクリーク列であるとする。
- \(G\) の上シフト欲張り下降クリーク列 \(\mathbf{x}\) が、開いたスレッド \(u\) を持つ時に、\(\mathbf{x}\) は \(G\) の開放上シフト欲張りクリーク下降列であるとする。
欲張りクリーク関数
以下の急増加する関数を定義する。
- \(\text{USGCS}(k)\) は、\(S = \mathbb{Q}^k\) としたときに「\(S\) の要素を頂点に持つすべての順序不変な単純グラフ \(G\) が、最大でも \(N\) の長さの開放上シフト欲張りクリーク列を持っている」と言える最小の整数 \(N\) である。
- \(\text{USGDCS}(k)\) は、\(S = \mathbb{Q}^k\) としたときに「\(S\) の要素を頂点に持つすべての順序不変な有向グラフ \(G\) が、最大でも \(N\) の長さの開放上シフト欲張りクリーク下降列を持っている」と言える最小の整数 \(N\) である。
- \(\text{USGDCS}_2(k)\) は、\(\text{USGDCS}(k)\) の定義において \(S = \mathbb{Q}^k \cup \mathbb{Q}^{k+1}\) としたものである。
関数の増加速度
ここでは、\(n\) は自然数とする。まずは、次の理論を定義する。
- SRP 理論は、ZFC に、すべての \(n\) に対して「\(n\)-Stationary Ramsey Property を持つラムゼイ基数 (Ramsey cardinal) が存在する」という公理を加えたものである。
- SRP+ 理論は、ZFC に、「すべての \(n\) に対して\(n\)-Stationary Ramsey Property を持つラムゼイ基数が存在する」という公理を加えたものである。
- HUGE 理論は、ZFC に、すべての \(n\) に対して「\(n\)-膨大基数 (\(n\)-huge cardinal) が存在する」という公理を加えたものである。
- HUGE+ 理論は、ZFC に、「すべての \(n\) に対して \(n\)-膨大基数が存在する」という公理を加えたものである。
この時、それぞれの関数の増加速度は次のようになる。
- USGCS と USGDCS は、SRPによって証明可能な再帰関数をすべて支配し、SRP+によって証明可能な再帰関数である。
- USGDCS2 は、HUGEによって証明可能な再帰関数をすべて支配し、HUGE+によって証明可能な再帰関数である。