So there is this famous TREE(3) function producing various trees.
Is there at least one way to compare any pair of such trees so that they can be viewed as ordered sequence?
If there is such a way, can we find the latest tree for TREE(3)? Or at least count how many seeds (nodes) this tree contains? I am assuming that the actual number of nodes will be growing much slower than the order sequence, so is it possible that the number of nodes is actually computable? Perhaps we could even compute that last tree in full?
I assume here is that if we know generation rules for TREE(3) trees, we can zip them in any direction so we can iterate backwards and essentially get the latest one without computing a really large number of their precursors first.
What got me thinking about that: There's a huge number of e.g. MD5 hashes, but it's not hard to figure out that the biggest MD5 hash is simply ffffffffffffffffffffffffffffffff. Perhaps that the biggest tree produced by TREE(3) is actually not that big? Or perhaps it is? Any information that we have about it?
As noted by commenter, the last tree is a single blue node. It has to be last because it is a topological minor to any other tree after first two.
As far as my understanding goes, TREE function is somewhat boring, and that's a good thing as far as mathematics go.
Since no tree should be a topological minor of any following tree, these trees have a backward iterating character, demonstrated by the second line of image, where a complex tree that fits in
Nvertices is followed by all possible topological minors of that tree, followed by another complex tree (can be called key-tree) with its family of minors, etc.It seems that the rate of production of such trees eventually becomes slightly lower than the linear increase of
N, but it has a huge head start so it takes a while to converge. Eventually in the sequence there would be the last key tree of unimaginably hugeNnodes followed by zero or more of its minors, after which the next potential key tree would be at least one node larger than permitted by then-currentN. Then the iteration will stop with a single blue node tree.On the head start. You may notice that the last tree in the image has 7 spare nodes. It is sufficient for it to have the top node and four leftmost nodes to be in that sequence, but it adds seven nodes more to iterate their possible minors, and while this happens the N will grow considerably.
I'm still not sure whether there is any algorithmic way to iterate this tree sequence forward. I'm sure it's pretty easy to order them and to find out the last one :)