Friedman's SSCG function
{{short description|Fast-growing function}}
{{More citations needed|date=January 2025}}
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 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-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 there is a sequence with maximal length. The function SSCG(k)[http://www.cs.nyu.edu/pipermail/fom/2006-April/010305.html [FOM] 274:Subcubic Graph Numbers] denotes that length for simple subcubic graphs. The function SCG(k)[http://www.cs.nyu.edu/pipermail/fom/2006-April/010362.html [FOM] 279:Subcubic Graph Numbers/restated] denotes that length for (general) subcubic graphs.
The SCG sequence begins SCG(0) = 6, but SCG(1) explodes to a value equivalent to fε2*2 in the fast-growing hierarchy.
The SSCG sequence begins slower than SCG, SSCG(0) = 2, SSCG(1) = 5, but then grows rapidly. SSCG(2) = 3 × 2(3 × 295) − 8 ≈ 3.241704 × 10{{val|35775080127201286522908640065}}. Its first and last 20 digits are 32417042291246009846...34057047399148290040. SSCG(2) has in total {{val|35775080127201286522908640066}} digits. SSCG(3) is much larger than both TREE(3) and TREETREE(3)(3) (the TREE function nested TREE(3) times with 3 at the bottom).
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)."[https://cp4space.wordpress.com/2012/12/19/fast-growing-2/comment-page-1/#comment-1036 TREE(3) and impartial games | Complex Projective 4-Space]
The function was proposed and studied by Harvey Friedman.
See also
References
{{reflist}}
{{Large numbers}}
{{DEFAULTSORT:Friedman's SSCG function}}