FANDOM


Where the different values of SCG(n)? And what level of growth in this function? In list of googologisms it is considered as uncomputable number. Is this right? Ikosarakt1 (talk) 11:11, November 9, 2012 (UTC)


Even SCG(0) seems hard to compute. We can start with a graph with 1 vertex, which can contain 1 loop. This means there are no more loops in any of the remaining graphs. The second graph can have 2 vertices, with three edges connecting them. The third graph can have 3 vertices, with two edges connecting every pair. The fourth graph can have 4 vertices a,b,c,d, with ab, bc, and cd connected by two edges each, and the remaining three pairs connected by one edge each. It seems that this can go on for a very long time. So even SCG(0) might be very large.


The growth rate of SCG(n) is at least the level of ψΩ1ω) in the fast-growing hierarchy. One of these days I will write a blog post explaining the fast-growing hierarchy up to these large ordinals. I'm pretty sure that SCG(13) will be greater than meameamealokkapoowa oompa, and Chris Bird comes to the same conclusion in his Bowers' Named Numbers article.

"Uncomputable number" is a rather vague term, but it is certainly true that SCG(n) is a computable function. You can write a program that runs through all possible acceptable sequences of graphs and keeps track of the longest one.Deedlit11 (talk) 17:31, November 16, 2012 (UTC)

Thank you that have explained it to me. I'll put it in the appropriate place. Ikosarakt1 (talk) 09:10, November 17, 2012 (UTC)


Whoops, I messed up the SCG(0) analysis. I'm now quite certain that SCG(0) = 6. The first graph is a single vertex with a loop; this prevents all loops or cycles in future graphs. The second graph is two vertices with a single edge between them. This prevents all edges of any kind in future graphs. So the remaining graphs are all edgeless graphs. So the last four graphs are graphs with 3, 2, 1, and 0 vertices with no edges between them. So SCG(0) = 6, or 5 if the empty graph is not allowed.

SCG(1), on the other hand, is provably very large. We can construct a sequence of graphs (for convenience I will start with G2, so that Gn has n vertices.)

G2 = 2 vertices with three edges between them.

G3 = vertices a, b, and c with two edges between a and b and one edge between b and c.

G4 = two pairs of vertices each with two edges between them.

G5 = a 5-cycle, i.e. the graph of a pentagon.

G6 = a four-cycle (square) plus two vertices with an edge between them.

G7 = a square plus three vertices each with a loop.

G8 = a square plus two looped vertices and two unlooped vertices.

G9 = a square plus two looped vertices and one unlooped vertex.

G10 = a square plus two looped vertices.

G11 = a square plus one looped vertex and six unlooped vertices.

G12 = a square plus one looped vertex and five unlooped vertices.

...

G17 = a square plus one looped vertex.

G18 = a square plus 14 unlooped vertices.

G19 = a square plus 13 unlooped vertices.

...

G32 = a square.


We can then define G33 to be a triangle plus a 30-vertex cubic tree. We can then continue with a triangle plus a very long sequence of cubic forests. Let forest(n) be the length of the longest sequence of cubic forests such that the ith forest has at most n + i vertices. Then we can continue our above sequence with a sequence of length forest(29) consisting of a triangle plus a cycleless cubic forest. We can then continue with a sequence of length forest(forest(29)) consisthing of 2-cycle plus a cyclelss cubic forest. Then we construct a sequence of length forest(forest(forest(29))) consisting for a looped vertex plus a cycleless cubic forest. We finish with a sequence of length forest(forest(forest(forest(29)))) consisting of cycleless cubic forests.'

I believe the growth rate of forest(n) is about epsilon_0 in the fast-growing hierarchy, SCG(1) > forest(forest(forest(forest(29)))) is very large, clearly indeterminable.Deedlit11 (talk) 03:08, November 23, 2012 (UTC)

According to you, SCG(1) is larger than goppatothplex, but it is a mere lower bound... Ikosarakt1 (talk) 12:15, November 26, 2012 (UTC)

I just had an idea of how this sequence can be made a lot longer - if I'm not mistaken non-simple subcubic graphs can have loop on leaf vertex (if they can't, you can stop reading here). Define G'3 as Deedlit's G3 with loop around vertex c. G'4 is same as G3 and G'5 is same as G4. Then G'6 is hexagon graph. G'7 will be pentagon with two vertices with loops and edge between them. G'9 will be just G6 (I haven't made any analysis, so G'8 and G'9 just delete leaf loops, for simplicity). Continuing in same manner as Deedlit we'll at some point reach alone pentagon. Say it happens at G'x. Using cubic trees we can now reach forest^5(x-4). We can also insert stages between triangle plus a cycleless forest and 2-cycle plus a cycleless forest by using 2 vertices with loops around them, and then 2 vertices from which only one has loop. This creates forest^7(x-4) graphs long sequence. And for the end another lengthening - suppose that after using forests with 2-cycles we make forests and 3 looped vertices, then 2 looped vertices, then one. With some optimization we can create sequences reaching forest^(forest(x-4))(x-4) or even ones with function exponent having function exponent! LittlePeng9 (talk) 18:02, February 5, 2013 (UTC)

Yeah, I wasn't trying to maximize the sequence because it was taking too much explaining to do.  I would be interested to see how high you can go! Deedlit11 (talk) 04:55, March 7, 2013 (UTC)

I created whole blog post defining and explaining 3 functions I later used to bound SCG(1) from below. Can you come up with better result? LittlePeng9 (talk) 20:24, March 10, 2013 (UTC)

Rayo's number

How does SCG(13) compare to Rayo's number? FB100Ztalkcontribs 02:52, January 2, 2013 (UTC)

Rayo's function grows as fast as \(f_{\omega_{1}^{CK} \times \omega}(n)\) (I found it at cp4space). Busy beaver function is only \(f_{\omega_{1}^{CK}}(n)\). BB(n) is yet uncomputable, and Ra(n) all the more so. SCG(n), however, is computable, so Rayo's number should be larger. Ikosarakt1 (talk) 16:49, January 19, 2013 (UTC)

Look on this CP4space again. Together with A.P.Goucher we concluded that Rayo's function strength is at level of \(f_{\omega_{\omega}^{CK}}(n)\) (ordinal in there is smallest limit of admissibles, obviously still countable) LittlePeng9 (talk) 16:18, January 28, 2013 (UTC)

Actual strength of SCG function

Deedlit states that strength of SCG function is at least \(\psi_{\Omega_1}(\Omega_\omega)\). I guess he says so, because it is provably strength of Robertson-Seymour theorem. But this theorem is saying about well-quasi-ordering set of all graphs. Subcubic graphs make only tiny fraction of whole. I think strength of SCG function is strictly smaller than this ordinal. What do you think about that?

On the other hand, at the end of Wikipedia article on graph minor theorem there is finite form concerning every possible graph with graph minorship relation. Function based on this finite form has at least \(\psi_{\Omega_1}(\Omega_\omega)\) as corresponding ordinal, and I'm almost sure I can prove that LittlePeng9 (talk) 20:42, February 13, 2013 (UTC)

Actually, I wasn't basing the strength of the SCG function on the Robertson-Seymour theorem, but rather on Friedman's statements in his FOM postings.  In particular, he statest that the fact that finite subcubic graphs are WQO under homeomorphic embeddability is not provable in the theory Pi-1-1-CA_0.  This implies that SCG(n) is not a provably recursive function of Pi-1-1-CA_0, and the proof-theoretic ordinal of pi-1-1-CA_0 is  \(\psi_{\Omega_1}(\Omega_\omega)\).  In fact Friedman states that even the fact that finite planar subcubic graphs (and presumably finite planar simple subcubic graphs) are WQO under homeomorphic emeddability is not provable in Pi-1-1-CA_0, so PSCG(n) and PSSCG(n) won't be provably recursive in Pi-1-1-CA_0.

Now, we may presume that a function is provably recursive in Pi-1-1-CA_0 if and only if it is elementary recursive in some function \(F_{\alpha}\) for \( \alpha < \psi_{\Omega_1}(\Omega_\omega)\).  So a function not provably recursive in Pi-1-1-CA_0 will not be elementary recursive in any \(F_{\alpha}\) for \( \alpha < \psi_{\Omega_1}(\Omega_\omega)\).  However, this does not mean that the function will dominate all \(F_{\alpha}\) for \( \alpha < \psi_{\Omega_1}(\Omega_\omega)\); for example, it could alternate between large values and 0. (Or, for an example of an increasing function, it could alternate between periods of growing very fast with growing very slowly, with the periods getting longer and longer.)  So perhaps we cannot state with certainty that the previous functions grow at a certain rate.  However, it seems highly unlikely to me that any natural function will have such strange behavior;  so I am almost certain that PSSCG(n) et al grow at \(F_{\psi_{\Omega_1}(\Omega_\omega)} \) or faster. Also, Friedman states as a theorem that SCG(13) is larger than the halting time of any Turing machine starting from the blank tape that can be proven to halt in at most \(2 \uparrow \uparrow 2000 \) symbols, based on the fact that \(SCG(13) \ge PSCG(2 \uparrow \uparrow 2000) \).  So somehow he knows that \(PSCG(n) > f(n) \), where f(n) is the halting time of the longest running Turing machine starting from the blank tape that can be proven to halt in at most n symbols. I think it is clear that the latter grows at the rate of \(\psi_{\Omega_1}(\Omega_\omega)\) or higher. How Friedman knows this, I don't know, but I will trust him. Deedlit11 (talk) 04:50, March 7, 2013 (UTC)

I wonder how the values of SCG(n) compare to numbers derived from the Buchholz hydra game? --Ixfd64 (talk) 18:35, March 7, 2013 (UTC)

Good question!  If we let BHydra(n) be the time it takes to slay a Buchholz hydra consisting of an (n+2)-path labelled with n n's (the first two vertices are required to be labelled with + and 0), then both SCG(n) and BHydra(n) are about at the level of \(\psi_{\Omega_1}(\Omega_\omega)\).  BHydra(n) will in fact be roughly equivalent to  \(F_{\psi_{\Omega_1}(\Omega_\omega)} \) , as the structure of Buchholz Hydras with finite ordinal labels mimic ordinal notations up to \(\psi_{\Omega_1}(\Omega_\omega)\), and the act of slaying the hydras mimics taking fundamental sequences.  On the other hand, from Friedman's work we can infer that \(PSCG(n) \ge F_{\psi_{\Omega_1}(\Omega_\omega)} \), and SCG(n) grows faster than PSCG(n) (for example \(SCG(13) > PSCG(2\uparrow\uparrow 2000) \).  So I believe SCG(n) outpaces BHydra(n).

However, if we label Buccholz hydras with infinite ordinals, than I bet that the numbers derived from Buchholz hydras will grow faster. Deedlit11 (talk) 00:33, March 8, 2013 (UTC)

From Buchholz's work we know that for every hydra we can prove its termination in \(\Pi^1_1-CA_0\), but we can't do this uniformly (otherwise, Theorem III from this paper could be disproven by induction on number of labels). So we know that function F(n) related to (n+2)-path labelled with n ω's is unprovably recursive in \(\Pi^1_1-CA_0\), so it almost certainly outbounds \(F_{\psi_{\Omega_1}(\Omega_\omega)} \) LittlePeng9 (talk) 10:25, March 9, 2013 (UTC)

Blog entry about SCG function

Someone wrote an interesting blog entry on the SCG function here. I suspect it's someone from this wiki. --Ixfd64 (talk) 20:09, June 26, 2013 (UTC)

Wondering who is the author? Konkhra (talk) 21:27, June 26, 2013 (UTC).
When the author talks about increasing the valence limit of SCG, it would be easier to go to Minor(n) instead. We can define \(Minor_f\) as the longest sequence of graphs \(G_n\) such that the number of vertices of \(G_n\) is no more than \(f(n)\) and for no i < j do we have \(G_i\) a minor of \(G_j\). Note that it is important that we go from topological minor to regular minor for valence greater than 3, otherwise we do not necessarily get a finite sequence.
The array extension at the end just adds \(\omega^2\) to the ordinal, so it's pretty unimportant. Deedlit11 (talk) 23:48, June 26, 2013 (UTC)
I'm working on the values hereWythagoras (talk) 09:51, August 8, 2013 (UTC)

I think this extension can add \(\omega^\omega\) to the order type, as it works similar to Bowers' variant of array notation. Ikosarakt1 (talk ^ contribs) 19:57, June 29, 2013 (UTC)

But it works more like Conway chained arrow notation, since the recursion rule decrements the highest entry rather than the lowest nonzero entry. Deedlit11 (talk) 00:17, June 30, 2013 (UTC)

2^[1000]

I have heard about a^[b] as a notation for \(a \uparrow\uparrow b\). Is it true? Ikosarakt1 (talk) 17:38, March 1, 2013 (UTC)

Yes, really. Harvey Friedman wrote: "Here 2 ^ [1000] is an exponential stack of 2's of height 1000"  Here's the link: [1]Konkhra (talk) 09:07, March 2, 2013 (UTC)

Informal explanation?

Is there a way to explain SCG less esoterically, in a way similar to TREE sequence#Explanation? It'd be nice if we could find a way to encode subcubic graphs in strings so that the concept of a graph minor is really clear. FB100Ztalkcontribs 19:12, March 17, 2013 (UTC)

I don't think so - I think best we can do is explain what graph and topological minors are, and how it connects to homeomorphic embeddability. LittlePeng9 (talk) 11:00, March 18, 2013 (UTC)

I don't know of any natural interpretation of graphs as strings, other than to list out the adjacency matrix, and I don't it will be easy to define topological minors using that.Deedlit11 (talk) 12:49, March 18, 2013 (UTC)

After all these months, I have an idea: incidence matrices. Graph minors are formed by deleting rows or columns, or by adding two rows if they share a 1 and deleting one column containing a 2. (Note that we use a 2 to indicate loops.) FB100Ztalkcontribs 21:46, November 11, 2013 (UTC)

extending the function?

Is it possible to generalize or extend the SCG function to make it more powerful? Just curious. --Ixfd64 (talk) 05:17, April 17, 2013 (UTC)

There is certainly no obvious way to escape corresponding ordinal of SCG function. Giving more freedom for size of graphs won't increase asymptotic growth, and throwing subcubicity away may break totality of function (infinite sequences). We can allow general simple graphs if we consider graph (instead of topological) minor relation, which is WQO over set of all graphs. But it still doesn't have larger ordinal. LittlePeng9 (talk) 05:31, April 17, 2013 (UTC)

I'll use Minor(n) for Robertson-Seymour function. While SCG(n) and Minor(n) functions have the same minimum ordinal, neither has a good maximum ordinal (except perhaps the proof-theoretic ordinal of a much stronger theory), and it's quite possible that the ordinal for Minor(n) is larger than the ordinal for SCG(n). Deedlit11 (talk) 06:49, April 17, 2013 (UTC)

What is the function Minor(n)? Where I can read about it? Konkhra (talk) 12:51, May 24, 2013 (UTC)
Wonder how large Minor(1) or Minor(2)? Konkhra (talk) 03:14, May 25, 2013 (UTC)
Minor(n) is length of longest sequence of simple graphs G such that Gi has at most i+n vertices and no Gi is graph minor of Gj for j>i. I'm pretty sure Minor(1)=4 and Minor(n)>=SSCG(n), I also guess Minor(2)=SSCG(2). LittlePeng9 (talk) 08:28, May 25, 2013 (UTC)

growth rate of SCG(k) upper-bounded by TFB ordinal?

This paper suggests that the strength of the graph minor theorem is limited by \(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\). I'm not sure of the difference between \(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\) and \(\Pi_1^1-\text{CA}+\text{BI}\), but does this mean the ordinal of the SCG function is limited by the Takeuti-Feferman-Buchholz ordinal? --Ixfd64 (talk) 16:50, June 27, 2013 (UTC)

As far as I know, subscript in \(\text{CA}_0\) is often dropped, so both mentioned systems are equal. Friedman's result gives lower bound corresponding to system \(\Pi_1^1-CA_0\), which excludes so called bar induction. Paper you linked doesn't prove what you said; that was already proven by Robertson and Seymour. I think that result shows that ordinal of SCG function is at most TFB ordinal (with tiny chance for equality). LittlePeng9 (talk) 20:54, June 27, 2013 (UTC)

The zero subscript definitely makes a difference, although I forget exactly what it meant. (It affects the scope of the comprehension axiom.) Since \(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\) has the TFB ordinal as its proof-theoretic ordinal, this result shows that SCG(n) and Minor(n) indeed are at most the TFB ordinal in the FGH. Deedlit11 (talk) 03:16, June 28, 2013 (UTC)
Indeed, zero subscript means restricted induction. In this case, comprehension, so also induction, is limited to \(\Pi^1_1\) formulas. But this system without inductive restriction is equivalent to full second order arithmetic. What I meant is that subscript is often ommited in this particular system, though I may be completely wrong. LittlePeng9 (talk) 06:08, June 28, 2013 (UTC)
I don't believe systems with the full second order induction scheme are equivalent to second order arithmetic; for example, I have read that the proof theoretic ordinal of ACA is \(\epsilon_{\epsilon_0}\), as opposed to ACA_0 which has proof theoretic ordinal \(\epsilon_0\). So ACA is strictly between ACA_0 and second order arithmetic. I believe the same thing is true of \(\Pi_1^1\)-\(\text{CA}\) versus \(\Pi_1^1\)-\(\text{CA}_0\) The paper that Ixfd64 linked suggests they are different as well. Deedlit11 (talk) 06:31, June 28, 2013 (UTC)
It might be, I just said what I thought is true. Everyone is allowed to be mistaken. Do you maybe know where is this result about ACA mentioned? LittlePeng9 (talk) 16:28, June 28, 2013 (UTC)
Certainly everyone is allowed to be mistaken, no judgment here! Not sure where I read it, but a quick Google search yields the following: http://mathforum.org/kb/message.jspa?messageID=5973538 Deedlit11 (talk) 16:56, June 28, 2013 (UTC)

I just found a presentation from the University of Wisconsin that says the order type of the graph minor theorem is greater than the TFB ordinal. However, all the other papers and discussions I've read say otherwise. Would it be safe to assume that the UW paper is incorrect? --Ixfd64 (talk) 00:32, July 2, 2013 (UTC)

I believe he is mistaken, because he says that the proof theoretic ordinal of \(\Pi_1^1\)-\(\text{CA}_0\) is \(\psi_0 (\varepsilon_{\Omega_{\omega}+1})\), whereas I have read from multiple sources that the proof theoretic ordinal is \(\Pi_1^1\)-\(\text{CA}_0\) is \(\psi_0 (\Omega_{\omega})\). Nice slides though, please keep sharing your finds. Deedlit11 (talk) 04:18, July 2, 2013 (UTC)

It's pretty funny how two papers you linked are stating contrary results about how RS theorem relates to TFB ordinal. This slideshow is also nicely introducing wqo's. This is I think where I first heard of them. LittlePeng9 (talk) 08:45, July 2, 2013 (UTC)

Values of SSCG

I found:

SSCG(0) = 2

SSCG(1) = 5, using the following sequence:  •–•  •••  ••  • and the empty graph

Also, is an empty graph allowed? Wythagoras (talk) 09:16, June 28, 2013 (UTC)

It's not clear what Friedman intended, but I have been allowing it. (The article currently says SCG(0) = 6 which assumes the empty graph is allowed.) Of course, it just makes the numbers one greater.
You may be interested in the following article http://cp4space.wordpress.com/2013/01/13/graph-minors/, which among other things discusses the values of SSCG(2) and SSCG(3). Note that SSCG(3) is _extremely_ large! Deedlit11 (talk) 09:34, June 28, 2013 (UTC)
Can we find values for PSCG(n) and PSSCG(n)? And for SSCG(3), what does very large n mean? Can it be larger than TREE(3) itself?  or even TREE^(TREE(3))(3)? Wythagoras (talk) 10:42, June 28, 2013 (UTC)
Regarding PSCG(n) and PSSCG(n), note that a graph is planar if and only if it does not contain a subdivision of K_5 or K_3,3 as a subgraph. (This is Kurotowski's Theorem, which is usually used for simple graphs but one can see that it applies to multigraphs as well.) Since K_5 is a degree 4 graph, a subcubic graph will never contain a subdivision of K_5, so a subcubic graph is planar if and only if it doesn't contain a subdivision of K_3,3, which has 6 vertices. So PSSCG(n) = SSCG(n) for n < 5. However PSCG(n) < SCG(n) and PSSCG(n) < SSCG(n) for n >= 6; it is a reasonable conjecture that SSCG(5) = PSSCG(6). Deedlit11 (talk) 14:59, June 28, 2013 (UTC)
How we could know that a K_3,3 cannot appear on the expansion of SCG(5)? The answer will help proving that PSCG(n) = SCG(n) for n < 6. -- I want more clouds! 13:39, June 30, 2013 (UTC)
We can check by cases that every 5-vertex subcubic graph is minor of K3,3. We can check trees, graphs with 3-cycle but not 4-cycle, with 4-cycle but not 5-cycle and with 5-cycle. First two are easy, latter two may have fused cycles, so may be a little problem, but it isn't that hard. LittlePeng9 (talk) 15:09, June 30, 2013 (UTC)
No, wait, it works for simple graphs only! If we take a triangle with one edge with a loop added, then triangle with single edge added and separate loop, next graph can be K3,3! Also, it doesn't work for SSCG(5), because then K3,3 can be first graph. LittlePeng9 (talk) 15:30, June 30, 2013 (UTC)
You're both right; I corrected the post.  So, by LittlePeng9's example, PSCG(3) < SCG(3). Obviously PSCG(0) = SCG(0). What about PSCG(1) and PSCG(2)?  Similar questions for PSSCG(n) versus SSCG(n):  Clearly PSSCG(n) = SSCG(n) for n < 4, but what about PSSCG(4)?  Deedlit11 (talk) 17:32, June 30, 2013 (UTC)
About PSCG(2) we have following sequence: path of length 2 (i.e. with 2 edges) and loops on both ends. Then K1,3 (called claw or star) with loop on one vertex. Now path of length 5 with loop on one end. K3,3 is now valid graph, butI doubt it can lead to very long sequence. I think PSCG(1)=SCG(1), unless we can find graphs on 3, 4 and 5 vertices, each with exactly one cycle (loop or double edge, to be exact), none of which is minor of other or K3,3. I also gave reason why PSSCG(4)=SSCG(4) (it must start with 5-vertex graph whichis minor of K3,3). LittlePeng9 (talk) 17:55, June 30, 2013 (UTC)
Hmmm, now that I think about it, we don't know that PSCG(3) < SCG(3) unless we know that the starting sequence for SCG(3) is optimal, which could be very hard to prove. I've found a sequence for SCG(1) that leads to K_3,3: start with an edge with loops at both ends. Next is an edge with a loop at one end, plus a loop. Next is four loops, followed by three loops, followed by K_3,3. But we don't know that this leads to a longer sequence than PSCG(1) unless we can prove that the longest sequence for PSCG(1) starts the same way. I've made a ton of mistakes here! Deedlit11 (talk) 18:07, June 30, 2013 (UTC)
I also just found nonplanar sequence for SCG(1). I wanted to ask, is your bound SSCG(7)>PSSCG_PSSCG(n)(n) about SSCG(6) or SSCG(7)? I tried to do it for SSCG(6), but I couldn't do much with K3,3 with one added vertex. LittlePeng9 (talk) 18:22, June 30, 2013 (UTC)
It's about SSCG(7). I too couldn't do much with just one added vertex, but with two added vertices you can go on for a LONG time. Deedlit11 (talk) 18:25, June 30, 2013 (UTC)
SSCG(3) is indeed larger than TREE^(TREE(3))(3). If we define TREE_2 = TREE^n (n), TREE_3 = (TREE_2)^n (n), and TREE_4 = (TREE_3)^n (n), then SSCG(3) is at least TREE_4 (n) for n large (I haven't worked out how large, but clearly greater than Graham's number for example.). Deedlit11 (talk) 15:05, June 28, 2013 (UTC)
Thanks. And SSCG(4)? is it bigger then TREE_SSCG(3)(SSCG(3)) for example? Wythagoras (talk) 08:04, June 29, 2013 (UTC)
I must admit I haven't thought much about SSCG(4). It might be bigger than TREE_SSCG(3) (SSCG(3)), but it would be hard to prove it, as we would need to employ a sequence of SSCG(3) graphs somewhere, and that would leave just one extra vertex to use, which doesn't seem like enough.
I can prove that SSCG(7) > PSSCG_PSSCG(n)(n) for a large n, so SSCG grows much faster than PSSCG, and similarly SCG grows much faster than PSCG. Deedlit11 (talk) 19:20, June 29, 2013 (UTC)

Also, I believe I can prove that SSCG(3n+4) >= 3 SCG(n), improving Goucher's inequality. We can convert any multigraph into a simple graph by the following procedure: Whenever we have multiple edges between two vertices, we subdivide all but one of the edges into two edges. Whenever we have a loop, we subdivide it into three edges. Each vertex either has a loop, a double or triple edge, or neither. In any case we need to add at most two vertices to the adjoining edges. So this conversion at most triples the number of edges.

So, let's say we have a sequence of SCG(n) multigraphs with at most n+1, n+2, ... n+SCG(n) vertices. The conversion converts this to a sequence of simple graphs with at most 3n+3, 3n+6, ... 3n + 3 SCG(n) vertices. Since each subsequent graph in the sequence has the max number of vertices increasing by 3, we replace each graph by a sequence of three graphs, by replacing G by G + 2 vertices, G + 1 vertex, G. This leads to a sequence with 3n+5, 3n+4, 3n+3, 3n+8, 3n+7, 3n+6,... vertices. This is a valid sequence for SSCG(3n+4) of length 3SCG(n), so SSCG(3n+4) >= 3SCG(n). Deedlit11 (talk) 16:12, June 28, 2013 (UTC)

I found that SSCG(6)>=PSSCG(12)+6 and SCG(6)>=PSCG(7+PSCG(1))+PSCG(1)+1. I believe first equality holds, but I doubt about second one. As we are not even sure if SCG(3)=PSCG(3) (I think we can prove it for 1 and 2 by checking all sequences leading to K3,3) sequence I used may be suboptimal. LittlePeng9 (talk) 15:22, July 1, 2013 (UTC)

Yes, I agree with both inequalities. Although we might as well say SCG(6)>=PSCG(7+SCG(1))+SCG(1)+1 until we can actually prove that SCG(1) = PSCG(1). Deedlit11 (talk) 15:38, July 1, 2013 (UTC)


Might it be time to update the values and bounds section with the two results agreed above: SSCG(3) > TREE^(TREE(3))(3) and SSCG(3n+4) >= 3 * SCG(n)?  That would make it easier to provide a reference to a Wikipedia entry about SSCG .  It would also allow for greater specificity in the value of SSCG(3), which used a colorful, but imprecise, description from Goucher. Michael Tiemann (talk) 00:42, October 3, 2015 (UTC)

The derivation of SSCG(3n+4) >= 3 SCG(n) contains an error. Something like Goucher's bound of SSCG(4n+3) >= SCG(n) seems like it should work, but proof seems complicated. I don't know whether Goucher wrote down an explicit proof, or simply came up with a correspondence that appeared to work and didn't bother with the details. Perhaps it is better not to put it into Wikipedia. Deedlit11 (talk) 10:14, October 3, 2015 (UTC)
The lower bound TREE^(TREE(3))(3) could certainly be used as a lower bound for SSCG(3), but much stronger bounds are provable. Of course the stronger bounds would take longer to describe. The reason I'm leery of saying that TREE^(TREE(3))(3) is a lower bound in a Wikipedia entry is that A^(A(187196))(1) was mentioned as a lower bound for TREE(3); even though it was specifically stated that this was a _weak_ lower bound, still this wound up with a lot of people saying that the value of TREE(3) was actually A^(A(187196))(1), when in fact it is enormously larger. So there is a danger in giving weak lower bounds. Deedlit11 (talk) 04:18, October 3, 2015 (UTC)

Another variant

Consider SSCG function with following restriction - every graph must consist of one connected component (or is empty graph). I checked that CSSCG(0)=2, CSSCG(1)=4, CSSCG(2)=8. After many tries I was able to prove CSSCG(3)>TREE(3), and heurestically that CSSCG(3)>TREE(5), though it'd takeme a while to verify. The key was Goucher's reduction, which thankfully results in connected graphs. I noticed CSCG(1) won't be really big number, though it may reach epsilon_0. LittlePeng9 (talk) 10:39, July 2, 2013 (UTC)

Grows CSSCG faster then PSSCG? Wythagoras (talk) 13:22, July 2, 2013 (UTC)

I believe connected variant grows strictly slower than planar one. This is only intuition, though. LittlePeng9 (talk) 14:15, July 2, 2013 (UTC)

I get that CSSCG(1) = 3; edge, point, empty graph. I agree that CSSCG(2) = 8. As for CSSCG(3), we can improve Goucher's reduction to TREE(n) a little bit: instead of having the label connect to a triangle, we can have the label connect directly to the main cycle. We can still distinguish the label since it will be an acyclic tree, whereas the children nodes will always have a cycle. This will allow the sequence to have fused cycles with triangles in addition to the fused cycles with squares that Goucher has, before going to the TREE sequence. Anyway, I'd be interested to hear you analysis for CSSCG(3) > TREE(3) and CSSCG(3) > TREE(5) heuristically. Deedlit11 (talk) 18:46, July 2, 2013 (UTC)
Yes, CSSCG(1)=3, for some reason I counted loop graph. But your improvement doesn't work - if a label is connected just as child nodes are (which is a case in your method) then tree can interfere with ancestors of node. Simplest example: suppose we have one node tree with label represented by path of length, say, 4. In the next tree root very likely has a child, but because label was connected just as child is, the second node can't have 4-path as a minor, so it restricts more than TREE function does. I'll post my analysis tomorrow, as soon as I find my notes, but I think I actually failed with TREE(5) bound. LittlePeng9 (talk) 21:10, July 2, 2013 (UTC)
I found my notes (A4 sheet of drawing paper filled with graphs of all kinds) and here is sequence of graphs I found:
G4: K4
G5: K2,3
G6: square with two triangles fused
G7: square and pentagon fused. Let R denote two fused squares, with long and short edges defined intuitively.
G8: R with single points attached two corners on longer edge
G9: R with 1-path attached to one vertex and single point attached to opposite vertex
G10: same as above, but with 1-path reduced to point
Let Ra,b denote R with a vertices added to one vertex, and b vertices added to adjacent one. Then G11-24 are: R5,0 R4,2 R4,1 R4,0 R3,3 R3,2 R3,1 R3,0 R2,2 R2,1 R2,0 R1,1 R1,0 R. While writing this I noticed I can use trees too, so there are big hopes for much more than TREE(5)!
Now with G25 we start TREE simulation with tree with counter 10 and single node with any 4-vertex label. G35 is same with counter of length 0, and then we continue. We have two 3-vertex trees which we can use as labels, but it's enough for TREE(3), as we use first label only once. So CSSCG(3)>TREE(3), Q.E.D. LittlePeng9 (talk) 08:40, July 3, 2013 (UTC)
This number is bigger than I'd ever expect! Major observation is that we can attach to R not only trees, but any graph not containing earlier minors. For example, G11 can have square fused with triangle attached to R. Without slightest problems I could get to around \(2\uparrow^{2\uparrow^{...}20}20\) with a lot of levels. Another thing is that we can have cycle fused to triangle such that both cycles are connected to other cycles (in TREE reduction it appears only at root, with fused triangles). Other than that, we can extend Goucher's reduction by adding more counters, which will allow adding levels of recursion to TREE, so CSSCG(3)>>TREE_n(n) for surprisingly large n. LittlePeng9 (talk) 14:33, July 3, 2013 (UTC)
If it is true, you have even improved the bound for SSCG(3). Good job! Wythagoras (talk) 14:47, July 3, 2013 (UTC)
Improvement of Goucher's method is something I figured out much earlier, and I'm pretty certain about its validity. The interesting thing is that SSCG function blows so suddenly - 2, 5, 2^2^95, >>TREE_TREE(n) TREE(n). LittlePeng9 (talk) 15:14, July 3, 2013 (UTC)

I just found _incredible_ bound for CSSCG(8) using planar variant. Let P(n) denote PCSSCG(n) (yes, planar connected simple subcubic graph number). Then CSSCG(8)>P_P_P_...(7) (7) (7), where the number of nestings is P_P_P_...(7) (7) (7), where the number of nestings is P_P_P_...(7) (7) (7), where the number of nestings is... with this repeated P_P_P_...(7) (7) (7), where the number of nestings is... with this repeated at least 4 times and with P(7) at the end. And I thought CSSCG(3) is big! My brain hurts. AND as an interesting note, CSSCG(8)<SSCG(8)<SCG(8)<SCG(13). LittlePeng9 (talk) 10:07, July 4, 2013 (UTC)

But how much PCSSCG(7)? Konkhra (talk) 11:05, July 4, 2013 (UTC)
Little Peng, we can use BEAF (namely BEAF, not BEAN) to express your result more compactly. Take {a,b (S) 2} = P^b(a) and then your bound will be much less than, say, {7,7,7,7 (S) 2}. I think it is around {7,{7,4,1,2},1,2 (S) 2}. Ikosarakt1 (talk ^ contribs) 15:15, July 4, 2013 (UTC)

Let T(n) denote longest sequence of rooted binary trees such that no former one is embeddable into latter one. \(T(n)\approx f_{\varepsilon_0}(n)\). Let \(F_a(n)=T^{T^{...^{T(n)}...}(3)}(3)\) with a T's in stack. Then \(CSCG(1)>F_2^4(F_3^4(F_2^6(2^12)))\). LittlePeng9 (talk) 07:24, August 6, 2013 (UTC)

Can we prove something like BB(30,2)>CSCG(1) or is it too hard?Konkhra (talk) 02:17, October 8, 2015 (UTC)

New variants: for every SCG-type function we add outerplanar variant. Note that Goucher's reduction of TREE into SSCG will work for OCSSCG(5) (denote this function as O(n)). Right now I'm working on bound for CSSCG(4) in terms of O.

Now I'm using following method of finding bounds: given graph Gn I look for length of longest sequence starting with Gn in terms of O. My result is: if \(O(n)\approx f_\alpha(n)\) then mentioned function for a square with two K2,3s connected to opposite vertices is about \(f_{\alpha^\omega}(n)\). LittlePeng9 (talk) 14:24, August 9, 2013 (UTC)

I forgot to mention that above result is heurestic rather than strictly proven. I'm fairly certain about \(\alpha^\omega\) mentioned above, and I got \(\alpha^{\alpha^\omega}\) for K2,3s connected to opposite vertices of hexagon. I conjecture that with polygons and two K2,3s we can get up to \(\alpha^{\alpha^{\alpha^{...}}\). I may write a blog post about that later. LittlePeng9 (talk) 08:34, August 10, 2013 (UTC)

SCG(n) > SSCG(2n+1)?

I think I've discovered that SCG(n) > SSCG(2n+1)+n. Start with a string of (n+1) points with a loop. Call a graph that is allowed to have n vertices Gn. Use for SCG(n) > SSCG(n+1)+n the following sequence:

G(n+1): a string of (n+1) vertices connected with n edges and a loop at the end.

G(n+2): a string of n vertices connected with (n-1) edges and a loop at the end.

G(2n+1): 1 vertex with a loop.

G(2n+2): The first graph of the sequence of SSCG(2n+1)

G(2n+1+SSCG(2n+1)): the empty graph.

So SCG(n) > SSCG(2n+1)+n

Wythagoras (talk) 15:44, August 6, 2013 (UTC)

Loop is a minor of every graph having a cycle. So having it as G(2n+1) forces you to use only trees later. LittlePeng9 (talk) 16:21, August 6, 2013 (UTC)

I may misunderstand something, but I think what you are saying is not correct.

For example in the sequence op SCG(0): •() •-• 3• 2• 1• is •() allowed.

The loop-graphs are in the sequence before the non-loop-graphs. You're not allowed to add a loop to make a graph a minor of a graph before it, are you? Wythagoras (talk) 17:03, August 6, 2013 (UTC)

Latter graphs in that sequences have no cycles so loop isn't minor of it. Loop is an edge connecting vertex to itself, so adding it is allowed. LittlePeng9 (talk) 17:18, August 6, 2013 (UTC)

But why isn't •-• graph minor of •() in SCG(0)? Wythagoras (talk) 18:20, August 6, 2013 (UTC)

A graph G is a minor of H if H can be reduced to G by contracting edges (i.e. shrinking edges to a point) and/or removing edges or vertices. Observe that contracting the edge in •() results in •; there's no way to get •-•. That's not why the sequence for SCG(0) is okay though; the property is that earlier graphs cannot be minors of later graphs, so •() cannot be a minor of •-•, which it isn't. Again, if we contract the edge in •-•, we get •, which is not •().

There is also the notion of topological minor; G is a topological minor of H if we can change G into a subgraph of H by adding vertices to edges. (i.e. replacing edges with paths) For subcubic graphs, these two notions of minors turn out to be the same, so we can use either one in the definition of SCG et al. Deedlit11 (talk) 18:06, August 6, 2013 (UTC)

But how about my bound? Wythagoras (talk) 18:20, August 6, 2013 (UTC)

Doesn't work; by adding n-1 vertices to the loop we get an n-cycle, so a loop is the topological minor of any graph with a cycle. So you are left with just forests, as LittlePeng9 said. Deedlit11 (talk) 18:32, August 6, 2013 (UTC)

Okay. But now I do the same thing, but I use CSSCG(n) without the •-•-•-•-...-•-•-•-• string at the end. In CSSCG(n) doubles •-•-•-•-...-•-•-•-• the value, so remove it won't be a large change. 2*SCG(1) > CSSCG(3) >> TREE(3)? Wythagoras (talk) 06:17, August 7, 2013 (UTC)

I don't get it. Two best choices for G2 in SCG(1) sequence are triple edge or stick with two loops. In either case we already know we can't use Goucher's TREE reduction. LittlePeng9 (talk) 06:41, August 7, 2013 (UTC)

SCG(1)

G2: •-•+loop

G3: •+loop

G4: first graph of CSSCG(3)

...

I use only the forest part of CSSCG(3)

Wythagoras (talk) 08:23, August 7, 2013 (UTC)

Using only trees best possible choice is

G4: claw graph

G5: path with 5 vertices

G6: path with 4 vertices...

G10: empty graph

Even if you use disconnected forests, best you can do is SSCG(2)+1 with this method. LittlePeng9 (talk) 10:43, August 7, 2013 (UTC)

The thing

Umm what is Π^1_1-CA_0 and what does it mean? King(2 [2] 18){0} (talk) 13:46, February 22, 2014 (UTC)

It's a subsystem of second-order arithmetic with proof-theoretic ordinal \(\psi_0(\Omega_{\omega})\). -- ☁ I want more clouds! ⛅ 13:15, February 22, 2014 (UTC)
Thanks. Looks interesting hmmmmmm.... King(2 [2] 18){0} (talk) 13:46, February 22, 2014 (UTC)
oh wow really King2218 (talk) 05:44, July 16, 2015 (UTC)

SCG(0)

Has SCG(0) = 6 been proven? -- vel! 01:26, July 16, 2015 (UTC)

Yes, this is something you can prove by yourself in ~5 minutes, try it. LittlePeng9 (talk) 05:33, July 16, 2015 (UTC)
I don't see any longer sequence for this so yes King2218 (talk) 05:44, July 16, 2015 (UTC)

\(SSCG(4n+3) \geq SCG(n)\)

Does anyone know a proof of this bound or a place where this can be found? Goucher only mentions the result without a proof. LittlePeng9 (talk) 14:59, October 2, 2015 (UTC)

well we could ask Goucher himself I guess Fluoroantimonic Acid (talk) 15:04, October 2, 2015 (UTC)
Here's a proof of a better bound. (Note: this proof is erroneous, look at the proof below instead.)
First, we define a mapping \(T\) from subcubic graphs to simple subcubic graphs. Given a subcubic graph \(G\), we define \(T(G)\) as follows: for each loop in \(G\), put two vertices along the loop. For each nonloop edge, put one vertex on it. The final graph is \(T(G)\), which is clearly a simple subcubic graph.
Next, define a mapping \(S\) on subcubic graphs as follows: let the vertices of \(S(G)\) be the vertices of \(G\) of degree 1, or degree 3 or higher. The vertices of degree 2 of \(G\) can simply be removed one at a time, and the two edges connected to the vertex can be merged into one edge. This defines the graph \(S(G)\). Now, since \(T(G)\) was created from \(G\) entirely by adding vertices along edges of \(G\), we clearly have \(S(T(G)) = S(G)\) for all subcubic graphs \(G\).
For our first lemma, we will show that if \(T(G_1)\) is a topological minor of \(T(G_2)\), then \(G_1\) is a topological minor of \(G_2\). First, we show that \(S(G_1) = S(T(G_1))\) is a topological minor of \(S(G_2) = S(T(G_2))\). Now \(T(G_1)\) is a subdivision of \(S(G_1)\), and \(T(G_2)\) contains a subdivision of \(T(G_1)\), and a subdivision of a subdivision is a subdivision. So \(T(G_2)\) contains a subdivision of \(S(G_1)\), i.e. \(S(G_1)\) is a topological minor of \(T(G_2)\). Call \(H\) the subdivision of \(S(G_1)\) contained in \(T(G_2)\). Note that a subdivision simply adds vertices of degree 2 to edges, and the mapping \(S\) removes all such vertices, so we must have \(S(G_1) = S(H)\). But clearly \(S\) respects the subgraph relation, so \(S(H)\) is a subgraph of \(S(T(G_2)) = S(G_2)\). So \(S(G_1)\) is a subgraph of \(S(G_2)\). We now address whether \(G_1\) is a topological minor of \(G_2\). \(G_1\) is a subdivision of \(S(G_1)\), and \(G_2\) is a subdivision of \(S(G_2)\). The subgraph inclusion of \(S(G_1)\) into \(S(G_2)\) corresponds to a mapping from \(G_1\) to \(G_2\), which maps the vertices of degree other than 2 of \(G_1\) to vertices of degree other than 2 of \(G_2\), and disjoint paths of edges of \(G_1\) go to disjoint paths of edges of \(G_2\). this will be a subdivision inclusion, provided that no disjoint path of edges of \(G_1\) corresponds to a shorter path of edges of \(G_2\). To prove this, we observe that the subgraph inclusion from \(S(G_1)\) into \(S(G_2)\) was induced by a subgraph inclusion of \(T(G_1)\) into a subdivision of \(T(G_2)\). So there we do get that each disjoint path of edges of \(T(G_1)\) has length less than or equal to the corresponding path of edges of \(T(G_2)\). Now, a loop in a graph \(G\) becomes a path of length 3 in \(T(G)\), and a nonloop path of length \(i\) in \(G\) becomes a path of \(T(G)\). Therefore a path of length \(i\) in \(T(G)\) must come from a path of length \(\lfloor{i/2}\rfloor\) in \(G\). So since each disjoint path of edges of \(T(G_1)\) has length less than or equal to the corresponding path of edges of \(T(G_2)\), we must have that each disjoint path of edges of \(G_1\) has length less than or equal to the corresponding path of edges of \(G_2\), and so \(G_1\) is a topological minor of \(G_2\), and our lemma is proved.
For our second lemma, define \(U(G)\) to be the same as \(T(G)\) except that we replace each isolated vertex of \(G\) with a pair of vertices with an edge connecting them. Note that each connected component of \(G\) that isn't an isolated vertex gets mapped via \(T\) to a connected component of at least 3 vertices. So \(T(G)\) is a bunch of connected components all with at least 3 vertices plus \(n\) isolated vertices, and \(U(G)\) is the same bunch of connected components all with at least 3 vertices plus \(n\) pairs of vertices connected with an edge. So if we have \(U(G_1)\) as a topological minor of \(U(G_2)\), then we must have the connected components of \(U(G_1)\) of order at least 3 mapping to the connected components of \(U(G_2)\) of order at least 3, and the remaining connected components of \(U(G_1)\), which are all isolated edges, must map into the remainder of \(U(G_2)\); some will map to into connected components of \(U(G_2)\) of order at least 3, and some will map 1-1 to isolated edges of \(U(G_2)\). From this we can clearly define a topological mapping from \(T(G_1)\) into \(T(G_2)\), by using the same mapping on the connected components of order at least 3, and pulling back the mappings of isolated edges of \(U(G_1)\) to isolated vertices of \(T(G_1)\). Each isolated edge of \(U(G_1)\) either maps to an isolated edge of \(U(G_2)\), in which case the corresponding isolated vertex of \(T(G_1)\) can map to the corresponding isolated vertex of \(T(G_2)\), or the isolated edge of \(U(G_1)\) maps to an edge of a connected component of \(U(G_2)\) of order at least 3, in whic case the corresponding isolated vertex of \(T(G_1)\) can map to one of the two vertices connected to the corresponding edge of \(T(G_2)\). This if \(U(G_1)\) is a topological minor of \(U(G_2)\), the \(T(G_1)\) is a topological minor of \(T(G_2)\), and therefore from the first lemma \(G_1\) is a topological minor of \(G_2\), and this is our second lemma.
For our third lemma, we must bound the order of \(U(G)\), given that \(G\) has order \(n\). Each loop of \(G\) adds two vertices, and each nonloop edge of \(G\) adds one vertex. So if we assign weights to the vertices of \(G\), where each loop adds 2 to the weight of the vertex it is connected to, and each nonloop edge adds 1/2 to each of the vertices it is connected to, and each isolated vertex is assigned a weight of 1, then the sum of the weights of all the vertices will equal the number of added vertices. Now, if a vertex is connected to a loop, it cannot connect to another loop, and can connect to at most one nonloop edge, so the maximum weight of the vertex in this case is 5/2. If a vertex is not connected to a loop, but is not isolated, it can connect with at most 3 nonloop edges, so the maximum weight is 3/2. Finally, an isolated vertex has a weight of 1. So 5/2 is a universal upper bound for the weight of a vertex; thus at most \(\lfloor{5n/2}\rfloor\) vertices are added, and \(T(G)\) can have at most \(\lfloor7n/2\rfloor\) vertices.
Finally, suppose we have a maximal allowable sequence of subcubic graphs \(G_1, G_2, \ldots, G_m\), where \(m = SCG(n)\). Define \(H_{4i - j}\) for \(j = 0,1,2,3\) and \(1 \le i \le m\) to be the graph with \(U(G_i)\) plus \(j\) isolated vertices. Thus, letting \(I\) be the graph of one isolated vertex, we define \(H\) to be the sequence
\(U(G_1) + 3I, U(G_1) + 2I, U(G_1) + I, U(G_1), U(G_2) + 3I, U(G_2) + 2I, U(G_2) + I, U(G_2), \ldots\)
We must show that if \(a < b\), there is no topological embedding from \(H_a\) into \(H_b\). If \(a = 4i-j, b = 4i-k\), with \(0 \le k < j \le 3\), then \(H_a\) is \(H_b\) with \(j-k\) more isolated vertices; thus there can be no topological embedding from \(H_a\) to \(H_b\) as \(H_a\) has more vertices than \(H_b\). Otherwise \(a = 4i-k, b=4j-l\) with \(i < j\). Suppose \(H_a = U(G_i) + kI\) is a topological minor of \(H_b = U(G_j) + lI\). Then \(U(G_i)\) must be a subgraph of a subdivision of \(U(G_j) + lI\); but any subdivision of \(lI\) is just \(lI\), a collection of isolated vertices. Since \(U(G_i)\) has no isolated vertices, none of its vertices can map to any of the isolated vertices of \(U(G_j) + lI\), so \(U(G_i)\) must be a topological minor of \(U(G_j)\). But, by our second lemma above, this implies that \(G_i\) is a topological minor of \(G_j\), which contradicts our assumption that the \(\lbrace G_k \rbrace\) formed an allowable sequence. So for no \(a < b\) do we have that \(H_a\) is a topological minor of \(H_b\).
Further, we have that \(|G_i| \le n+i\), so by the third lemma above we have \(|U(G_i) \le \lfloor{\frac{7n+7i}{2}}\rfloor\), and therefore \(|H_{4i-j}| \le \lfloor{\frac{7n+7i+2j}{2}}\rfloor\). In particular for \((i,j) = (1,3)\) we have \(|H_1| \le \lfloor{\frac{7n+13}{2}}\rfloor = \lfloor{\frac{7n+11}{2}}\rfloor + 1\). Each increase of \(i\) by one increases the left hand index of \(|H_{4i-j}| \le \lfloor{\frac{7n+7i+2j}{2}}\rfloor\) by 4 and the right hand side by either 3 or 4; each decrease of \(j\) by 1 increases the left hand index by 1 and decreases the right hand side by 1. So for all \(i\) we have \(H_i \le \lfloor{\frac{7n+11}{2}}\rfloor+i\). Since the \(H_i\) are a sequence of allowable simple subcubic subgraphs of length \(4SCG(n)\), we have \(SSCG(\lfloor{\frac{7n+11}{2}}\rfloor) \ge 4 SCG(n) \).

Hmm, this turned out to require more detail than I expected. Deedlit11 (talk) 03:57, October 3, 2015 (UTC)

I have only read up to about half of the proof of the first lemma, but there are fundamental flaws already there. Firstly, I just want to mention that \(S\) behaves weirdly on cycles, because from your description, it will map any cycle to a graph with one edge and no vertices, which doesn't sound quite correct. Second, let me say that if something is clear then it doesn't necessarily have to be true. Apparently when you said "clearly \(S\) respects the subgraph relation" you didn't consider a 1-path being a subgraph of a triangle. Third and most important - first lemma isn't even valid. If we take \(G_1\) to be a union of two disjoint 1-paths and \(G_2\) to be a triangle, then \(G_1\) is not a minor of \(G_2\), but \(T(G_1)\), which is a union of two 3-paths, is a minor (indeed, a subgraph) of \(T(G_2)\), which is a hexagon.
I hope there is a way to fix this proof, but as you can see, there is a lot of work to be done :| LittlePeng9 (talk) 06:41, October 3, 2015 (UTC)
Derp Deedlit11 (talk) 09:42, October 3, 2015 (UTC)
Okay, Wojowu gave me an idea that turns out to work. So, here is the proof take two:
First, we define a mapping \(U\) from subcubic graphs to simple subcubic graphs as follows: For any subcubic graph \(G\), we construct \(U(G)\) by replacing each non-loop-connected vertex of \(G\) with a triangle (three vertices pairwise connected by edges) and each loop-connected vertex of \(G\) with two fused triangles (four vertices with all pairs of vertices but one connected with an edge); we will define a "node" to be one of the aforementioned triangles or fused triangles. Then, for each edge between two vertices of \(G\), construct an edge between vertices of degree 2 of the corresponding nodes. This can always be done, as a loop-connected vertex of \(G\) can have one other edge, and a fused triangle has two available vertices of degree 2, while a non-loop-connected vertex of \(G\) can have at most three edges, and a triangle has three vertices of degree 2. Observe that, while we can choose between different vertices of a node to connect, the vertices of degree 2 of a node are all symmetric with respect each other, so the above construction is unique up to isomorphism. Also, the constructed graph is simple and subcubic.
Our main lemma is that if \(U(G_1)\) is a topological minor of \(U(G_2)\), then \(G_1\) is a topological minor of \(G_2\). Note that an embedding must take cycles to cycles, and fused cycles to fused cycles (a fused cycle is two cycles sharing a path of length one or more). Further, a subdivision of a cycle is a cycle, and a subdivison of a fused cycle is a fused cycle. So, an embedding from a subdivision of \(U(G_1)\) into \(U(G_2)\) induces a mapping \(f\) from the nodes of \(U(G_1)\) to the nodes of \(U(G_2)\), where fused triangles get mapped to fused triangles.
Next, we pull back from \(U(G_i)\) to \(G_i\). Each node of \(U(G_i)\) originates from a vertex of \(G_i\), so this takes \(f\) to a mapping \(g\) from vertices of \(G_1\) to vertices of \(G_2\), where loop-connected vertices get mapped to loop-connected vertices. The map from loops of \(G_1\) to loops if \(G_2\) is immediate, so all we need now is to map edges of \(G_1\) to disjoint paths of \(G_2\). A edge between vertices \(u\) and \(v\) corresponds to an edge between \(U(u)\) and \(U(v)\), which corresponds to a disjoint path between \(f(U(v))\) and \(f(U(u))\). When we pull the map back to \(G_2\), we get a path between \(g(u)\) and \(g(v)\). We claim that for any edges \(uv, wx\) of \(G_1\), the paths \(g(u)g(v),g(w)g(x)\) defined above are disjoint. Indeed, if \(g(u)g(v)\) and \(g(w)g(x)\) share an edge, then that edge corresponds to an edge of \(U(G_2)\), which must be contained in both the defined paths between \(f(U(v))\) and \(f(U(u))\). But those paths were defined by an embedding of a subdivision of \(U(G_1)\) into \(U(G_2)\), and therefore must be disjoint. So we have that the nonloop edges of \(G_1\) get mapped to disjoint paths of \(G_2\), and thus we conclude that \(G_1\) is a topological minor of \(G_2\), as desired.
Finally, suppose we have a maximal allowable sequence of subcubic graphs \(G_1, G_2, \ldots, G_m\), where \(m = SCG(n)\). Define \(H_{4i - j}\) for \(j = 0,1,2,3\) and \(1 \le i \le m\) to be the graph with \(U(G_i)\) plus \(j\) isolated vertices. Thus, letting \(I\) be the graph of one isolated vertex, we define \(H\) to be the sequence
\(U(G_1) + 3I, U(G_1) + 2I, U(G_1) + I, U(G_1), U(G_2) + 3I, U(G_2) + 2I, U(G_2) + I, U(G_2), \ldots\)
We must show that if \(a < b\), there is no topological embedding from \(H_a\) into \(H_b\). If \(a = 4i-j, b = 4i-k\), with \(0 \le k < j \le 3\), then \(H_a\) is \(H_b\) with \(j-k\) more isolated vertices; thus there can be no topological embedding from \(H_a\) to \(H_b\) as \(H_a\) has more vertices than \(H_b\). Otherwise \(a = 4i-k, b=4j-l\) with \(i < j\). Suppose \(H_a = U(G_i) + kI\) is a topological minor of \(H_b = U(G_j) + lI\). Then a subdivision of \(U(G_i)\) must be a subgraph of \(U(G_j) + lI\); but since a subdivision of \(U(G_i)\) has no isolated vertices, none of its vertices can map to any of the isolated vertices of \(U(G_j) + lI\), so \(U(G_i)\) must be a topological minor of \(U(G_j)\). But, by our second lemma above, this implies that \(G_i\) is a topological minor of \(G_j\), which contradicts our assumption that the \(\lbrace G_k \rbrace\) formed an allowable sequence. So for no \(a < b\) do we have that \(H_a\) is a topological minor of \(H_b\).
Since each vertex of \(G\) gets mapped to either a triangle (3 vertices) or two fused triangles (4 vertices), \(|U(G)|\) (the number of vertices of \(G\)) is at most \(4|G|\). Thus \(|H_{4i-j}| \le 4|G_i| + j \le 4n + 4i + j \le 4n + (4i - j) + 6\), and so \(|H_i| \le 4n + 6 + i\), and the \(H_i\) form a valid sequence for \(SSCG(4n+6)\) of length \(4 SCG(n)\). Thus \(SSCG(4n+6) \ge 4SCG(n)\). Deedlit11 (talk) 09:41, October 3, 2015 (UTC)
Scratch that, the above proof is still flawed :( Deedlit11 (talk) 10:11, October 3, 2015 (UTC)

Correct me if I'm wrong, but there is no proof that SCG(2) > \(f_{\vartheta(\Omega^{\omega})}(\text{SCG(1)})\), there is only proof that it is greater than \(f_{\vartheta(\Omega^{\omega})}(\text{MSCG(1)})\), where \(\text{MSCG(1)}\) is the best known sequence for SCG(1). Maybe called Googology Noob (talk) 16:34, March 7, 2016 (UTC)

You're correct (I misread), although I'd also like to note that heuristically, its improbable that that is not the case due to the unlikelihood for a different sequence to produce a larger value for SCG(1), but this gap become negated at the level of SCG(2), unless the difference at SCG(1) is minute. I think we can say that \(\text{SCG}(2)\gtrsim f_{\vartheta(\Omega^{\omega})}(\text{SCG}(1))\), but an approximation isn't a bound. ~εmli 21:21, March 7, 2016 (UTC)

Allow unbouded valence?

Harvey's original message says

If we were considering graphs with unbounded valence, then we could not allow multiple edges for finite statements

while this article says

For the sake of this article, subcubic graphs are allowed to be multigraphs, and are not required to be connected.

It appears to be saying the opposite. If we allow suncubic graphs to be multigraphs, we cannot allow unbouded valence, and therefore they ARE required to be connected. Am I correct? 🐟 Fish fish fish ... 🐠 17:25, January 2, 2017 (UTC)

Valence refers to the number of edges attached to a vertex, a.k.a. the degree. So subcubic graphs have valence bounded by definition. Connectedness has nothing to do with this. LittlePeng9 (talk) 17:42, January 2, 2017 (UTC)
I see. Thanks. 🐟 Fish fish fish ... 🐠 18:09, January 2, 2017 (UTC)

Well-quasi-founding

The article says

The Robertson-Seymour theorem proves that subcubic graphs are well-founded by homeomorphic embeddability,

implying that subcubic graphs are well ordered. But, as the Wikipedia article on Robertson–Seymour theorem says

The Robertson–Seymour theorem states that finite undirected graphs and graph minors form a well-quasi-ordering. It is obvious that the graph minor relationship does not contain any infinite descending chain, because each contraction or deletion reduces the number of edges and vertices of the graph (a non-negative integer).

Well-foundedness of the subcubic graphs is a trivial part, and important part is well-quasi-ordering. Therefore, the article should be modified by using the term well-quasi-ordering, I think. 🐟 Fish fish fish ... 🐠 19:08, January 2, 2017 (UTC)

"implying that subcubic graphs are well ordered" This doesn't imply they are well ordered, since the ordering is partial (i.e. the graphs can be incomparable under this ordering). Other than that, you are right - the important bit is the fact we don't have any infinite antichains (sets of pairwise incomparable graphs). For the record, the notion of "well-quasi-ordered" implies both that there are no infinite descending chains and there are no infinite antichains, which is precisely what is required here. I'm going to edit the page right now. LittlePeng9 (talk) 19:20, January 2, 2017 (UTC)


How about the best graph sequence for SSCG(13)?

The original article of Harvey Friedman suggest to start from two copies of K(3,3) and a K2:

http://www.cs.nyu.edu/pipermail/fom/2006-April/010305.html

What if we start from Petersen graph + K4 instead? Or maybe it's better to start from Heawood graph?

Some ordinal levels are listed here: http://googology.wikia.com/wiki/User_blog:Hyp_cos/SCG(n)_and_some_related

AndreyKulsha (talk) 13:07, March 11, 2017 (UTC)

Friedman's suggestion was by no means meant to be optimal. He just took whatever worked for him. Nowadays we know that just SSCG(3) is larger than the sequence suggested by Friedman (which gave only a lower bound) for SSCG(13). LittlePeng9 (talk) 13:30, March 11, 2017 (UTC)
Of course it's impossible to know, since we'll never complete the sequence, but starting from the Heawood graph seems like a good idea.
Interesting fact: the ordinal for general simple graphs under the minor relation lies between \(\theta(\Omega_\omega,0)\) and \(\theta(\Omega_\omega^\omega,0)\). Since every simple graph is embeddable in a simple subcubic graph, they should have the same ordinal. Deedlit11 (talk) 13:31, March 11, 2017 (UTC)
To surpass TREE(3) or TREE(TREE(...TREE(3)...)) (with TREE(3) TREE's) we just need SSCG(3), and I guess that to surpass \(\Pi_1^1\text{-CA}_0\) we just need SSCG(7). But I still don't know the structure of the ordering beyond \(\theta(\Omega_2,0)\).
By the way, I've never seen "SSCG(n) lies \(\le\theta(\Omega_\omega^\omega,0)\)"; I've only seen "SSCG(n) lies below TFB". {hyp/^,cos} (talk) 14:36, March 11, 2017 (UTC)
Yeah, it's a recent result by Michael Rathjen. He has some slides discussing his research here: [2]. Deedlit11 (talk) 20:20, March 11, 2017 (UTC)

The optimal starting sequences for SSCG(n)

For SSCG(2) it's the sequence found by Adam Goucher:
G1 = 2 1
G2 = 2 2
G3 = 2 3
and then a trivial sequence of linear forests (42, 4111, 411, 41, 4, 3332, ...) follows.
For SSCG(3) my guess coincides with a guess by {hyp/^,cos} until 11th term, but then disagree:
G1 = 3 1
G2 = 3 2
G3 = 3 3
G4 = 3 4
G5 = 3 5
G6 = 3 6
G7 = 3 7
G8 = 3 8
G9 = 3 9
G10 = 3 a
G11 = 3 b
G12 = 3 c
G13 = 3 d
G14 = 3 e
G15 = 3 f
G16 = 3 g
G17 = 3 h
G18 = 3 i
G19 = 3 j
G20 = 3 k
G21 = 3 l
G22 = 3 m
G23 = 3 n
G24 = 3 o
G25 = 3 p
G26 = 3 q
G27 = 3 r
G28 = 3 s
G29 = 3 t
G30 = 3 u
G31 = 3 v
G32 = 3 w
G33 = 3 x
G34 = 3 y
When the outward triangle decays to a single vertex, the third component explodes to many copies of
3 z1
When all of them disappear, the second component explodes to a lot of copies of
3 z2
and each of them can grow to a tree of polyvalent units like this one:
3 z2tree
Then, after a while, the first component explodes to a heavy lot of copies of
3 z3
and each of them can grow to a tree of polyvalent units like this one:
3 z3tree
For SSCG(4) my guess is:
G1 = 4 1
G2 = 4 2
G3 = 4 3
G4 = 4 4
G5 = 4 5
G6 = 4 6
G7 = 4 7
G8 = 4 8
G9 = 4 9
G10 = 4 a
G11 = 4 b
G12 = 4 c
G13 = 4 d
G14 = 4 e
G15 = 4 f
G16 = 4 g
When the lower structure decays, a large tree of tetravalent units
4 z1
follows, and then, when in decays to a single unit, a very large tree of condensed cycles appear:
Gn = 4 z2
For SSCG(5) my guess is:
G1 = 5 1
G2 = 5 2
G3 = 5 3
G4 = 5 4
G5 = 5 5
G6 = 5 6
G7 = 5 7
G8 = 5 8
G9 = 5 9
G10 = 5 a
G11 = 5 b
G12 = 5 c
G13 = 5 d
G14 = 5 e
The triangle decays in Goucher's way, and then we get a cube, (23×295-1)×3/7 triangular prisms with additional vertex on the base edge and a normal triangular prism.
Any improvements? AndreyKulsha (talk) 17:52, March 3, 2018 (UTC)
Well, you can't really say whether one starting sequence is better than another, unless you know the plan for the whole sequence. One way to do this is to devise an ordering on subcubic graphs that you want to follow, and which respects the topological minor relation. Then you can follow a "greedy strategy", taking the highest available graph each time that doesn't have too many vertices. Of course, you are free to deviate from the greedy strategy whenever you want in the starting sequence - but then you can fill in the rest of the sequence using the greedy algorithm, and if we know what ordinal the last member of the starting sequence corresponds to, we can have an idea of the length of the sequence.
I imagine you have some ordering in mind, at least informally. If you could describe your ordering, it would be a great help. Deedlit11 (talk) 17:45, March 4, 2018 (UTC)
Starting from G13 in my variant of SSCG(3) sequence one can derive a graph containing lots of copies of G12 from the sequence by {hyp/^,cos}. Getting into account that G1-G11 are the same, can we really say that my sequence is better? :)
As for the ordering, that's just intuition. The main goal on each step was to prevent getting too much restrictions on the further steps. AndreyKulsha (talk) 20:52, March 4, 2018 (UTC)
Well, roughly speaking, the priority rises this way:
vertices (by valence);
cycles (by size);
condensed cycles (by the number of shared vertices);
polyhedra (by the number of faces);
non-planar structures (by the crossing number).
Also, please take a look and the second component of G22 in {hyp/^,cos}'s sequence vs. mine. Both of us used 8 vertices to build it, but it seems that my variant is more promising. AndreyKulsha (talk) 20:21, March 5, 2018 (UTC)
Colin de Verdière graph invariant seems to be a good ordering criterion. AndreyKulsha (talk) 23:00, April 10, 2018 (UTC)

Questions about valence and computation

Is there a reason why Friedman chose to restrict graphs to be subcubic? Is the behaviour for graphs with a lower maximum valence trivial, or does the well-ordering break down for higher valences than three, or something else?

Also, one of the allowed transformations in the "implementing with matrices" sections mentions having two rows A and B such that A+B contains a 2 somewhere. Does that rule only apply when A+B has exactly one 2 in it somewhere, or can there be other 2's? If multiple 2's are allowed, then are we supposed to delete all columns that contain those 2's or just one of them?  QuasarBooster (talk) 02:13, November 18, 2019 (UTC)

The very first thing discussed in Robertson-Seymour theorem was SIMPLE graphs with arbitrarily large valence. Friedman then focused on SSCG because graph minor and topological minor are the same on subcubic graphs. After that, Friedman used SCG, whose graph minor relation is still well-quasi-ordering, where subcubic graphs were not necessarily required to be simple. {hyp/^,cos} (talk) 03:09, November 18, 2019 (UTC)
Community content is available under CC-BY-SA unless otherwise noted.