フリードマンのSSCG関数

急成長中の機能

数学において、単純部分立方グラフ（SSCG）とは、各頂点の次数が最大で3である有限の単純グラフです。単純部分立方グラフの列、、… があり、各グラフは最大で個の頂点を持ち（ある整数 に対して）、 がに同相的に埋め込み可能（つまり がのマイナーグラフである）であるとします。 ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle G_{i}}$ ${\displaystyle i+k}$ ${\displaystyle k}$ ${\displaystyle i<j}$ ${\displaystyle G_{i}}$ ${\displaystyle G_{j}}$

ロバートソン・シーモア定理は、（単純または非単純を問わず）サブキュービックグラフが同相埋め込み可能性によって整基数であることを証明し、そのような列は無限にはなり得ないことを意味する。次に、ケーニヒの補題を拡張下のそのような列の木に適用すると、 の各値に対して最大長の列が存在する。関数 は、単純サブキュービックグラフの長さを表す。関数 は、（一般の）サブキュービックグラフの長さを表す。 ${\displaystyle k}$ ${\displaystyle {\text{SSCG}}(k)}$ ${\displaystyle {\text{SCG}}(k)}$

SSCG関数

サブキュービックグラフの列。列の - 番目のグラフには最大で個の頂点が含まれ、列内の後続のグラフに同相的に埋め込むことができるグラフはありません。は、そのような列の可能な最長の長さとして定義されます。 ${\displaystyle n}$ ${\displaystyle n+3}$ ${\displaystyle \operatorname {SSCG} (3)}$

ハーヴェイ・フリードマンはSSCGとSCGという2つの関数を定義した。彼は以下を満たす最大の整数を次のように定義した。 ^[1] ${\displaystyle {\text{SSCG}}(k)}$ ${\displaystyle n}$

それぞれが最大で個の頂点を持ち、 に対して が に同相的に埋め込み可能な、単純なサブキュービックグラフのシーケンスが存在します。 ${\displaystyle G_{1},\ldots ,G_{n}}$ ${\displaystyle G_{i}}$ ${\displaystyle i+k}$ ${\displaystyle i<j}$ ${\displaystyle G_{i}}$ ${\displaystyle G_{j}}$

数列の最初の数項は

${\displaystyle \operatorname {SSCG} (0)=2,}$

${\displaystyle \operatorname {SSCG} (1)=5,}$  そして

${\displaystyle \operatorname {SSCG} (2)=3\cdot 2^{3\cdot 2^{95}}\!\!-8=3\cdot 2^{118\,842\,243\,771\,396\,506\,390\,315\,925\,504}\!-8}$

${\displaystyle \qquad \qquad \;\approx \,3.241\,704\,229\cdot 10^{35\,775\,080\,127\,201\,286\,522\,908\,640\,065}}$

${\displaystyle \qquad \qquad \;\approx \,10^{3.5775\,\cdot \,10^{28}}.}$^[2]

次の項はTREE(3)より大きいことが示されている。^[3] ${\displaystyle {\text{SSCG}}(3)}$

フリードマンは、πで停止することが証明できるあらゆるチューリングマシンの停止時間よりも大きいことを示した。 ${\displaystyle {\text{SSCG}}(13)}$¹
₁-CA _{0 は}最大で^[a]個の記号で表され、 はテトレーションを表す。彼は の場合と同様の考え方を用いてこれを行っている。^[1] ${\displaystyle 2\uparrow \uparrow 2000}$ ${\displaystyle \uparrow \uparrow }$ ${\displaystyle {\text{TREE}}(3)}$

彼はまた、と比較して が全く目立たないことを指摘している。^[1] ${\displaystyle {\text{TREE}}(3)}$ ${\displaystyle {\text{SSCG}}(13)}$

SCG関数

後にフリードマンは、サブキュービックグラフに「単純」という条件を課す正当な理由がないことに気づき、条件を緩和して、以下を満たす最大のものを と定義した。^[4] ${\displaystyle {\text{SCG}}(k)}$ ${\displaystyle n}$

それぞれが最大で個の頂点を持ち、 に対して が に同相的に埋め込み可能な、サブキュービック グラフのシーケンスが存在します。 ${\displaystyle G_{1},\ldots ,G_{n}}$ ${\displaystyle G_{i}}$ ${\displaystyle i+k}$ ${\displaystyle i<j}$ ${\displaystyle G_{i}}$ ${\displaystyle G_{j}}$

数列の最初の項は であるが、次の項はグラハム数よりも大きい。さらに、は よりも大きい。^[3] ${\displaystyle {\text{SCG}}(0)=6}$ ${\displaystyle {\text{SCG}}(1)}$ ${\displaystyle {\text{SCG}}(3)}$ ${\displaystyle {\text{TREE}}^{{\text{TREE}}(3)}(3)}$

アダム・P・ガウチャーは、SSCGとSCGの漸近的成長率の間に質的な違いはないと主張している。彼は「 であることは明らかだが、 であることも証明できる」と書いている。^[5] ${\displaystyle {\text{SCG}}(n)\geq {\text{SSCG}}(n)}$ ${\displaystyle {\text{SSCG}}(4n+3)\geq {\text{SCG}}(n)}$

参照

• グッドスタインの定理
• パリス・ハリントン定理
• 金森・マカルーン定理
• クラスカルの木定理は、同様のTREE関数を導く。

注記

^ aフリードマンは実際にはこれを2 ^[2000] と書き、これは彼の記法では高さ2000の2の指数関数的積み重ねを表しています。^[6]

参考文献

1. Friedman, Harvey. "[FOM] 274:Subcubic Graph Numbers". 2024年4月7日時点のオリジナルよりアーカイブ。
2. Sloane, N. J. A. (編). 「数列A300403 (SSCG(i) >= nとなる最小の整数i)」.オンライン整数数列百科事典. OEIS財団.
3. YouTubeの「Immense Subcubic Graph Numbers - Numberphile」
4. Friedman, Harvey. "[FOM] 279:Subcubic Graph Numbers/restated". 2024年5月13日時点のオリジナルよりアーカイブ。
5. TREE(3)と公平ゲーム | 複素射影4次元空間
6. フリードマン、ハーヴェイ。「[FOM] 271:スミス論文の明確化」オハイオ州立大学数学科。2024年2月26日時点のオリジナルよりアーカイブ。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Friedman%27s_SSCG_function&oldid=1323425686"