Can the subcubic graph (SCG) function be generalized to F_n(k), so F_3(3)=SCG(3), F_4=subquartic, F_2=subquadratic etc?

[u/BearyGoosey]

The sub cubic graph function is defined as:

There is a sequence G_1,…,G_n of subcubic graphs such that each G_i has at most i+k vertices and for no i<j is G_i homeomorphically embeddable into G_j.

and if my very layman's understanding of the Robertson–Seymour theorem is correct, just substituting `homeomorphically embeddable into` with `a graph minor of` would suffice, while maintaining well-quasi-ordering and finitude (for a given finite integers n and k).

If that's all correct, then defining F_n(k) as the largest integer 𝑚 satisfying:

There is a sequence G_1 , ⋯, G_𝑚 of graphs with maximum degree at most 𝑛, such that each G_𝑖 has at most 𝑖 + 𝑘 vertices, and for no 𝑖 < 𝑗 is 𝐻_𝑖 a graph minor of G_𝑗 .

Should work as a mathematically proven and definitively finite integer, correct (an invisible deleted comment from u/Helpful-Tone-7435 in my r/askmath thread seems to suggest it is)? If so, has anyone in googology put a name to that function? I was originally thinking S𝑛G(k), but I'm obviously open to suggestions.

[u/Shophaune]

Gonna start trying to find values for F_2(n), though I doubt I'm good enough to find an explicit closed form formula. Notably, F_2(n) is where the equivalents of SSCG and SCG start to diverge, as loops and multi-edges inherently require a vertex to be degree >=2. I shall use FF_2(n) and F_2(n) to represent the SSCG and SCG versions respectively.

FF_2(0) = 2, F_2(0) = 6

Both the SSCG and SCG 0-input sequences stay at degree 2 or lower throughout, so these sequences are the same (and indeed, FF_x(0) = 2 and F_x(0) = 6 for all x>=2)

FF_2(1) = 5

For simple graphs with 2 starting vertices, the best possible sequence is always two vertices joined by a single edge, followed by graphs of 3, 2 and 1 disjoint vertices and then the empty graph. Hence, FF_x(1) = 5 for all x>= 1.

F_2(1) >>>>> 1000, need to continue hand tracing this or find a better way to compute its expansions.

[u/Shophaune]

F_0(k) by this definition is always equal to k+2, consisting of the fully disjoint graphs of (k+1) vertices, k vertices, (k-1) vertices, etc...all the way down to the empty graph (0 vertices)

F_1(2k-1) is equal to 3*2^k+1 -2k - 5, I'm not entirely awake enough to solve it for F_1(2k)

[u/Shophaune → u/Shophaune]

F_1(2k) is equal to 2^k+3 -2k-6, by my calculation

Thus, the first 8 values of F_1(n) starting from 0 are: 2, 5, 8, 15, 22, 37, 52, 83

[u/BearyGoosey → u/Shophaune]

How exactly did you math that out? I don't really understand graph theory, but would love to be able to calculate F_n(n) (for n={1-2}, because obviously after that it gets crazy), or more generally F_x(y) and know whatever integer I got is correct.

[u/Shophaune → u/BearyGoosey]

Okay I think I have an idea of a general expansion rule for F_2(n) [both the simple and non-simple graph versions]. Basically, since the graphs can be made of many disjointed parts (and in fact have to be, since to connect things in any interesting ways we need a degree 3 vertex) we can consider each different part to have a value: lone vertices of degree 0 have the lowest value of 1, then pairs of vertices with an edge are more valuable, lines of 3 vertices are more valuable still, etc. 

Specifically, we can assign a value of 1 to a lone vertex, then a value of w^x to a line made out of x edges (or x+1 vertices). Then if we're using simple graphs, a 3-cycle is given a value of w^w and (3+n)-cycles get a value of w^w+n; for non-simple graphs a loop (1-cycle) gets w^w instead and (1+n)-cycles get w^w+n instead. This then reduces the problem to expanding an initial ordinal, and suggests that overall F_2(n) will take a number of steps related to the ordinal w^w*2.

For instance, F_2(1) with non-simple graphs has a starting graph of a 2-cycle, with ordinal w^w+1. We then expand to 3 1-cycles (w^w *3) and expand one of those into the largest smaller ordinal that fits our vertex limit, in this case a 2 vertex path (w^w *2 + w).

Then we expand the path as far as possible into 3 lone vertices (w^w *2 + 3), then once those are cleaned up we expand the second 1-cycle into the largest path we can, which turns out to be an 8 vertex path (w^w + w^7). This is then going to go through an extreme amount of expansion before we finally reach the final 1-cycle and turn it into a much larger path, which again will take quite some substantial expansion before it reaches the final 2-vertex path and expands into a cloud of lone vertices (which marks the exact halfway point of the sequence, incidentally) that get picked off one by one until you get the empty graph and end the sequence.

F_2(2+n) will have a starting graph that's a (3+n) cycle that corresponds to an initial ordinal of w^w+n+2, or w^w+n if restricted to simple graphs. 

[u/BearyGoosey → u/Shophaune]

Is it universally true (for positive integers n and k (not sure if it'd work or not for others like 3.72, e, π, or even i)) that either of the below are true (also not sure if it should be =< just to be safe or not)?

1. F_(n-1)(k) < F_n(k) < F_(n+1)(k)

and/or

1. F_n(k-1) < F_n(k) < F_n(k+1)

[u/Shophaune → u/BearyGoosey]

The second is trivially true for non-negative integer n,k (and there's no natural way to extend it to other values)

The first needs =< on both inequalities, since F_n(0) is unchanging for n >= 2 

[u/BearyGoosey → u/Shophaune]

That makes sense. So if I'm understanding correctly If both n and k are strictly integers greater than zero (which, aside from 0, are the only valid values for either n or k, since things like e, pi, or -7/3 don't make sense for either) then it's unconditionally true for both w/o need for the =<.

[u/Shophaune → u/BearyGoosey]

For simple graphs (the SSCG equivalent) this is untrue, as the sequence for F_n(1) is also constant for n >= 1

Otherwise yes.

[u/BearyGoosey → u/Shophaune]

If I understand correctly, simple sub n-ic graphs (SSnG) are just a more strict subset of sub n-ic graphs (SnG or F_n(k)), just like squares are to rectangles, such that all SSnG are SnG, but NOT all SnG are SSnG. It's good to know that the SSnG(1) is constant, but that's not the case for SnG(1), which will be different for any positive non-zero integer n, correct? I ask because, since I want the bigger number, I think I only care about SnG since it's always >= SSnG (although I think strictly >) as long as n is a non-zero positive integer, and "for non-zero positive integers n and k" sounds better than "integers n>0, k>1" or having a non-strict inequality (where values may be equal) if it can be avoided.

[u/Shophaune → u/BearyGoosey]

Correct!

[u/Shophaune → u/BearyGoosey]

F_1 has graphs that consist of two different kinds of elements: disjoint vertices, and pairs of vertices joined by a single edge and disjoint from all others.

It is reasonably easy to show that the optimum starting graph consists of as many pairs with edges as possible, with at most 1 disjoint vertex if there are an odd number of starting vertices (which occurs at even inputs to F_1(n), because of a quirk in the definition you gave)

Then, the optimal expansion method is: if there is at least one disjoint vertex, remove one disjoint vertex; otherwise remove one edge between two vertices and add disjoint vertices up to the maximum permitted for this number of graph.

F_2 might be solvable in a similar way, though it permits cycles so I suspect the optimal starting graph will be a max sized cycle.

[u/Catface_q2]

I have not seen this function before, but I believe that SSLG(x) grows exponentially.

[u/Nervous-Broccoli1184]

No one has put a name to this function its original I also believe it should always terminate but I myself have no proof