Friedman's SSCG function

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 $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. 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 $\text{SSCG}(k)$ denotes that length for simple subcubic graphs. The function $\text{SCG}(k)$ denotes that length for (general) subcubic graphs.

SSCG function

A sequence of subcubic graphs. The $n$-th graph in the sequence contains at most $n+3$ vertices, and no graph is homeomorphically embeddable within any later graph in the sequence. $\mathrm{SSCG}(3)$ is defined to be the longest possible length of such a sequence.

Harvey Friedman defined two functions, SSCG and SCG. He defined $\text{SSCG}(k)$ as the largest integer $n$ satisfying the following:

There is a sequence $G_1,\dots ,G_n$ of simple subcubic graphs such that each $G_i$ has at most $i+k$ vertices and for no $i<j$ is $G_i$ homeomorphically embeddable into $G_j$.

The first few terms of the sequence are

$\mathrm{SSCG}(0)=2,$

$\mathrm{SSCG}(1)=5,$  and

$\mathrm{SSCG}(2)=3\cdot 2^{3\cdot 2^{95}}-8=3\cdot 2^{118842243771396506390315925504}-8$

$\approx 3.241704229\cdot 10^{35775080127201286522908640065}$

$\approx 10^{3.5775\cdot 10^{28}}.$

It has been shown that the next term, $\text{SSCG}(3)$, is greater than TREE(3).

Friedman showed that $\text{SSCG}(13)$ is greater than the halting time of any Turing machine that can be proved to halt in Π¹
₁-CA₀ with at most $2\uparrow \uparrow 2000$^[a] symbols, where $\uparrow \uparrow$ denotes tetration. He does this using a similar idea as with $\text{TREE}(3)$.

He also points out that $\text{TREE}(3)$ is completely unnoticeable in comparison to $\text{SSCG}(13)$.

SCG function

Later, Friedman realized there was no good reason for imposing "simple" on subcubic graphs. He relaxes the condition and defines $\text{SCG}(k)$ as the largest $n$ satisfying:

There is a sequence $G_1,\dots ,G_n$ of subcubic graphs such that each $G_i$ has at most $i+k$ vertices and for no $i<j$ is $G_i$ homeomorphically embeddable into $G_j$.

The first term of the sequence is $\text{SCG}(0)=6$, while the next term $\text{SCG}(1)$ is bigger than Graham's number. Furthermore, $\text{SCG}(3)$ is bigger than ${\text{TREE}}^{\text{TREE}(3)}(3)$.

Adam P. Goucher claims there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It's clear that $\text{SCG}(n)\ge \text{SSCG}(n)$, but I can also prove $\text{SSCG}(4n+3)\ge \text{SCG}(n)$".

See also

• Goodstein's theorem
• Paris–Harrington theorem
• Kanamori–McAloon theorem
• Kruskal's tree theorem, which leads to the similar TREE function

Notes

^{^ a} Friedman actually writes this as 2^[2000], which denotes an exponential stack of 2's of height 2000 using his notation.