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

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

サブキュービックグラフとは各頂点が最大3の次数を持つグラフである。この記事内では、サブキュービックグラフは多重グラフであってもよい(同じ2頂点間の辺が2つ以上あるものや、両端点が同じ頂点である辺をもつものもグラフとみなす)し、連結でなくてもよい。与えられた整数kに対し、サブキュービックグラフの列 G₁, G₂,.. を、全てのグラフ G_i が最大 i+k の頂点を持つような列で、i < j のとき G_i は G_j の位相マイナー（ G_j の「端点の片方が次数2である辺」を縮約したり、辺や頂点を取り除いたりすることを繰り返して 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点に潰す操作に対応している。

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

ここで許されるグラフを単純グラフ(どの辺も2つの端点は別の頂点であり、2つの端点が等しい辺の組が存在しないグラフ)のみとし、シンプル・サブキュービックグラフ数を定義、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}}\)

グラフマイナー定理との関係

グラフ間の関係として有名なものに、「マイナー」と「位相マイナー」がある。これらは名前が似ているものの、異なる概念である。

特に、関数SCGやSSCGが自然数全域で定義されていることを示すには、「グラフマイナーの定理」と呼ばれる、グラフ間のマイナー関係についての定理が用いられているが、これをそのまま位相マイナー関係に変えた命題は成り立たないことがわかっている。FriedmanはSCG関数を位相マイナーを用いて定義したので、一見するとSCG関数がしっかり定義されてるかは疑わしい。

しかし、サブキュービックグラフ同士では、マイナー関係と位相マイナー関係は同値となる。そのため、マイナーと位相マイナーのどちらで定義しても同じ関数となるので問題ない。

サブキュービックグラフでないグラフ同士では、マイナーと位相マイナーは別物であり、これらを用いて作られる関数の値も異なることに注意せよ。例えば、(根付き、根無しに関わらず)木のマイナー関係と位相マイナー関係は異なるので、SCGと同様に関数を作ると増大度は著しく変わる可能性がある。また、一般のグラフを用いてSCGのような関数を定義すると、マイナー関係であれば自然数全域に定義できるが、位相マイナー関係では全域に定義されない。

外部リンク

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