利用者:Hrtauo/フリードマンのSSCG関数

単純なサブキュービックグラフから作られるSSCG関数は、各頂点の次数が最大3である有限の単純なグラフです。単純なサブキュービックグラフG1 、 G ₂ 、...のシーケンスがあり、任意の自然数kに対し各グラフGiが最大で_i _+ｋ個の頂点を持ち、 i < jがない場合はGiが（に同形的に埋め込まれる）である_とします。つまり、） Gjのマイナーグラフです。

Robertson-Seymourの定理は、サブキュービックグラフ（単純かどうかに関係なく）が同相の埋め込み可能性によって十分に根拠があることを証明しており、そのようなシーケンスが無限ではないことを意味します。したがって、 kの値ごとに、最大長のシーケンスがあります。関数SSCG（ k ） ^[1]は、単純なサブキュービックグラフの長さを示します。関数SCG（ k ） ^[2]は、（一般的な）サブキュービックグラフの長さを示します。

SCGシーケンスはSCG（0）= 6で始まりますが、その後、急成長階層で_{fε2* ₂}

と同じように増加します。

SSCG関数はSSCG（0）= 2、SSCG（1）= 5で始まり、その後物凄い速さで成長します。 SSCG（2）= 3×2 ^{（3×2 ⁹⁵ ）} −8≈3.241704× ^{1035775080127201286522908640066}およびその小数展開は...11352349133049430008で終了します。 Adam P. Goucherは、SSCGとSCGの漸近的成長率の間に質的な違いはないと主張しています。彼は「SCG（ n ）≥SSCG（ n ）であることは明らかですが、SSCG（4 n + 3）≥SCG（ n ）であることも証明できます」と書いています。 ^[3]

これらも参照してください[編集]

ノート[編集]

参考文献[編集]

[[Category:グラフ理論]] [[Category:整礎性]] [[Category:順序構造]] [[Category:離散数学の定理]] [[Category:数理論理学]] [[Category:数学]]

[1] [FOM] 274:Subcubic Graph Numbers

[2] [FOM] 279:Subcubic Graph Numbers/restated

[3] TREE(3) and impartial games | Complex Projective 4-Space

[1]

[2]

[3]