For example, how to prove that TREE(n) for an extremely large n, like TREE(TREE(3)) is finite, in layman’s terms? Or is it impossible to understand the proof without being an expert in graph theory?
In: Mathematics
You’re correct in assuming that the existence of TREE(n) is not obvious. And just because we have an algorithm does not mean that the algorithm will complete – it could just get stuck in an infinite loop and we actually need a theorem which says that it will eventually end.
For TREE(n), the theorem is [Kruskal’s Tree Theorem](https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem). This is a result which puts constraints on lists of graphs and is maybe more easily seen with a different example. Consider Pythagorean Triples like (3,4,5) and (5,12,13), which are integer triples that fit in as the sides on a right triangle. If I have two triples, as above, then it is the case that either one is a multiple of the other or they are totally distinct from each other. So, for instance, (6,8,10) is a multiple of (3,4,5) and we can write (3,4,5) < (6,8,10), but we can’t write (3,4,5) < (5,12,13) or (5,12,13)<(3,4,5). A triple which is not a multiple of any other triple is called a Primitive Triple. So I might as the question: How comparable are Pythagorean Triples? For instance, if I have a list of 100 Triples can I guarantee that there will be at least *two* that are comparable? The answer to this is “No” because there are infinitely many primitive triples, so I can just use triples from the list of primitive triples and I’ll never run into a multiple.
If we have two trees, then we can sometimes compare them in a kinda similar way. If you have two trees T and S, then we can write T<S if we can view T as a smaller tree contained in S (in a technical way). So we can ask: If I have a list of trees T_1, T_2, T_3, etc then am I guaranteed to be able to find two trees so that T_i < T|_j when i<j. It’s a little different than the Pythagorean Triple example, but it’s the same kind of question that asks whether or not the size of a set can guarantee some kind of meaningful structure – which is common in math.
The answer to this is an affirmative. TREE(n) is the largest number that you *can’t* do this for when the trees have n-labels. But the theorem does guarantee that if you have too many such graphs, then you’ll always be able to compare at least two. As for why this theorem works, it’s actually not simple. I’m no graph theorist, but [people say](https://math.stackexchange.com/questions/2517207/proof-that-treen-where-n-3-is-finite) it is similar to Goodstein’s Theorem, which is another result dealing with huge numbers. In Goodstein’s Theorem, they find a fancy encoding for numbers which orders them in terms of the “complexity” of how they are written, and then show that the processes in Goodstein’s Theorem always make things less complex, which means that the sequences in Goodstein’s Theorem end. PBS Infinite Series had [an video](https://www.youtube.com/watch?v=oBOZ2WroiVY) on Goodstein’s theorem that explains it well.
Latest Answers