サブキュービックグラフ数

サブキュービックグラフ数はとても速く成長する組合せ論的関数の出力である。Harvey Friedmanによって開発された。

サブキュービックグラフとは各頂点が最大3の次数を持つグラフである。この記事内では、サブキュービックグラフはマルチグラフであってもよいし、連結でなくてもよい。与えられた整数kに対し、サブキュービックグラフの列 G₁, G₂,.. を、全てのグラフ G_i が最大 i+k の頂点を持つような列で、i < j のとき G_i は G_j に位相同型的埋め込み可能（ G_j の辺を縮約したり取り除いたり頂点を取り除いたりすることを繰り返して G_i にすることができること）でないものとする。

Friedman はこの列が無限の長さにはならないことを証明した。そして、そのような列の最大長を SCG(k) とする。

特定の値

SCG(0)=6 を示すことは簡単である。最初のグラフは一つのループで、2番目は2点とそれを結ぶ辺で作られる。次の4つのグラフは接続されてない 3, 2, 1, 0 の頂点である。このようにすべての列はピークがあり、衰退していく。SCG(1) はとても大きく、多くのnで \(f_{\varepsilon_0^\omega}(n)\) を超える。Googology Wiki の Hyp cos がより詳細な結果を示している（外部リンクの節を参照）。

SCG(k) の k として負の値を与えることもできる。たとえば SCG(-1)=1 であり、その1つは空グラフである。

Friedman は SCG(13) は \(\Pi^1_1\)-\(\text{CA}_0\) によって²⁰⁰⁰2個 (2^22...222, 2000個の2) 以内の記号で停止することが証明可能であるようないかなるチューリングマシンの実行時間よりも大きいことを証明した。あまり多くのことは知られていないが SCG(13) >> TREE(3) であることは分かっている。だが SCG(n) は計算可能であるため、ビジービーバー関数にはかなわない。

SCG(n) の急増加関数での増加率は ブーフホルツのψ関数に関して任意の自然数 \(n\) に対して \(\psi_0(\Omega_n)\) を超えることが知られており、上界は竹内・フェファーマン・ブーフホルツ順序数 で与えられると推測されている。

行列による解釈

関数 SCG を定義する別の方法として、以下のように行列を用いるものがある。サブキュービックグラフの接続行列 (incidence matrix) とは、各成分が 0, 1, 2 のいずれかであり、各列の和はちょうど2、各行の和は3以下であるような行列のことをいう。与えられた非負整数kに対し、n 個の接続行列の列 M₁, M₂, ..., M_n で、各 M_i の行数は i+k 以下であり、i < j のとき、M_j は次の操作を繰り返し施してもM_iにはならないものを考える。

1. 行または列の順番を入れ替える。
2. 列の一部を消去する。
3. 行の一部を消去し、和が2でない列を消去する。
4. 2つの行 A, B と自然数 i で、行 A+B の第 i 番目が 2 であり、行 A+B の合計が 5 以下であるものを選ぶ。行 A と B を除去し、行 A+B を追加する。そして i 番目の列を除去する。

このとき、SCG(k) は n として取りうる最大の値に一致する。

注: 接続行列の行、列は各々サブキュービックグラフの頂点、辺に対応している。また、1は頂点または辺の番号の入れ替え、2は辺の除去、3は頂点とそれに隣接する辺の除去、4は頂点 A と B をつなぐ辺 i を1点に潰す操作に対応している。

シンプル・サブキュービックグラフ数

ここで許されるグラフをシンプルな物のみ(マルチグラフなどは無し)とし、シンプル・サブキュービックグラフ数を定義、SSCGとする。SSCG(2)<<TREE(3)<<SSCG(3)である。というか、大きなn(たとえばn=TREE(3))に対してもTREEⁿ(3)<<SSCG(3)である。

値と下限

• SSCG(0) = 2
• SSCG(1) = 5
• SSCG(2) \(\geq 3*2^{3*2^{95}}-8 \approx 10^{3.5775*10^{28}}\)

外部リンク

• en:User blog:Hyp cos/SCG(n) and some related