Friedman's SSCG function is a mathematical function defined by Harvey Friedman. It is defined by as the largest integer satisfying the following: There is a sequence of simple subcubic graphs such that each has at most vertices and for no is homeomorphically embeddable into .
Later, Friedman defined the more general subcubic graphs .
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 , , ... such that each graph has at most vertices (for some integer ) and for no is homeomorphically embeddable into (i.e. is a graph minor of) .
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 there is a sequence with maximal length. The function denotes that length for simple subcubic graphs. The function denotes that length for (general) subcubic graphs.
Harvey Friedman defined two functions: SSCG and SCG.
SSCG function
Friedman defined as the largest integer satisfying the following:
There is a sequence of simple subcubic graphs such that each has at most vertices and for no is homeomorphically embeddable into .
The first few terms of the sequence are
and
It has been shown that the next term, , is greater than TREE(3). Friedman showed that is greater than the halting time of any Turing machine that can be proved to halt in Π-CA0 with at most symbols, and that it cannot be proved to exist in that theory with less than symbols, where denotes tetration. He does this using a similar idea as with a similar statement he proved about .
SCG function
Later, Friedman realized there was no good reason for imposing "simple" on subcubic graphs. He relaxes the condition and defines as the largest satisfying:
There is a sequence of subcubic graphs such that each has at most vertices and for no is homeomorphically embeddable into .
The first term of the sequence is , while the next term is bigger than Graham's number. Furthermore, is bigger than .
Adam P. Goucher claims there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It's clear that , but I can also prove ".TREE(3) and impartial games | Complex Projective 4-Space
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 Friedman actually writes this as 2, which denotes an exponential stack of 2's of height 2000 using his notation.
References