Encyclopedia

Friedman's SSCG function

Fast-growing function

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated July 17, 2026

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

01Background

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.

02SSCG function

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

03SCG 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)$ ".

Watch videos about Friedman's SSCG functionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Friedman's SSCG function”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

SSCG(3) sequence.png by LightbulbMEOW, CC BY-SA 4.0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Friedman's SSCG function

01Background

02SSCG function

03SCG function

Sources and credits

Related topics

Goodstein's theorem

Paris-Harrington theorem

Kanamori-McAloon theorem