TREE(3) is the famously absurdly large number that is the length of a longest list of rooted, 3-colored trees whose $i$th element has at most $i$ vertices, and for which no tree's vertices can be mapped to the vertices of a subsequent tree preserving color and inf relationships.

Some lower bounds of TREE(3) have been proven. Among them are $A^{A(187196)}(1)$, where the superscript denotes function iteration and $A(x) = 2\uparrow^{x-1}x$ (using Knuth up-arrows) is a version of the Ackermann function. More bounds appear in this Wikia article and here. These bounds are rather unsatisfying because there is no indication of how tight they are.

The only upper bound of TREE(3) that I have seen (other than, trivially, TREE($n$) for $n > 3$) has a similar derivation as a longest sequence of a more general type of graph; I can't find a reference at the moment. This upper bound is also unsatisfying because it is non-constructive.

Does anyone know of an explicit expression that is an upper bound of TREE(3)? Or is it so large that there is no hope to construct one?


$\ TREE(3)\ $ is far above the $\Gamma_0$-level of the fast growing hierarchy.

See here how insane large it is : https://sites.google.com/site/largenumbers/home/appendix/a/numbers3

I am not sure whether an upper bound is known. Nested Ackermann-functions do not come near to $\ TREE(3)\ $ at all. Conway chains and even Bowers's $3D$-arrays are still MUCH MUCH MUCH too small.


After discussing the problem with Andreas Weiermann, it appears there are no good upper bounds to TREE(3). One can derive a good asymptotic bound to TREE(n) on the order of $F_{\theta(\Omega^\omega \omega,0)}(n)$, however this does not in and of itself prove any bound to TREE(3).

I suppose it seems unlikely, given the asymptotic upper bound for TREE(n), that TREE(3) would exceed say $F_\alpha(3)$ for $\alpha$ much larger than $\theta(\Omega^\omega \omega,0)$, but this is speculative.


The underlying rationale will be as follows. The Tree(n) question can be translated into a problem of the length of effectively given bad sequences. I think this goes directly back to Friedman. Such effectively given bad sequences can be mapped into effectively descending sequences of ordinals using the reification technique. Effectively descending sequences can be bounded by the Hardy hierarchy (by say an old MLQ article by Buchholz, Cichon, Weiermann). This will also give a reasonable concrete upper bound for n=3. The problem in writing this up is that until now according to my judgement very few people were interested in it. Moreover the material would be considered as "folklore" and so a publication might be turned down.