The TREE sequence begins TREE(1) = 1, TREE(2) = 3, then suddenly TREE(3) explodes to a value so enormously large that many other "large" combinatorial constants, such as Friedman's n(4), are extremely small by comparison. A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is A(A(...A(1)...)), where the number of A's is A(187196), and A() is a version of Ackermann's function: A(x) = 2↑^(x-1)x in Knuth's up-arrow notation. Graham's number, for example, is approximately A^64(4) which is much smaller than the lower bound A^(A(187196))(1).
This is the best one I've ever seen. The description seems fairly benign, but then one needs a ridiculous number like A(187196) to describe the applications of Ackermann's function to get a weak lower bound.
And the first two steps are rather small, which adds to the surprise.
TREE(3): http://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem
From the article:
The TREE sequence begins TREE(1) = 1, TREE(2) = 3, then suddenly TREE(3) explodes to a value so enormously large that many other "large" combinatorial constants, such as Friedman's n(4), are extremely small by comparison. A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is A(A(...A(1)...)), where the number of A's is A(187196), and A() is a version of Ackermann's function: A(x) = 2↑^(x-1)x in Knuth's up-arrow notation. Graham's number, for example, is approximately A^64(4) which is much smaller than the lower bound A^(A(187196))(1).