Return to Revisions

(Following are two comments, posted this way because I ("r.e.s.") cannot post comments directly.)

Comment on the answer by "Deedlit":

He does this by showing that TREE(3) must be very large - specifically, he constructs a sequence of more than n(4) rooted trees labeled from {1,2,3} such that Ti has at most i vertices, for no i,j with i<j do we have Ti homeomorphically embeddable into Tj, and each tree contains either a 2 label or a 3 label. We can obviously continue this with tree(n(4)) trees with all labels 1.

That's not quite right. His first tree T1 uses label 3 (so this label cannot be used later at all), followed by more than n(4) trees using labels 1,2 -- not, as you wrote, using labels 2,3. It's because of the way these latter {1,2}-labelled trees are constructed, that they can nevertheless be followed by a long sequence of trees using only label 1. (I show the beginning of his sequence in my other comment below, using bracket expressions in which the bracket-types (),[],{} correspond to his labels 1,2,3 respectively.)

In fact, we can do somewhat better than this; we can replace the n(4) above by F(4), where F(4) is defined as the length of the longest sequence of sequences x1,x2,…xn from {1,2,3,4} such that xi has length i+1 and for no i,j with i<j do we have xi a subsequence of xj.

Actually, we can do even better (although these may be relatively "small" adjustments?) ... Specifically, by playing with various ways to start a long embedding-free sequence, one can do better than the one shown below constructed by Friedman, but still using his method of coding n()- or F()-type longest-word-sequences via certain subtrees. For example, one can find sequences that demonstrate (in Deedlit's notation)

$TREE(3) \geq tree(N) + N \geq H_{\vartheta (\Omega^{\omega}, 0)}(N)$

where

$N = F_{\omega}^3 F_{\omega+1} {F_\omega}^2 F(4)$

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0() = F()$ (rather than beginning with $F_0(x) = x+1$).

Comment on the answer by "Feldman Denis":

[TREE(3) is] the length of the longest sequence (T2,T3,T4,…,Tn) of labeled trees such that Tk has at most k nodes labeled a or b, and Ti is not a subtree of Tj for i<j.

Rather than "is not a subtree of", that should be "is not homeomorphically embedded in", which is a very much more stringent requirement. (There might not even exist a longest such sequence in the less-stringent case. A similar situation occurs for Friedman's n() function -- in that case, the relation "is not a subsequence of" is more stringent than "is not a substring of" -- there being no longest sequence in the latter case.) With this correction, and by starting with T2, the length of the resulting sequence will of course be TREE(3) - 1.

BTW, a convenient representation of TREE(3) uses nested bracket expressions (well-formed in the usual way with pairs of matching brackets) involving only three bracket-types -- say (),[],{} -- each rooted tree being uniquely represented by a nest of such brackets (up to isomorphism with respect to sibling order). TREE(3) is then the length of a longest sequence (T1,T2,T3,T4,…,Tn) of nests such that each Tk has at most k bracket pairs and for no i<j is Ti embedded in Tj. Here X is embedded in Y means that X can be obtained from Y by erasing zero or more matching bracket-pairs.

(Note that, because T1 must be some single bracket pair which cannot then appear in any later nest in an embedding-free sequence, an equivalent definition is obtained by assuming T1={}, so TREE(3) is one greater than the length of a longest embedding-free sequence (T2,T3,T4,…,Tn) (starting with index 2) of nests formed as before but using only two bracket types (),[].)

Another thing to note is that TREE(3) assumes rooted trees with unordered siblings, so, for example, the nests ([]()) and (()[]) are not regarded as distinct. Some authors have treated wqo's for rooted trees with ordered siblings, with corresponding "longest sequence" results.

To illustrate the use of bracket expressions, here is a representation of the initial tree sequence used by Friedman to prove the lower bound mentioned by the OP:

T1  {}
T2  [[]]
T3  [()()]
T4  [((()))]
T5  ([][][][])
T6  ([][][](()))
T7  ([][](()()()))
T8  ([][](()(())))
T9  ([][](((((()))))))
T10 ([][]((((())))))
T11 ([][](((()))))
T12 ([][]((())))
T13 ([][](()))
T14 ([][]())
...

NB: It should be noted that the article linked by the OP does not treat Friedman's TREE function, but a rather different function TR. The confusion may be partly due to the fact that "TR" is also what Friedman called the TREE function before he changed it to the latter name in a follow-up article to the one mentioned in Deedlit's posting.