// Workers AI · dad joke modeWhat did Friedman's SSCG function say? "I'm a hash above the rest.

Friedman's SSCG function is a mathematical function defined by Harvey Friedman. It is defined by ${\text{SSCG}}(k)$ as the largest integer $n$ satisfying the following:

There is a sequence $G_{1},\ldots ,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}$.

Later, Friedman defined the more general subcubic graphs ${\text{SCG}}(k)$.

Background

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 $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-quasi-ordered 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.

Harvey Friedman defined two functions: SSCG and SCG.

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. $\operatorname {SSCG} (3)$ is defined to be the longest possible length of such a sequence.

Friedman defined ${\text{SSCG}}(k)$ as the largest integer $n$ satisfying the following:

There is a sequence $G_{1},\ldots ,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

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

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

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

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

$\qquad \qquad \;\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, and that it cannot be proved to exist in that theory with less than $2\uparrow \uparrow 1000$ symbols, where $\uparrow \uparrow$ denotes tetration. He does this using a similar idea as with a similar statement he proved about ${\text{TREE}}(3)$.

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},\ldots ,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)\geq {\text{SSCG}}(n)$, but I can also prove ${\text{SSCG}}(4n+3)\geq {\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
• Hydra game

Notes

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