FANDOM


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

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.