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

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

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

Harvey Friedman defined two functions: SSCG and SCG.

SSCG function

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

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

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

The first few terms of the sequence are

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

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

SSCG ⁡ ( 2 ) = 3 ⋅ 2 3 ⋅ 2 95 − 8 = 3 ⋅ 2 118 842 243 771 396 506 390 315 925 504 − 8 {\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}

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

≈ 10 3.5775 ⋅ 10 28 . {\displaystyle \qquad \qquad \;\approx \,10^{3.5775\,\cdot \,10^{28}}.}

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

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

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

SCG function

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

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

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

See also

Notes

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