查看“︁TREE函数”︁的源代码

'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。

== 定义 ==

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

* 删除一个叶子节点。
* 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。

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

# 所有树的顶点至多有<math>n</math>种不同的颜色；
# <math>T_k</math>至多有<math>k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

=== tree(n) ===
<math>\rm tree(n)</math>(注意大小写)被称为'''弱tree函数'''，它研究的不是染色树，而是普通树。

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

# <math>T_k</math>至多有<math>n+k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

== 取值 ==

=== n较小时 ===
对于<math>\rm TREE(n)</math>，有：

<math>\rm TREE(1)=1</math>

<math>\rm TREE(2)=3</math>

对于<math>\rm tree(n)</math>，有：

<math>\rm tree(1)=2</math>

<math>\rm tree(2)=5</math>

<math>{\rm tree(3)>844,424,930,131,960}</math>

=== TREE(3) ===
和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。

HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>、的一个下界：

\({\rm TREE(3)}>H_{\varphi(1\omega,3)\cdot\varphi(1\omega)}({\rm tree(tree(3)+1)})\)(其中H为[[增长层级#哈代层级|哈代层级]]，下同)

=== tree(4) ===
2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：

<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>