FANDOM


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

2. K3,3 with additional edge.

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.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.