show/hide this revision's text 5 "TREE(3)" should be "lower bound on TREE(3)"; improve wording & notations

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 improve upon the one shown below sequence constructed by Friedman (displayed below), 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)

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

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0 = F$(, rather than beginning as usual with $F_0(x) = x+1$)x+1$. (Friedman showed that $F$ eventually dominates every $f_{\lt \omega^\omega}$ in the usual fast-growing hierarchy.)

Rather than "is not a subtree of", that should be "is not homeomorphically embedded inembeddable into", 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 and $F()$ functions concerning word-sequences: these use "is not a subsequence of" is more stringent rather than the less-stringent "is not a substring of" -- of", there being no longest sequence word-sequence in the latter case.) With this correction, and by starting with $T_2$, the length of the resulting sequence will of course be TREE(3) - 1.

BTW, a

A convenient representation way of TREE(3) uses representing these trees is to use 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). A lower bound on TREE(3) is then the length of a longest sequence $(T_1,T_2,T_3,T_4,…,T_n)$ (X_1,X_2,…,X_n)$ of nests such that each $T_k$ X_k$ has at most $k$ bracket pairs and for no $i \lt j$ X_i$ is $T_i$ embedded in a later $T_j$. Here X_j$, where $X$ is embedded in $Y$ means that $X$ can be obtained from $Y$ by erasing zero or more pairs of matching bracket-pairsbrackets. (Note thatThus, if $X$ is not embedded in $Y$, then the tree represented by $X$ is not inf-and-label-preserving embeddable into the tree represented by $Y$; the converse, because however, does not hold.)

Because $T_1$ X_1$ must be some single bracket pair bracket-pair which cannot then appear in any later nest in an embedding-free sequence, an equivalent definition is obtained by assuming it may be assumed that $T_1=\ X_1=\ ${}, so TREE(3) is one greater than the length of a longest embedding-free sequence $(T_2,T_3,T_4,…,T_n)$ (starting with index 2) of all later nests formed as before but using only the two bracket types bracket-types (),[]. )

Another thing to Also, note is that TREE(3) assumes rooted concerns 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.results.)
show/hide this revision's text 4 add link to a sketch of the example

(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 $T_i$ has at most $i$ vertices, for no $i,j$ with $i \lt j$ do we have $T_i$ homeomorphically embeddable into $T_j$, 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 $T_1$ 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 $x_1,x_2,…x_n$ from {1,2,3,4} such that $x_i$ has length $i+1$ and for no $i,j$ with $i \lt j$ do we have $x_i$ a subsequence of $x_j$.

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_{\omega}^2 \ F(4)$

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0() F_0 = F()$ F$ (rather than beginning with $F_0(x) = x+1$). I've posted a very terse derivation-sketch of this result.

Comment on the answer by "Feldman Denis":

[TREE(3) is] the length of the longest sequence $(T_2,T_3,T_4,…,T_n)$ of labeled trees such that $T_k$ has at most $k$ nodes labeled $a$ or $b$, and $T_i$ is not a subtree of $T_j$ for $i \lt 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 $T_2$, 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 $(T_1,T_2,T_3,T_4,…,T_n)$ of nests such that each $T_k$ has at most $k$ bracket pairs and for no $i \lt j$ is $T_i$ embedded in $T_j$. 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 $T_1$ 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 $T_1=\ ${}, so TREE(3) is one greater than the length of a longest embedding-free sequence $(T_2,T_3,T_4,…,T_n)$ (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.
show/hide this revision's text 3 switch to mathjax formatting
a sequence of more than n(4)$n(4)$ rooted trees labeled from {1,2,3} such that Ti$T_i$ has at most i$i$ vertices, for no i,j$i,j$ with $i <j\lt j$ do we have Ti$T_i$ homeomorphically embeddable into Tj, $T_j$, and each tree contains either a 2 label or a 3 label. We can obviously continue this with tree(n(4)) tree$(n(4))$ trees with all labels 1.

That's not quite right. His first tree T1$T_1$ uses label 3 (so this label cannot be used later at all), followed by more than n(4)$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 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) $n(4)$ above by F(4), $F(4)$, where F(4) $F(4)$ is defined as the length of the longest sequence of sequences x1,x2,…xn $x_1,x_2,…x_n$ from {1,2,3,4} such that xi $x_i$ has length i+1 $i+1$ and for no i,j $i,j$ with $i \lt j$ do we have $x_i$ a subsequence of $x_j$.

Actually, we can do even better (although these may be relatively "small" adjustments?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()- $n()$- or F()-type longest-word-sequences $F()$-type longest word-sequences via certain subtrees. For example, one can find sequences that demonstrate (in Deedlit's notation)

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

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

[TREE(3)TREE(3) is] the length of the longest sequence (T2,T3,T4,…,Tn)$(T_2,T_3,T_4,…,T_n)$ of labeled trees such that Tk$T_k$ has at most k$k$ nodes labeled a$a$ or b, $b$, and Ti$T_i$ is not a subtree of Tj$T_j$ for $i <j\lt 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()$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, $T_2$, 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)$(T_1,T_2,T_3,T_4,…,T_n)$ of nests such that each Tk$T_k$ has at most k$k$ bracket pairs and for no $i <j\lt j$ is Ti$T_i$ embedded in Tj. $T_j$. Here X$X$ is embedded in Y $Y$ means that X$X$ can be obtained from Y$Y$ by erasing zero or more matching bracket-pairs.

(Note that, because T1$T_1$ 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={$T_1=\ ${}, so TREE(3) is one greater than the length of a longest embedding-free sequence (T2,T3,T4,…,Tn)$(T_2,T_3,T_4,…,T_n)$ (starting with index 2) of nests formed as before but using only two bracket types (),[].)

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" 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.
show/hide this revision's text 2 mention an even larger result; deleted 14 characters in body
show/hide this revision's text 1