# 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*_{1}, *G*_{2}, ... 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*)^{[1]} denotes that length for simple subcubic graphs. The function SCG(*k*)^{[2]} 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)…))^{[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(4*n* + 3) ≥ SCG(*n*)."^{[4]}

## See also

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

## References

- ↑ http://www.cs.nyu.edu/pipermail/fom/2006-April/010305.html
- ↑ http://www.cs.nyu.edu/pipermail/fom/2006-April/010362.html
- ↑ https://cp4space.wordpress.com/2013/01/13/graph-minors/
- ↑ https://cp4space.wordpress.com/2012/12/19/fast-growing-2/comment-page-1/#comment-1036