Friedman's SSCG function


In mathematics, a simple subcubic graph is a finite simple graph in which each vertex has degree at most three. Suppose we have a sequence of simple subcubic graphs G1, G2,... such that each graph Gi has at most i + k vertices and for no i < j is Gi homeomorphically embeddable into Gj.
The Robertson–Seymour theorem proves that subcubic graphs are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. So, for each value of k, there is a sequence with maximal length. The function SSCG denotes that length for simple subcubic graphs. The function SCG denotes that length for subcubic graphs.
The SCG sequence begins SCG = 6, but then explodes to a value equivalent to fε2*2 in the fast-growing hierarchy.
The SSCG sequence begins SSCG = 2, SSCG = 5, but then grows rapidly. SSCG = 3 × 2 − 8 ≈ 3.241704 ⋅ 1035775080127201286522908640066 and its decimal expansion ends in...11352349133049430008.
SSCG is much larger than both TREE and TREETREE. Adam P. Goucher claims there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It's clear that SCG ≥ SSCG, but I can also prove SSCG ≥ SCG."