SCG函数 & SSCG函数

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

定义

图的嵌入

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

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

SCG(n)

给定正整数n，$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$被定义为满足以下条件的“图列”$\{G_k\}$的最大长度：

1. 所有图的每个顶点度数$\le 3$；
2. $G_k$至多有$n+k$个顶点；
3. 对于正整数$k<l$，$G_k$不能嵌入到$G_l$中。

SSCG(n)

$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$是$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$在简单图上的限制。

给定正整数n，$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$被定义为满足以下条件的“图列”$\{G_k\}$的最大长度：

1. 所有图的每个顶点度数$\le 3$ 且无自环和重边；
2. $G_k$至多有$n+k$个顶点；
3. 对于正整数$k<l$，$G_k$不能嵌入到$G_l$中。

有限性证明

$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$和$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$的序列总是有限的，这可由Robertson-Seymour定理保证。

Robertson-Seymour定理说明，有限图的嵌入关系是一个良拟序，良拟序的定义参考这里。

也就是说，任意无限张图构成的序列中，必存在两张图，前面的图能嵌入到后面的图中。这就证明了$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$和$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$的有限性。

取值

对于较小的n，我们有

$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{0}\mathrm{)}\mathrm{=}\mathrm{6}$

$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{0}\mathrm{)}\mathrm{=}\mathrm{2}$

$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{1}\mathrm{)}\mathrm{=}\mathrm{5}$

$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{2}\mathrm{)}\ge 3\times 2^{3\times 2^{95}}-8$

以及一些下界

$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{1}\mathrm{)}>f_{{\epsilon }_2\times 2}(f_{{\epsilon }_0\times 2}(f_{{\epsilon }_0+1}(f_{\epsilon }{}_0(f_{{\omega }^{\omega }+1}(f_{{\omega }^5+{\omega }^2+\omega }(f_{{\omega }^2\times 3+1}(f_{{\omega }^2\times 2+1}(f_{{\omega }^2+\omega \times 3+1}(f_{{\omega }^2+1}(f_{{\omega }^2}(3\times 2^{3\times 2^{95}})))))))))))$

$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{2}\mathrm{)}>f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\omega }})}(f_{{\epsilon }_2\times 2}(f_{{\epsilon }_0\times 2}(f_{{\epsilon }_0+1}(f_{\epsilon }{}_0(f_{{\omega }^{\omega }+1}(f_{{\omega }^5+{\omega }^2+\omega }(f_{{\omega }^2\times 3+1}(f_{{\omega }^2\times 2+1}(f_{{\omega }^2+\omega \times 3+1}(f_{{\omega }^2+1}(f_{{\omega }^2}(3\times 2^{3\times 2^{95}}))))))))))))$

$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{3}\mathrm{)}>\mathrm{T}\mathrm{R}\mathrm{E}{\mathrm{E}}^{\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}\mathrm{(}\mathrm{3}\mathrm{)}}\mathrm{(}\mathrm{3}\mathrm{)}$

$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{2}\mathrm{)}$的下界小于$\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}\mathrm{(}\mathrm{3}\mathrm{)}$，目前无法判断它们之间的大小关系。

增长率

我们可以证明$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}\ge \mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}\ge \mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{4}\mathrm{n}\mathrm{+}\mathrm{3}\mathrm{)}$。因此$\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$和$\mathrm{S}\mathrm{S}\mathrm{C}\mathrm{G}\mathrm{(}\mathrm{n}\mathrm{)}$有相同的增长率。

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

然而这仍然是一个未解决的问题，目前我们只对所有平面图进行了编序，并且这一步就用掉了所有$\psi ({\mathrm{\Omega }}_{\omega })$之下的序数。因此，这两个函数的增长率下界为$\psi ({\mathrm{\Omega }}_{\omega })$。

我们认为增长率的上界可能为$\psi ({\mathrm{\Omega }}_{\omega +1})$。

我们尚不知道这两个函数增长率的具体取值。