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 G₁, G₂, ... such that each graph G_i has at most i + k vertices (for some integer k) and for no i < j is G_i homeomorphically embeddable into (i.e. is a graph minor of) G_j.

The Robertson–Seymour theorem proves that subcubic graphs (simple or not) 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(k) denotes that length for simple subcubic graphs. The function SCG(k) denotes that length for (general) subcubic graphs.

The SSCG sequence begins SSCG(0) = 2, SSCG(1) = 5, but then grows rapidly. SSCG(2) = 3 × 2^{3 × 295} − 9 ≈ 10^{3.5775 × 1028}. SSCG(3) is not only larger than TREE(3), it is much, much larger than TREE(TREE(…TREE(3)…)) where the total nesting depth of the formula is TREE(3) levels of the TREE function . Adam Goucher claims there’s 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)."

See also

• Goodstein's theorem
• Paris–Harrington theorem
• Kanamori–McAloon theorem
• Kruskal's tree theorem
• Robertson–Seymour theorem