SCG函数 & SSCG函数 - 版本历史

2025年8月20日 (三) 08:17 Z

2025-08-20T08:17:05Z

←上一版本		2025年8月20日 (三) 16:17的版本
第58行：		第58行：
	尚不知道这两个函数增长率的具体取值。		尚不知道这两个函数增长率的具体取值。
	== 参考资料 ==		== 参考资料 ==
	<references />		<references />{{默认排序:相关问题}}
	[[分类:记号]]		[[分类:记号]]

Tabelog：修正参考资料

2025-07-30T07:26:54Z

修正参考资料

←上一版本		2025年7月30日 (三) 15:26的版本
第1行：		第1行：
	'''~~SCG(SubCubic~~ Graph ~~number)函数~~'''和'''~~SSCG(Simple~~ SubCubic Graph ~~number)函数~~'''~~是两个由Harvey Friedman提出的图论函数。~~		'''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>：		给定两个图<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：

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

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

第17行：		第17行：
	# 对于正整数<math>k<l</math>，<math>G_k</math>不能嵌入到<math>G_l</math>中。		# 对于正整数<math>k<l</math>，<math>G_k</math>不能嵌入到<math>G_l</math>中。

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

	~~给定正整数n，~~<math>\rm SCG(n)</math>被定义为满足以下条件的“图列”<math>\{G_k\}</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>\leq3</math> 且无自环和重边；
			# <math>G_k</math> 至多有 <math>n+k</math> 个顶点；
			# 对于正整数 <math>k<l</math>，<math>G_k</math> 不能嵌入到 <math>G_l</math> 中。

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

	~~<math>{\rm SSCG(2)}\geq{3\times2^{3\times2^{95}}}~~-~~8</math>~~		Robertson-Seymour 定理说明，有限图的嵌入关系是一个良拟序，良拟序的定义参考[[TREE函数#有限性证明\|这里]]。

	~~以及一些下界~~<~~ref~~>~~https://googology.fandom.com/wiki/User_blog:Hyp_cos/~~SCG(n)~~_and_some_related~~</~~ref~~><~~ref~~>~~https://www.zhihu.com/question/665933771/answer/3619954642~~</~~ref~~>		也就是说，任意无限张图构成的序列中，必存在两张图，前面的图能嵌入到后面的图中。这就证明了 <math>\rm SCG(n)</math> 和 <math>\rm SSCG(n)</math> 的有限性。

	<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>		=== 取值 ===
			对于较小的 n，我们有

	<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 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>

	<~~math~~>~~{\rm~~ SSCG(3)}>~~{\rm TREE^{\rm~~ TREE(3)}(3)}</~~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(2)</math>~~的下界小于~~<math>\rm TREE(3)</math>~~，目前无法判断它们之间的大小关系。~~		* <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>{\rm SSCG(n)}\geq{\rm SCG(n)}\geq{\rm SSCG(4n+3)}</math>。因此 <math>\rm SCG(n)</math> 和 <math>\rm SSCG(n)</math> 有相同的增长率。

	然而这仍然是一个未解决的问题，目前我们只对所有平面图进行了编序，并且这一步就用掉了所有<math>\psi(\Omega_\omega)</math>之下的序数。因此，这两个函数的增长率下界为<math>\psi(\Omega_\omega)</math>。		类似于 [[TREE函数#增长率\|TREE 函数的增长率]]，只要对所有图的嵌入关系进行编序，即可得出它们的增长率。

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

	~~我们尚不知道这两个函数增长率的具体取值。~~		尚不知道这两个函数增长率的具体取值。
	== 参考资料 ==		== 参考资料 ==
	<references />		<references />
	[[分类:记号]]		[[分类:记号]]

Apocalypse：创建页面，内容为“'''SCG(SubCubic Graph number)函数'''和'''SSCG(Simple SubCubic Graph number)函数'''是两个由Harvey Friedman提出的图论函数。 == 定义 == === 图的嵌入 === 给定两个图 $A$ 和 $B$ ，我们称 $A$ 能嵌入到 $B$ 中，如果 $B$ 能通过有限次以下操作得到 $A$ ： * 删除一个度为0的点，即没有连接边的点。 * 删除一条边。 * 对于一条连接两个不同…”

2025-07-17T21:39:10Z

创建页面，内容为“'''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的点，即没有连接边的点。 * 删除一条边。 * 对于一条连接两个不同…”

新页面

'''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>https://googology.fandom.com/wiki/User_blog:Hyp_cos/SCG(n)_and_some_related</ref><ref>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 />
[[分类:记号]]

SCG函数 & SSCG函数 - 版本历史

2025年8月20日 (三) 08:17 Z

Tabelog：​修正参考资料

Tabelog：修正参考资料