Friedman's SSCG function
 | This article needs additional citations for verification. (January 2025) |
In mathematics, a simple subcubic graph (SSCG) is a finite simple graph in which each vertex has a degree of 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 (for some integer k) and for no i < j is Gi homeomorphically embeddable into (i.e. is a graph minor of) Gj.
The Robertson–Seymour theorem proves that subcubic graphs (simple or not) are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. Then, by applying Kőnig's lemma on the tree of such sequences under extension, for each value of k there is a sequence with maximal length. The function SSCG(k)[1] denotes that length for simple subcubic graphs. The function SCG(k)[2] denotes that length for (general) subcubic graphs.
The SCG sequence begins SCG(0) = 6, but SCG(1) explodes to a value equivalent to fε2*2 in the fast-growing hierarchy.
The SSCG sequence begins slower than SCG, SSCG(0) = 2, SSCG(1) = 5, but then grows rapidly. SSCG(2) = 3 × 2(3 × 295) − 8 ≈ 3.241704 × 1035775080127201286522908640065. Its first and last 20 digits are 32417042291246009846...34057047399148290040. SSCG(2) has in total 35775080127201286522908640066 digits. SSCG(3) is much larger than both TREE(3) and TREETREE(3)(3), that is, you have TREE(3) different unique nodes.
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(n) ≥ SSCG(n), but I can also prove SSCG(4n + 3) ≥ SCG(n)."[3]
The function was proposed and studied by Harvey Friedman.