FANDOM


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

サブキュービックグラフとは各頂点が最大3の次数を持つグラフである。(この記事内では、マルチグラフや接続されていないグラフもサブキュービックグラフともなる)サブキュービックグラフの列 G1, G2,.. を全てのグラフGiが最大i+kの頂点を持つような列で(kは任意の整数)i<jたる全てのGj位相同型的埋め込み可能でないものとする。

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

特定の値 編集

SCG(0).jpg
SCG(0)を証明するのは可能である。最初のグラフは一つのループで、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)は、最大20002(222...222 2000個の2)、記号では\(\Pi^1_1\)-\(\text{CA}_0\)、で停止することが証明可能であるような、いかなるチューリングマシンの実行時間よりも大きいことを証明した。あまり多くのことは知られていないが、SCG(13) >> TREE(3) であることは分かっている。だがSCG(n)は計算可能であるため、ラヨ数にはかなわない。

SCG(n)の急増加関数での増加率は\(\psi_{\Omega_1}(\Omega_\omega)\)ほどで、上限は竹内・フェファーマン・ブーフホルツ順序数である。

行列による解釈 編集

An alternate way of describing the SCG function is as follows. Define an incidence matrix as a matrix with entries in {0, 1, 2} where each column sums to exactly 2 and each row sums to at most 3. Given a nonnegative integer k, we construct a sequence of n incidence matrices M1, M2, ..., Mn such that each matrix Mi has at most i + k rows, and no matrix can be changed into an earlier one by repeated applications of any of the following processes:

  • Reordering rows or columns.
  • Deleting columns.
  • Deleting rows, then deleting any columns that do not sum to 2.
  • Adding two rows so their sum produces at least one 2, and deleting the column containing that 2.

SCG(k), then, is the largest possible value of n.

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

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

Goucherは\(SSCG(4n+3) \geq SCG(n)\)を証明した。[3]さらに、\(SSCG(3n+4) \geq 3 SCG(n)\)も証明できる。

値と下限 編集

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

出典 編集

  1. Harvey Friedman, FOM 279:Subcubic Graph Numbers/restated
  2. Adam Goucher, Graph minors
  3. Adam Goucher, TREE(3) and impartial games (see comment)

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki