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 ${\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.

SSCG function

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

Harvey Friedman defined two functions, SSCG and SCG. He 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 {\text{SSCG}}(0)=2}$, ${\displaystyle {\text{SSCG}}(1)=5}$, and ${\displaystyle {\text{SSCG}}(2)=3\cdot 2^{3\cdot 2^{95}}-8\approx 10^{3.5775\cdot 10^{28}}}$.^[2]

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 TREE(3).^[1]

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

SCG function

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:^[3]

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}}$.

Most of the results that hold true for ${\displaystyle {\text{SSCG}}(k)}$ also hold true for ${\displaystyle {\text{SCG}}(k)}$.

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)}$".^[4]

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.^[5]