Friedman's SSCG function is a mathematical function defined by Harvey Friedman. It is defined by as the largest integer satisfying the following:
Later, Friedman defined the more general subcubic graphs .
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-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 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.
Friedman defined as the largest integer satisfying the following:
The first few terms of the sequence are
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 ÃÂ -CA<sub>0</sub> with at most symbols, where denotes tetration. He does this using a similar idea as with .
He also points out that is completely unnoticeable in comparison to .
Later, Friedman realized there was no good reason for imposing "simple" on subcubic graphs. He relaxes the condition and defines as the largest satisfying:
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 ".