A Lower Bound for Kruskal's Weak Tree Function tree(3)

Abstract

We establish an explicit lower bound for Kruskal's weak tree function at n=3, proving that tree(3) >= 844,424,930,131,960 = 3 * 2^48 - 8. This is achieved by constructing an explicit sequence of unlabeled rooted trees satisfying the constraints of the weak tree function and carefully analyzing the combinatorics of the "leg elimination" process. Our bound significantly exceeds previous estimates and demonstrates that even for small arguments, the weak tree function exhibits rapid growth.

8 pages, 10 figures