Friedman's SSCG function

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

There is a sequence G1,…,Gn of simple subcubic graphs such that each Gi has at most i+k vertices and for no i<j is Gi homeomorphically embeddable into Gj.

Later, Friedman defined the more general subcubic graphs 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 G1, G2, ... such that each graph Gi has at most i+k vertices (for some integer k) and for no i<j is Gi homeomorphically embeddable into (i.e. is a graph minor of) Gj.

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 SSCG(k) denotes that length for simple subcubic graphs. The function 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-th graph in the sequence contains at most n+3 vertices, and no graph is homeomorphically embeddable within any later graph in the sequence. SSCG⁡(3) is defined to be the longest possible length of such a sequence.

Friedman defined SSCG(k) as the largest integer n satisfying the following:

There is a sequence G1,…,Gn of simple subcubic graphs such that each Gi has at most i+k vertices and for no i<j is Gi homeomorphically embeddable into Gj.

The first few terms of the sequence are

SSCG⁡(0)=2,
SSCG⁡(1)=5,  and
SSCG⁡(2)=3⋅23⋅295−8=3⋅2118842243771396506390315925504−8
≈3.241704229⋅1035775080127201286522908640065
≈103.5775⋅1028.

It has been shown that the next term, SSCG(3), is greater than TREE(3). Friedman showed that 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[a] symbols, and that it cannot be proved to exist in that theory with less than 2↑↑1000 symbols, where ↑↑ denotes tetration. He does this using a similar idea as with a similar statement he proved about TREE(3).

SCG function

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

There is a sequence G1,…,Gn of subcubic graphs such that each Gi has at most i+k vertices and for no i<j is Gi homeomorphically embeddable into Gj.

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

See also