FANDOM

10,821 Pages

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)$$

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

Up to $$\vartheta(\Omega_22)$$

• K4 at $$\vartheta(\Omega_2)$$
• K4 with two vertices at one of the ends at $$\theta(\Omega_2,1)$$
• K4 with two vertices and one 1-path at each at $$\theta(\Omega_2,2)$$
• K4 with two vertices with claw at each at $$\theta(\Omega_2,\omega)$$
• K4 with two vertices with K4 at each at $$\theta(\Omega_2,\vartheta(\Omega_2))$$
• K4 with three vertices at one of the ends at $$\vartheta(\Omega_2+1)$$
• K4 with four vertices at one of the ends at $$\vartheta(\Omega_2+\Omega)$$
• K4 with triangle fused at one of the ends at $$\vartheta(\Omega_2+\Omega^\omega)$$
• K4 fused with K4 in some way $$\vartheta(\Omega_22)$$

Beyond $$\vartheta(\Omega_\omega)$$

Some ordinal levels (in FGH):

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

These might not be true.

• K3,3 with two vertices at one of the ends at $$\theta(\Omega_\omega,1)$$
• K3,3 with two vertices and one 1-path at each at $$\theta(\Omega_\omega,2)$$
• K3,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. K3,3 with one vertex on two different edges.
• 2. K3,3 with three vertices on an edge.
• 3. K3,3 with two vertices on an edge and one vertex connected to each of them.
• 4. K3,3 with two vertices on an edge and claw connected to one vertex
• 5. K3,3 with two vertices on an edge and 4-path connected to one vertex
• 6. K3,3 with two vertices on an edge and 3-path connected to one vertex and a stick
• 7, 8, 9. K3,3 with two vertices on an edge and 3-path connected to one vertex and 3,2,1 dots.
• 10. K3,3 with two vertices on an edge and 3-path connected to one vertex.
• 11. K3,3 with two vertices on an edge and 2-path connected to one vertex and PSSCG(8) sequence.
• PSSCG(8)+10. K3,3 with two vertices on an edge and 2-path connected to one vertex.
• PSSCG(8)+11. K3,3 with two vertices on an edge and 1-path connected to one vertex and PSSCG(PSSCG(8)+9) sequence.
• >PSSCG(PSSCG(8)+9). K3,3 with two vertices on an edge and 1-path connected to one vertex.
• >PSSCG(PSSCG(8)+9). K3,3 with two vertices on an edge and PSSCG(PSSCG(PSSCG(8)+9)) sequence.
• >PSSCG(PSSCG(PSSCG(8)+9)). K3,3 with two vertices on an edge.

Let X be PSSCG3(8), even larger than above number. We know that, in Hyp cos' system, K4 is at $$\vartheta(\Omega_2)$$ level. So, using his method, K4 with two extra vertices with K3,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*1028)th graph will be (double edge, 2.97*1028 vertices , 2.97*1028 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 2n instead of summing over the recursed 2n+3s, so it is quite a bit larger)
• Now note that decreasing third is about 2n, 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. K5

3. K3,3 connected to two vertices.

4. K3,3 connected to claw.

5. K3,3 connected to 4-path

6. K3,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.