 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Friedman's SSCG function" – news ·newspapers ·books ·scholar ·JSTOR(January 2025) (Learn how and when to remove this message) |
Inmathematics, asimple subcubic graph (SSCG) is a finite simplegraph in which eachvertex has adegree of at most three. Suppose we have a sequence of simple subcubic graphsG1,G2, ... such that each graphGi has at mosti +k vertices (for some integerk) and for noi <j isGihomeomorphically embeddable into (i.e. is agraph minor of)Gj.
TheRobertson–Seymour theorem proves that subcubic graphs (simple or not) are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. Then, by applyingKőnig's lemma on the tree of such sequences under extension, for each value ofk there is a sequence with maximal length. The function SSCG(k)[1] denotes that length for simple subcubic graphs. The function SCG(k)[2] denotes that length for (general) subcubic graphs.
TheSCG sequence begins SCG(0) = 6, but SCG(1) explodes to a value equivalent to fε2*2 in thefast-growing hierarchy.
TheSSCG sequence begins slower than SCG, SSCG(0) = 2, SSCG(1) = 5, but then grows rapidly. SSCG(2) = 3 × 2(3 × 295) − 8 ≈ 3.241704 × 1035775080127201286522908640065. Its first and last 20 digits are 32417042291246009846...34057047399148290040. SSCG(2) has in total35775080127201286522908640066 digits. SSCG(3) is much larger than bothTREE(3) and TREE(TREE(3)), that is, you have TREE(3) different unique nodes.
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)."[3]
The function was proposed and studied byHarvey Friedman.