Top Qs
Timeline
Chat
Perspective
Friedman's SSCG function
Fast-growing function From Wikipedia, the free encyclopedia
Remove ads
In mathematics, 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) .
This article needs additional citations for verification. (January 2025) |
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.
Remove ads
SSCG function

Harvey Friedman defined two functions, SSCG and SCG. He defined as the largest integer satisfying the following:[1]
- 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 .[2]
Friedman showed that is greater than the halting time of any Turing machine that can be proved to halt in Π1
1-CA0 with at most [a] symbols, where denotes tetration. He does this using a similar idea as with TREE(3).[1]
He also points out that is completely unnoticeable in comparison to .[1]
Remove ads
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:[3]
- There is a sequence of subcubic graphs such that each has at most vertices and for no is homeomorphically embeddable into .
Most of the results that hold true for also hold true for .
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 ".[4]
Remove ads
See also
- Goodstein's theorem
- Paris–Harrington theorem
- Kanamori–McAloon theorem
- Kruskal's tree theorem, which leads to the similar TREE function
Notes
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads