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})$。

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