Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Friedman's SSCG function
open-in-new
<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a simple subcubic graph (SSCG) is a finite simple <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> in which each <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> has a <a href="/facts/Vertex_degree/LnFFpI8v">degree</a> of at most three. Suppose we have a sequence of simple subcubic graphs <i>G</i>1, <i>G</i>2, ... such that each graph <i>G</i><i>i</i> has at most <i>i</i> + <i>k</i> vertices (for some integer <i>k</i>) and for no <i>i</i> < <i>j</i> is <i>G</i><i>i</i> <a href="/facts/Homeomorphism_(graph_theory)/WbFo1mNW">homeomorphically embeddable</a> into (i.e. is a <a href="/facts/Graph_minor/qn5eI22T">graph minor</a> of) <i>G</i><i>j</i>. </p><p>The <a href="/facts/Robertson%E2%80%93Seymour_theorem/J7g4CJ74">Robertson–Seymour theorem</a> proves that subcubic graphs (simple or not) are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. Then, by applying <a href="/facts/K%C5%91nig%27s_lemma/eCU93PN9">Kőnig's lemma</a> on the tree of such sequences under extension, for each value of <i>k</i> there is a sequence with maximal length. The function SSCG(<i>k</i>) denotes that length for simple subcubic graphs. The function SCG(<i>k</i>) denotes that length for (general) subcubic graphs. </p><p>The <i>SCG</i> sequence begins SCG(0) = 6, but SCG(1) explodes to a value equivalent to fε2*2 in the <a href="/facts/Fast-growing_hierarchy/4ctDqlLY">fast-growing hierarchy</a>. </p><p>The <i>SSCG</i> 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 total 35775080127201286522908640066 digits. SSCG(3) is much larger than both <a href="/facts/TREE(3)/3q0G4cbP">TREE(3)</a> and TREE(TREE(3)), that is, you have TREE(3) different unique nodes. </p><p>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(<i>n</i>) ≥ SSCG(<i>n</i>), but I can also prove SSCG(4<i>n</i> + 3) ≥ SCG(<i>n</i>)." </p><p>The function was proposed and studied by <a href="/facts/Harvey_Friedman_(mathematician)/Yq10dMrt">Harvey Friedman</a>. </p>