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

Comment on the [answer by "Deedlit"](http://mathoverflow.net/questions/93828/how-large-is-tree3/95588#95588):

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

<hr>

Comment on the [answer by "Feldman Denis"](http://mathoverflow.net/questions/93828/how-large-is-tree3/93986#93986):

> [`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](http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf) 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](http://www.cs.nyu.edu/pipermail/fom/2006-March/010279.html) to [the one mentioned in Deedlit's posting](http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html).