Friedman's SSCG function

In mathematics, especially graph theory, 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 ${\displaystyle G_{1}}$, ${\displaystyle G_{2}}$, ... such that each graph ${\displaystyle G_{i}}$ has at most ${\displaystyle i+k}$ vertices (for some integer ${\displaystyle k}$) and for no ${\displaystyle i<j}$ is ${\displaystyle G_{i}}$ homeomorphically embeddable into (i.e. is a graph minor of) ${\displaystyle 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 ${\displaystyle k}$ there is a sequence with maximal length. The function ${\displaystyle {\text{SSCG}}(k)}$ denotes that length for simple subcubic graphs. The function ${\displaystyle {\text{SCG}}(k)}$ denotes that length for (general) subcubic graphs.

Harvey Friedman defined two functions: SSCG and SCG.

Friedman defined ${\displaystyle {\text{SSCG}}(k)}$ as the largest integer ${\displaystyle n}$ satisfying the following:^[1]

There is a sequence ${\displaystyle G_{1},\ldots ,G_{n}}$ of simple subcubic graphs such that each ${\displaystyle G_{i}}$ has at most ${\displaystyle i+k}$ vertices and for no ${\displaystyle i<j}$ is ${\displaystyle G_{i}}$ homeomorphically embeddable into ${\displaystyle G_{j}}$.

The first few terms of the sequence are

${\displaystyle \operatorname {SSCG} (0)=2,}$

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

${\displaystyle \operatorname {SSCG} (2)=3\cdot 2^{3\cdot 2^{95}}\!\!-8=3\cdot 2^{118\,842\,243\,771\,396\,506\,390\,315\,925\,504}\!-8}$

${\displaystyle \qquad \qquad \;\approx \,3.241\,704\,229\cdot 10^{35\,775\,080\,127\,201\,286\,522\,908\,640\,065}}$

${\displaystyle \qquad \qquad \;\approx \,10^{3.5775\,\cdot \,10^{28}}.}$^[2]

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

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

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

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

There is a sequence ${\displaystyle G_{1},\ldots ,G_{n}}$ of subcubic graphs such that each ${\displaystyle G_{i}}$ has at most ${\displaystyle i+k}$ vertices and for no ${\displaystyle i<j}$ is ${\displaystyle G_{i}}$ homeomorphically embeddable into ${\displaystyle G_{j}}$.

The first term of the sequence is ${\displaystyle {\text{SCG}}(0)=6}$, while the next term ${\displaystyle {\text{SCG}}(1)}$ is bigger than Graham's number. Furthermore, ${\displaystyle {\text{SCG}}(3)}$ is bigger than ${\displaystyle {\text{TREE}}^{{\text{TREE}}(3)}(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 ${\displaystyle {\text{SCG}}(n)\geq {\text{SSCG}}(n)}$, but I can also prove ${\displaystyle {\text{SSCG}}(4n+3)\geq {\text{SCG}}(n)}$".^[5]

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

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