[Math] Looking to get a handle on SSCG(3) (which is much, much larger than TREE(3))

combinatoricsgraph theory

TREE numbers grow rapidly: TREE(1) = 1, TREE(2) = 3, and a lower bound for TREE(3) is A(A(…A(1)…)), where the number of As is A(187196) and A(n) is a version of Ackerman's function. That's mind-bendingly large, but also somewhat definitely quantified.

SSCG (Simple Subcubic Graph) numbers grow more rapidly: SSCG(0) = 2, SSCG(1) = 5, SSCG(2) = 3*2^(3*2^95) – 9, or approximately 10^(3.6*10^28). SSCG(3) is claimed to be larger than TREE(TREE(…(TREE(3))…)) for some very large number of nested TREE operations, but I have no clue how many there are. Anybody know what might bound this depth (preferably from below, but also from above)?

Best Answer

I think it will be extremely difficult to find "good" lower and upper bounds, but

$$SSCG(3)>>TREE^{TREE(3)}(3)$$

shows that $SSCG$ and $SCG$ create numbers far beyond usual googolism, even with very small arguments. $TREE(3)$ is already extremely big, even in googolism-standards, far exceeding the $\Gamma_0$-level, but the $SSCG-$ and $SCG-$ functions apparently easily surpass it.

Maybe $\Sigma(100)$ is larger than $SSCG(3)$, but if so, it will probably not be a "good" upper bound. The Rayo-function or Loader's number might surpass $SSCG(3)$. "Good" lower bounds also will extremely difficult to be found, if such a monster like $TREE^{TREE(3)}(3)$ is much much smaller.

Finding where $SSCG(3)$ lies in the fast growing hierarchy would be the first step to establish good bounds. I do not know whether this has already be done.