## FANDOM

10,843 Pages

This blog post is about an extension of SCG. I define SCG(a,b) as the maximal length of a sequence of graphs where the graphs has a valence of at most b. The nth graph has at most a+n vertices. We have to go to a regular minor for valence greater than 3.

## Default cases

### Valence = 0

SCG(a,0) is a default case. We are only allowed to use dots. For SCG, SSCG, PSCG and PSSCG this will be a sequence of length a+2, for CSCG, CSSCG, PCSCG and PCSSCG is it only 2 beacause we are not allowed to use 2 or more dots.

### Valence = 1

SCG(a,1) is a default case too. We are only allowed to use dots and sticks.

SCG(0,1) = 2: dot and empty

SCG(1,1) = 5: stick, 3 dots, 2 dots, 1 dot and empty

SCG(2,1) = 8: stick+dot, stick, 5 dots, 4 dots, 3 dots, 2 dots, 1 dot and empty

SCG(3,1) = 13: 2 sticks, stick+3 dots, stick+2 dots, stick+1 dot, stick, 8 dots, 7 dots ... 1 dot and empty

In general: SCG(n,1) = $$F_{n+4}$$ where $$F_{n}$$ is the nth fibonnacci number

For CSCG and variants is it equal to 3: stick, dot and empty.

Valence and variant

0 1

SCG, PSCG, SSCG, PSSCG

n+2 $$F_{n+4}$$
CSCG, PCSCG, CSSCG, PCSSCG 2 3

## Valence = 2

It becomes somewhat harder here.

SSCG(0,2) = 2

CSSCG(0,2) = 2

CSSCG(1,2) = 3

CSCG(0,2) = 4

SSCG(1,2) = 5

SCG(0,2) = 6

CSSCG(2,2) = 6

CSCG(1,2) = 7

CSSCG(3,2) = 9

CSCG(2,2) = 10

CSSCG(n,2) = 3n for n≥1

CSCG(n,2) = 3n+4 for n≥0

let's define some functions:

$$path_x(n)$$ for the maximal length of solving 2 path forests of length x at graph Gn. $$path_x(n) \approx f_{x-1}^2(n)$$

$$cycle_x(n)$$ for the maximal length of solving 2 cycles of length x at graph Gn. $$cycle_x(n) \approx f_{\omega+(x-3)}^2(n)$$

for SCG $$cycle_x(n) \approx f_{\omega+(x-1)}^2(n)$$

### SSCG(2,2)

G3: a triangle

G4: path forest of length 4

G5: path forest of length 3 + stick.

G6: path forest of length 3 + 3 dots

G7: path forest of length 3 + 2 dots

G8: path forest of length 3 + 1 dot

G9: path forest of length 3

G10: 5 sticks

G11: 4 sticks + 3 dots

G14: 4 sticks

G15: 3 sticks + 9 dots

G24: 3 sticks

G25: 2 sticks + 21 dots

G46: 2 sticks

G47: 1 stick + 45 dots

G92: 1 stick

G93: 93 dots

G185: 1 dot

G186: the empty graph

so SSCG(2,2) ≥ 184

### SSCG(3,2)

G4: 1 square

G5: 1 triangle + 1 stick

G6: 1 triangle + 3 dots

G9: 1 triangle

G10: path forest of length 10

G11: path forest of length 9 + 1 stick

G12: path forest of length 9 + 3 dots

G16: path forest of length 9

G17: 2 path forests of length 8 + 1 dot

G18: 2 path forests of length 8

$$SSCG(3,2) \approx f_7(f_7(18))$$

### SSCG(4,2)

G5: a pentagon

G6: a square + 1 stick

G7: a square + 3 dots

G10: a square

G11: 3 triangles + 1 stick

G12: 3 triangles + 3 dots

G15: 3 triangles

G16: 2 triangles + path forest of length 10

G$$f_7(f_7(18))$$: 2 triangles

G$$f_7(f_7(18))$$: 1 triangle + path forest of length $$f_7(f_7(18))$$

G$$f_{\omega}(f_7(f_7(18)))$$: 1 triangle

G$$f_{\omega}(f_7(f_7(18)))$$: path forest of length $$f_{\omega}(f_7(f_7(18)))$$

$$SSCG(4,2) \approx f_{\omega}(f_{\omega}(f_7(f_7(18))))$$

### SSCG(5,2)

G6: a hexagon

G7: a pentagon + 1 stick

G8: a pentagon + 3 dots

G11: a pentagon

G12: 3 squares

G13: 2 squares + 1 triangle + 1 stick

G14: 2 squares + 1 triangle + 3 dots

G17: 2 squares + 1 triangle

G18: 2 squares + path forest of length 10

$$SSCG(5,2) \approx f_{\omega+1}(f_{\omega+1}(f_7(f_7(18))))$$

### SSCG(6,2)

G7: a heptagon

G8: a hexagon + 1 stick

G9: a hexagon + 3 dots

G12: a hexagon

G13: 2 pentagons + 1 triangle

G14: 2 pentagons + path forest of length 4

G15: 2 pentagons + path forest of length 3 + stick

G16: 2 pentagons + path forest of length 3 + 3 dots

G19: 2 pentagons + path forest of length 3

G20: 2 pentagons + 5 sticks

G24: 2 pentagons + 4 sticks

G34: 2 pentagons + 3 sticks

G55: 2 pentagons + 2 sticks

G101: 2 pentagons + 1 stick

G195: 2 pentagons

$$SSCG(6,2) \approx f_{\omega+2}(f_{\omega+2}(196))$$

### SSCG(n,2)

General bound: $$SSCG(n+4,2) > f_{\omega+n}(SSCG(n+3,2))$$

### SCG(1,2)

G2: 2-cycle

G3: 3 loops

G4: 2 loops + stick

G5: 2 loops + 3 dots

G8: 2 loops

G9: 1 loop + path forest of length 8

G10: 1 loop + path forest of length 7 + stick

G11: 1 loop + path forest of length 7 + 3 dots

G14: 1 loop + path forest of length 7

G15: 1 loop + 2 path forests of length 6 + stick

$$SCG(1,2) \approx f_{\omega}(f_{5}^2(19))$$

### SCG(2,2)

G3: triangle

G4: 2 2-cycles

G5: 2-cycle + 3 loops

G6: 2-cycle + 2 loops + stick
G7: 2-cycle + 2 loops + 3 dots

G10: 2-cycle + 2 loops

G11: 2-cycle + 1 loop + path forest of length 8

$$SCG(2,2) \approx f_{\omega+1}(SCG(1,2))$$

### SCG(3,2)

G4: square

G5: triangle + 2 cycle

G6: triangle + 3 loops

G7: triangle + 2 loops + stick

G8: triangle + 2 loops + 3 dots

G11: triangle + 2 loops

$$SCG(3,2) \approx f_{\omega+2}(x)$$

### Table

0 1 2 3 n
SCG, PSCG 6 $$\approx f_{\omega}(f_{5}^2(19))$$ $$\approx f_{\omega+1}(x)$$ $$\approx f_{\omega+2}(x)$$ $$> f_{\omega+(n-1)}(x)$$
SSCG, PSSCG 2 5 ≥184 $$\approx f_7(f_7(18))$$ $$> f_{\omega+(n-4)}(x)$$
CSCG, PCSCG 4 7 10 14 3n+4
CSSCG, PCSSCG 2 3 6 9 3n

x: for any reasonable x

## Valence = 3

Known values:

0 1 2 3
SCG 6 > $$f_{\varepsilon_0}(x)$$
PSCG 6 > $$f_{\varepsilon_0}(x)$$
SSCG 2 5 $$3*2^{3*2^{95}}-8$$
PSSCG 2 5 $$3*2^{3*2^{95}}-8$$
CSCG 4 > $$f_{\varepsilon_0}(x)$$
PCSCG 4 > $$f_{\varepsilon_0}(x)$$
CSSCG 2 3 8 >> $$TREE(x)$$
PCSSCG 2 3 8

x: for any reasonable x.

## Valence = 4

### CSCG(0,4)

G1: double loop

G2: double edge

G3: loop on 2 edges

G4: loop on 3-path

G5: loop on 2-path

G6: loop on edge

G7: loop

G8: tree with two vertices of valence 4

G9: vertex connected to four 2-paths

From G9 on we can have a vertex with four edges, each edge connected to a different tree. So we will write it as     ( a, b, c, d ) where a,b,c,d are the four trees.

G9: ( edge, edge, edge, edge )

G10: ( 0, edge, 2 edges, 2 edges )

G11: ( 0, 2-path, 2-path, 2 edges )

G12: ( 0, 2-path, 2-path, 3-path )

G13: ( 0, edge, 5-path, 2 edges )

G14: ( 0, edge, 4-path, 2 2-paths )

Now only look at tree on the left. It will have one valence 3 node, a vertices between this node and valence 4 node, and b-path and c-path coming from it. This will be denoted ( a,b,c ).

G14: ( 0, 2, 2 )

G15: ( 0, 1, 4 )

G16-18: ( 2, 1, 3 ) - ( 1, 1, 3 ) - ( 0, 1, 3 )

G19-25: ( 6, 1, 2 ) - ( 5, 1, 2 ) ... ( 1, 1, 2 ) - ( 0, 1, 2 )

G26-40: ( 14, 1, 1 ) - ( 13, 1, 1 ) ... ( 1, 1, 1 ) - ( 0, 1, 1 )

Back to the whole graph:
G40: ( 0, edge, 4-path, 2 edges )

G41: ( 0, edge, 4-path, 31-path )

G70: ( 0, edge, 4-path, edge )

G71: ( 0, edge, 3-path, ( 0,31,31 ) )

Again:

G71: ( 0,31,31 )

G72: ( 0,30,33 )

G73-75: ( 2,30,32 ) ... ( 0,30,32 )

G76-82: ( 6,30,31 ) ... ( 0,30,31 )

G83-97: ( 14,30,30 ) ... ( 0,30,30 )

G98: ( 0,29,60 )

G$$2^{31}$$: ( 0,29,29 )

G$$2^{31}$$: ( 0,28,$$2^{31}$$)

G$$2^{2^{31}}$$: ( 0,27,$$2^{2^{31}}$$)

G$$2^{2^{2^{31}}}$$: ( 0,26,$$2^{2^{2^{31}}}$$)

G$$2 \uparrow\uparrow 31$$: ( 0, edge, 3-path, edge )

G$$2 \uparrow\uparrow 31$$: ( 0, edge, 2-path, ( 0, $$2 \uparrow\uparrow 31$$, $$2 \uparrow\uparrow 31$$ ) )

G$$2 \uparrow^{3} 4$$: ( 0, edge, 2-path, edge )

G$$2 \uparrow^{3} 5$$: ( 0, edge, edge, edge )

G$$2 \uparrow^{3} 5$$: ( 0, 0,$$2 \uparrow^{3} 5$$-path , edge )

G$$2 \uparrow^{3} 2 \uparrow^{3} 5$$: K1,4

So CSCG(0,4) >> $$2 \uparrow^{3} 2 \uparrow^{3} 5$$

### SCG(0,4)

SCG(0,4) is very probably in $$\varepsilon_0$$ territory or beyond.

### SSCG(0,4), SSCG(1,4) and SSCG(2,4)

SSCG(0,n) = Minor(0) = 2

SSCG(1,n) = Minor(1) = 5

SSCG(2,n) = Minor(2) = SSCG(2)

## Valence = 5

### CSCG(0,5)

G1: double loop

G2: double edge

G3: loop on 2 edges

G4: loop on 3-path

G5: loop on 2-path

G6: loop on edge

G7: loop

G8: K1,5 with 2 additional edges

G9: K1,5 with a 3-path

G10: K1,5 with a 2-path

G11: K1,5 with a edge

G12: K1,5

G13: ( 2 edges, 2 edges, 2 edges, 2 edges )

G14: ( edge, 2 edges, 3 edges, 3 edges )

G15: ( edge, 2 edges, 3 edges, 3 edges )

G16: ( edge, 2-path+edge, 2-path+edge, 3 edges )

G17: ( edge, 2-path+edge, 2-path+edge, 3-path+edge )

G18: ( edge, 2 edges, 5-path+edge, 3 edges )

G19: ( edge, 2 edges, 4-path+edge, 2 2-paths+edge )

etc.

So CSCG(0,5) >> $$2 \uparrow^{4} 2 \uparrow^{4} 5$$