查看“︁SCG函数 & SSCG函数”︁的源代码

'''SCG（SubCubic Graph number）函数'''和'''SSCG（Simple SubCubic Graph number）函数'''是两个由 Harvey Friedman 提出的图论函数。

=== 定义 ===

==== 图的嵌入 ====
给定两个图<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：

* 删除一个度为0的点，即没有连接边的点。
* 删除一条边。
* 对于一条连接两个不同顶点的边<math>e=(u,v)</math>，删除该边，并且合并两个顶点为一个新顶点<math>x</math>(也即将所有的边<math>(p,q)</math>中出现的<math>u</math>和<math>v</math>都替换为<math>x</math>)。

==== SCG(n) ====
给定正整数n，<math>\rm SCG(n)</math>被定义为满足以下条件的“图列”<math>\{G_k\}</math>的最大长度：

# 所有图的每个顶点度数<math>\leq3</math>；
# <math>G_k</math>至多有<math>n+k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>G_k</math>不能嵌入到<math>G_l</math>中。

==== SSCG(n) ====
<math>\rm SSCG(n)</math> 是 <math>\rm SCG(n)</math>在简单图上的限制。

给定正整数 n，<math>\rm SCG(n)</math> 被定义为满足以下条件的“图列”<math>\{G_k\}</math> 的最大长度：

# 所有图的每个顶点度数 <math>\leq3</math> 且无自环和重边；
# <math>G_k</math> 至多有 <math>n+k</math> 个顶点；
# 对于正整数 <math>k<l</math>，<math>G_k</math> 不能嵌入到 <math>G_l</math> 中。

=== 有限性证明 ===
<math>\rm SCG(n)</math> 和 <math>\rm SSCG(n)</math> 的序列总是有限的，这可由 Robertson-Seymour 定理保证。

Robertson-Seymour 定理说明，有限图的嵌入关系是一个良拟序，良拟序的定义参考[[TREE函数#有限性证明|这里]]。

也就是说，任意无限张图构成的序列中，必存在两张图，前面的图能嵌入到后面的图中。这就证明了 <math>\rm SCG(n)</math> 和 <math>\rm SSCG(n)</math> 的有限性。

=== 取值 ===
对于较小的 n，我们有

* <math>\rm SCG(0)=6</math>
* <math>\rm SSCG(0)=2</math>
* <math>\rm SSCG(1)=5</math>
* <math>{\rm SSCG(2)}\geq{3\times2^{3\times2^{95}}}-8</math>

以及一些下界<ref>HypCos (2014). SCG(n) and some related. ''(EB/OL), Googology Wiki''.  https://googology.fandom.com/wiki/User_blog:Hyp_cos/SCG(n)_and_some_related</ref><ref>大老李 (2024). 如何证明SSCG(3)>TREE(3)？[How to prove SSCG(3) > TREE(3)?]. ''(EB/OL), Zhihu''. https://www.zhihu.com/question/665933771/answer/3619954642</ref>

* <math>{\rm SCG(1)}>f_{\varepsilon_2\times2}(f_{\varepsilon_0\times2}(f_{\varepsilon_0+1}(f_\varepsilon_0(f_{\omega^\omega+1}(f_{\omega^5+\omega^2+\omega}(f_{\omega^2\times3+1}(f_{\omega^2\times2+1}(f_{\omega^2+\omega\times3+1}(f_{\omega^2+1}(f_{\omega^2}({3\times2^{3\times2^{95}}})))))))))))</math>
* <math>{\rm SCG(2)}>f_{\psi(\Omega^{\Omega^\omega})}(f_{\varepsilon_2\times2}(f_{\varepsilon_0\times2}(f_{\varepsilon_0+1}(f_\varepsilon_0(f_{\omega^\omega+1}(f_{\omega^5+\omega^2+\omega}(f_{\omega^2\times3+1}(f_{\omega^2\times2+1}(f_{\omega^2+\omega\times3+1}(f_{\omega^2+1}(f_{\omega^2}({3\times2^{3\times2^{95}}}))))))))))))</math>
* <math>{\rm SSCG(3)}>{\rm TREE^{\rm TREE(3)}(3)}</math>

<math>\rm SCG(2)</math> 的下界小于 <math>\rm TREE(3)</math>，目前无法判断它们之间的大小关系。

=== 增长率 ===
我们可以证明 <math>{\rm SSCG(n)}\geq{\rm SCG(n)}\geq{\rm SSCG(4n+3)}</math>。因此 <math>\rm SCG(n)</math> 和 <math>\rm SSCG(n)</math> 有相同的增长率。

类似于 [[TREE函数#增长率|TREE 函数的增长率]]，只要对所有图的嵌入关系进行编序，即可得出它们的增长率。

然而这仍然是一个未解决的问题，目前我们只对所有平面图进行了编序，并且这一步就用掉了所有 <math>\psi(\Omega_\omega)</math> 之下的序数。因此，这两个函数的增长率下界为 <math>\psi(\Omega_\omega)</math>。我们认为增长率的上界可能为 <math>\psi(\Omega_{\omega+1})</math>。

尚不知道这两个函数增长率的具体取值。
== 参考资料 ==
<references />{{默认排序:相关问题}}
[[分类:记号]]