This blog post is about planar, connected and simple variants of SCG.

This site is a great site for small simple graphs: graphclasses.

## SSCG ordinal levels beyond \(\vartheta(\Omega_2)\)

### Up to \(\theta(\Omega_2,1)\)

- K
_{4}with one vertex at \(\vartheta(\Omega_2)+1\) - K
_{4}with 1-path connected at \(\vartheta(\Omega_2)+2\) - K
_{4}with (k+1)-path connected at \(\vartheta(\Omega_2)+k\) - K
_{4}with claw connected at \(\vartheta(\Omega_2)+\omega\) - K
_{4}with K_{4}connected at \(\vartheta(\Omega_2)2\) - Claw with K
_{4}at all three ends at \(\vartheta(\Omega_2)^\omega\) - Triangle with K
_{4}at two ends at \(\varepsilon_{\vartheta(\Omega_2)+1}\) - Square with K
_{4}at two ends at \(\Gamma_{\vartheta(\Omega_2)+1}\) - Two triangles fused with K
_{4}at two ends at \(\theta(\Omega^\omega,\vartheta(\Omega_2)+1)\) - K
_{2,3}with K_{4}at two ends at \(\theta(\varepsilon_{\Omega+1},\vartheta(\Omega_2)+1)\)

### Up to \(\vartheta(\Omega_22)\)

- K
_{4}at \(\vartheta(\Omega_2)\) - K
_{4}with two vertices at one of the ends at \(\theta(\Omega_2,1)\) - K
_{4}with two vertices and one 1-path at each at \(\theta(\Omega_2,2)\) - K
_{4}with two vertices with claw at each at \(\theta(\Omega_2,\omega)\) - K
_{4}with two vertices with K_{4}at each at \(\theta(\Omega_2,\vartheta(\Omega_2))\) - K
_{4}with three vertices at one of the ends at \(\vartheta(\Omega_2+1)\) - K
_{4}with four vertices at one of the ends at \(\vartheta(\Omega_2+\Omega)\) - K
_{4}with triangle fused at one of the ends at \(\vartheta(\Omega_2+\Omega^\omega)\) - K
_{4}fused with K_{4}_{ }in some way \(\vartheta(\Omega_22)\)

### Beyond \(\vartheta(\Omega_\omega)\)

Some ordinal levels (in FGH):

- K
_{3,3}at \(\vartheta(\Omega_\omega)\) - K
_{3,3}with one vertex at \(\vartheta(\Omega_\omega)+1\) - K
_{3,3}with 1-path connected at \(\vartheta(\Omega_\omega)+2\) - K
_{3,3}with (k+1)-path connected at \(\vartheta(\Omega_\omega)+k\) - K
_{3,3}with claw connected at \(\vartheta(\Omega_\omega)+\omega\) - K
_{3,3}with K_{3,3}connected at \(\vartheta(\Omega_\omega)2\) - Claw with K
_{3,3}at all three ends at \(\vartheta(\Omega_\omega)^\omega\) - Triangle with K
_{3,3}at two ends at \(\varepsilon_{\vartheta(\Omega_\omega)+1}\) - Square with K
_{3,3}at two ends at \(\Gamma_{\vartheta(\Omega_\omega)+1}\) - Two triangles fused with K
_{3,3}at two ends at \(\theta(\Omega^\omega,\vartheta(\Omega_\omega)+1)\) - K
_{2,3}with K_{3,3}at two ends at \(\theta(\varepsilon_{\Omega+1},\vartheta(\Omega_\omega)+1)\) - K
_{4}with two extra vertices with K_{3,3}connected at \(\theta(\Omega_2,\vartheta(\Omega_\omega)+1)\)

These might not be true.

- K
_{3,3}with two vertices at one of the ends at \(\theta(\Omega_\omega,1)\) - K
_{3,3}with two vertices and one 1-path at each at \(\theta(\Omega_\omega,2)\) - K
_{3,3}with two vertices with claw at each at \(\theta(\Omega_\omega,\omega)\)

## PSSCG(n) and SSCG(n)

### SSCG(3)

**PSSCG(3) = SSCG(3)**

This is quite easy to prove. The first graph must be \(K_4\) for an optimal sequence. But \(K_4\) is minor of \(K_{3,3}\), therefore \(K_{3,3}\) cannot appear in the sequence for SSCG(3). \(K_5\) cannot appear by definition beacause it is not subcubic.

### SSCG(4)

**PSSCG(4) <? SSCG(4)**

This one is harder. The following graphs are candidates for the first graph for an optimal sequence (others are not subcubic or are minor of these):

- \(\bar{P_2\cup P_3}\)
- \(K_4\cup K_1\)

The first is minor of \(K_{3,3}\) but second isn't. ~~It seems unlikely that \(K_4\cup K_1\) is optimal as first graph~~, but I can't say PSSCG(4) = SSCG(4) or PSSCG(4) < SSCG(4) for now, so giving formal proof (or disproof?) of it remains unsolved problem. (see also the SSCG(4) section).

### SSCG(5) (earlier by Peng and Deedlit)

**SSCG(5) >= PSSCG(6)+1**

### SSCG(6) (earlier by Peng and Deedlit)

**SSCG(6) >= PSSCG(12)+6**

### SSCG(7) (improved)

**SSCG(7) >>** **\(f_{\theta(\Omega_2,\vartheta(\Omega_\omega)+1)}(\text{PSSCG}^3(8))\)**

Analysis:

- 1. K
_{3,3}with one vertex on two different edges.

- 2. K
_{3,3}with three vertices on an edge.

- 3. K
_{3,3}with two vertices on an edge and one vertex connected to each of them.

- 4. K
_{3,3}with two vertices on an edge and claw connected to one vertex

- 5. K
_{3,3}with two vertices on an edge and 4-path connected to one vertex

- 6. K
_{3,3}with two vertices on an edge and 3-path connected to one vertex and a stick

- 7, 8, 9. K
_{3,3}with two vertices on an edge and 3-path connected to one vertex and 3,2,1 dots.

- 10. K
_{3,3}with two vertices on an edge and 3-path connected to one vertex.

- 11. K
_{3,3}with two vertices on an edge and 2-path connected to one vertex and PSSCG(8) sequence.

- PSSCG(8)+10. K
_{3,3}with two vertices on an edge and 2-path connected to one vertex.

- PSSCG(8)+11. K
_{3,3}with two vertices on an edge and 1-path connected to one vertex and PSSCG(PSSCG(8)+9) sequence.

- >PSSCG(PSSCG(8)+9). K
_{3,3}with two vertices on an edge and 1-path connected to one vertex.

- >PSSCG(PSSCG(8)+9). K
_{3,3}with two vertices on an edge and PSSCG(PSSCG(PSSCG(8)+9)) sequence.

- >PSSCG(PSSCG(PSSCG(8)+9)). K
_{3,3}with two vertices on an edge.

Let X be PSSCG^{3}(8), even larger than above number. We know that, in Hyp cos' system, K_{4} is at \(\vartheta(\Omega_2)\) level. So, using his method, K_{4} with two extra vertices with K_{3,3} connected has level \(\theta(\Omega_2,\vartheta(\Omega_\omega)+1)\).

I think we can reach \(\theta(\Omega_\omega,1)\).

## SSCG(4)

We saw we had two options for the first graph:

- \(\text{co}(P_2\cup P_3)\)
- \(K_4\cup K_1\)

### \(\text{co}(P_2\cup P_3)\)

- 1. \(\text{co}(P_2\cup P_3)\)

- 2. \(K_4\) + stick

- 3. \(K_4\) + 3 dots

- 4. \(K_4\) + 2 dots

- 5. \(K_4\) + 1 dot

- 6. \(K_4\)

This doesn't really give us a good bound.

### \(K_4\cup K_1\)

1. \(K_4\cup K_1\)

2. \(K_{3,3}\)

Let v(n) stand for *vertex connected to vertex on edge n*. The edges are the 6 edges of \(K_4\).

# | Edge 1 | Edge 2 | Edge 3 | Edge 4 | Edge 5 | Edge 6 |
---|---|---|---|---|---|---|

3. | Double edge, vertex | |||||

4. | Double edge | Double edge | ||||

5. | Double edge | v(3), vertex | v(2) | |||

6. | Double edge | v(3) | v(2) | v(5) | v(4) | |

7. | Double edge | v(3) | v(2) | 1 vertex | 1 vertex | 1 vertex |

8. | Double edge | v(3) | v(2) | 2 vertices | 2 vertices | |

9. | Double edge | v(3) | v(2) | 4 vertices | 1 vertex | |

10. | Double edge | v(3) | v(2) | 3 vertices | 1 vertex | |

11. | Double edge | v(3) | v(2) | 2 vertices | 1 vertex | |

12. | Double edge | v(3) | v(2) | 1 vertex | 1 vertex | |

13. | Double edge | v(3) | v(2) | 9 vertices | ||

21. | Double edge | v(3) | v(2) | |||

22. | Double edge | 4 vertices | 4 vertices | 4 vertices | 4 vertices | 4 vertices |

23. | Double edge | 5 vertices | 5 vertices | 4 vertices | 4 vertices | 3 vertices |

24. | Double edge | 7 vertices | 4 vertices | 4 vertices | 4 vertices | 3 vertices |

27. | Double edge | 4 vertices | 4 vertices | 4 vertices | 4 vertices | 3 vertices |

28. | Double edge | 7 vertices | 7 vertices | 6 vertices | 3 vertices | 3 vertices |

29. | Double edge | 9 vertices | 6 vertices | 6 vertices | 3 vertices | 3 vertices |

32. | Double edge | 6 vertices | 6 vertices | 6 vertices | 3 vertices | 3 vertices |

33. | Double edge | 10 vertices | 10 vertices | 5 vertices | 3 vertices | 3 vertices |

37. | Double edge | 9 vertices | 9 vertices | 5 vertices | 3 vertices | 3 vertices |

46. | Double edge | 8 vertices | 8 vertices | 5 vertices | 3 vertices | 3 vertices |

67. | Double edge | 7 vertices | 7 vertices | 5 vertices | 3 vertices | 3 vertices |

112. | Double edge | 6 vertices | 6 vertices | 5 vertices | 3 vertices | 3 vertices |

205. | Double edge | 5 vertices | 5 vertices | 5 vertices | 3 vertices | 3 vertices |

- The 206th graph will be (double edge, 97 vertices , 97 vertices , 4 vertices, 3 vertices, 3 vertices)

- When doing some math, we see that the reduction grows like 3, 9, 21, 45, 93, 189, 381. In other words, it is the function 2n+3 recursed.

- The (5.94*10
^{28})th graph will be (double edge, 2.97*10^{28}vertices , 2.97*10^{28}vertices , 3 vertices, 3 vertices, 3 vertices)

- The >10
^{(8.94*1027)}th graph will be (double edge, 3 vertices , 3 vertices , 3 vertices, 3 vertices, 3 vertices). (note that I here used 2^{n}instead of summing over the recursed 2n+3s, so it is quite a bit larger)

- Now note that decreasing third is about 2
^{n}, fourth is that recursed so it more than \(2 \uparrow \uparrow n\). With the fifth we reach \(2 \uparrow\uparrow\uparrow n\)

- The >10
^{(8.94*1027)}th graph will be (double edge, 10^{(8.94*1027)}vertices , 10^{(8.94*1027)}vertices , 10^{(8.94*1027)}vertices, 10^{(8.94*1027)}vertices, 2 vertices).

- The \(k = 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow (10^{8.94\cdot 10^{27}})\)th graph will be (double edge), and then (k vertices, k vertices , k vertices, k vertices, k vertices)

- Here we reach \(2 \uparrow\uparrow\uparrow\uparrow n\) with the sixth, and the final value will be more than \(2 \uparrow\uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow (10^{8.94\cdot 10^{27}})\) before reaching \(K_4\).

We see that \(\text{SSCG}(4) > f_{\vartheta(\Omega_2)}(2 \uparrow\uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow (10^{8.94\cdot 10^{27}}))\).

We also see that it is very likely that \(\text{SSCG}(4) > \text{PSSCG}(4)\).

## Minor(n) and PSSCG(n)

### Minor(1), Minor(2) and Minor(3)

Minor(1) = SSCG(1) = PSSCG(1) = 5

Minor(2) = SSCG(2) = PSSCG(2)

Minor(3) > SSCG(3) = PSSCG(3)

### Minor(4)

Minor(4) is very, very large. The bound can be much, much stronger than that of SSCG(7).
1. K_{5}

2. K_{3,3 }with additional edge.

3. K_{3,3 }connected to two vertices.

4. K_{3,3 }connected to claw.

5. K_{3,3 }connected to 4-path

6. K_{3,3 }connected to 3-path and one vertex on two different edges.

We see that this graph is much better than the graph in the SSCG(7) sequence.