Friedman's SSCG function

Template:Short description Template:Multiple issues 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,\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$.

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. $\mathrm{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,\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 [[Reverse mathematics#Π11 comprehension Π11-CA0|ΠTemplate:Su-CA₀]] with at most $2\uparrow \uparrow 2000$Template:Ref label 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,\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
• Hydra game

Notes

Template:Note label Friedman actually writes this as 2^[2000], which denotes an exponential stack of 2's of height 2000 using his notation.