FANDOM


I've obtained something about subcubic graph numbers. First, here are ordinal level of some graphs. A graph with larger ordinal isn't homeomorphically embeddable into any graph with smaller ordinal.

SCG ordinal levels

There're many ways to order the graphs, and here is one.

Up to \(\varepsilon_0\)

It's a little different from tree(n) ordinal levels up to \(\varepsilon_0\) because we haven't "root vertex" in SCG.

A dot has level 0, and then

SCG 01

When we go through all the forests, we get a limit of \(\varepsilon_0\).

The ordinal level of a connected graph is related to FGH. If we get a connected graph G at level \(\alpha\) in SCG(n) sequence, and we cannot draw any graph at level above \(\alpha\) (because of graph minors), and the max-vertex-number (or index+n) is m at this step, then the sequence end up at max-vertex-number \(f_\alpha(m)\). For a disconnected graph, we treat it as some connected graphs: G1, G2, ... Gk at level \(\alpha_1,\alpha_2,\cdots,\alpha_k\) respectively, then the sequence end up at max-vertex-number \(f_{\alpha_1}(f_{\alpha_2}(\cdots f_{\alpha_k}(m)))\).

But this is just an approximation, not exact value. For example, when we get a stick (i.e. two dots with one edge connecting them) at max-vertex-number m, we get m+1 dots at max-vertex-number m+1, and the sequence ends at max-vertex-number 2m+2 (larger than \(f_1(m)\)). That makes it slightly stronger. However, when we get a level \(\omega^{\omega^\omega}\) graph at max-vertex-number m, we get a level \(\omega^{\omega^{\lfloor m/3-1\rfloor}}\) rather than \(\omega^{\omega^m}\) graph (plus a dot or a stick) at max-vertex-number m+1. That makes it slightly weaker.

From \(\varepsilon_0\) to \(\varepsilon_1\)

Here the trees work like in tree(n) (up to \(\varepsilon_0\)), because there are loops to act as roots in tree(n).

SCG 02

Using forests and self-loops, we get \(\varepsilon_1\).

From \(\varepsilon_1\) to SVO

In this section, we're going to the limit of tree(n), but it's just beginning of SCG(n).

SCG 03

Using forests and no-fused cycles, we get \(\vartheta(\Omega^\omega)\), or SVO.

From SVO to \(\vartheta(\Omega^{\omega^2})\)

Now I begin using "rooted graphs". We see a graph with high level as a root, and graphs with lower level connect to it. e.g. we see a self-loop as the root for all binary trees.

SCG 04

  • Note: The graph for \(\vartheta(\Omega^\omega\vartheta(\Omega^\omega3))\) is actually planar.

Using cycles "fused with" at most double edge we get \(\vartheta(\Omega^{\omega^2})\).

From \(\vartheta(\Omega^{\omega^2})\) to \(\vartheta(\Omega^{\Omega^{\Omega^\omega}})\)

Remember that this is just one way to order graphs. In SCG(n) for certain n, we don't need to follow this way. Also, the "complexity" of an ordinal expression and of a graph are not parallel. Sometimes we can use a more simple graph to present a complex ordinal, but sometimes we need a more complex graph to present a simple ordinal. For example, the graph for \(\theta(\Omega^\Omega,1)\) is more simple than the graph for \(\vartheta(\Omega^\Omega)\).

SCG 05

Emm, how to explain those graphs?

For rooted graphs, all those graphs below \(\vartheta(\Omega^{\Omega^{\Omega^\omega}})\) have "cycle-fusing-depth" 2. That means, if we go from the root, we may find a cycle C1. And there may be cycles C2(1), C2(2), ... C2(m) fused to C1. But for any C2(k), there's no such cycle C3 that is fused to C2(k) but isn't C1. And all the cycle-fusing are exactly using 2 vertex and the one edge between them.

For normal graphs, it's not so clear. If we start from somewhere of a graph, we may get "cycle-fusing-depth" 3. e.g. graph for \(\vartheta(\Omega^{\omega2})\), \(\vartheta(\Omega^{\omega^22})\) and \(\vartheta(\Omega^{\Omega2})\).

From \(\vartheta(\Omega^{\Omega^{\Omega^\omega}})\) to BHO

Then we go to "cycle-fusing-depth" 3 and more.

SCG 06

Now think of this: pick a no root tree, then change every vertex into a ring, for two vertices connected by an edge, they'll be changed into two rings and they are "fused by one edge" (i.e. the intersection of the two rings is two vertices and one edge connecting them). But a ring can be arbitrary large. Now we get some "cycle-one-edge-fusing-trees". Then the set of forests made from them (you can use different cycle-one-edge-fusing-trees) reaches BHO.

From BHO to \(\vartheta(\Omega_2)\)

Pick a no root tree, then change every vertex into a ring, for two vertices connected by an edge, they'll be changed into two fused rings. A ring can be arbitrary large and the fusing can be a long path, even including cycles. All these can lead to \(\vartheta(\Gamma_{\Omega+1})=\vartheta(\Omega_2)\).

SCG 07

Then \(K_4\) is the least term above that. It has level \(\vartheta(\Omega_2)\).

Beyond!

I've an idea to go beyond \(\vartheta(\Omega_2)\). First, let's define something.

  • Suppose G is a planar graph. And there're some ways to draw G in a plane that there're no such edges a and b that \(a\cap b\) is not fully made up of vertices of G. Those ways are called planar drawing of G. A graph can have many planar drawings.
  • For one planar drawing of G, a cycle is standard iff there's no cycle that has some vertices inside it.
  • Create a new graph H from a planar drawing of G. There exists a bijection f that f maps standard cycles of G into vertices of H, and, standard cycles a and b of G are fused iff f(a) and f(b) are connected by an edge. This H is called a cycle-linking-graph (CLG) of G. A planar graph can have many CLGs.
  • A planar graph G has cycle level 0 iff G is an empty graph. G has cycle level n+1 iff all CLGs of G have a minimum of cycle level n.

Notes:

  • For planar graph G, all the CLGs of G are simple graph.
  • For planar subcubic graph G, all the standard cycles of CLGs of G are "triangles".
  • For planar subcubic graph G, all the CLGs of CLGs of G are subcubic graph.
  • Forests have cycle level 1.

For example,

SCG 08

Then we can group planar subcubic graphs into cycle level 1, cycle level 2, cycle level 3, and so on. All those can lead to the limit of planar subcubic graph. Then \(K_{3,3}\) will be the least term above that.

But I'm still not sure about the full strength of PSCG(n), let alone SCG(n) - what's more, I don't know how SCG(n) goes on in non-planar graphs.

SCG(1)

If we really see graphs as ordinals, then limit ordinals have fundamental sequences. However, the fundamental sequences sometimes grow too slow to match FSes of ordinals in normal notation. If SCG(n) has growth rate \(\beta\), we cannot say \(SCG(n)\approx f_\beta(n)\) for small n.

The FS of graph ordinals can be defined as follows:

\(\alpha[n]\) is the greatest ordinal below \(\alpha\) that has n vertices.

For example, \(\varepsilon_0[1]=0,\varepsilon_0[2]=1,\varepsilon_0[3]=2,\varepsilon_0[4]=\omega,\varepsilon_0[5]=\omega+1,\varepsilon_0[6]=\omega2,\varepsilon_0[7]=\omega^\omega,\) \(\varepsilon_0[8]=\omega^\omega+\omega,\varepsilon_0[9]=\omega^{\omega+1},\varepsilon_0[10]=\omega^{\omega^\omega},\varepsilon_0[16]=\omega^{\omega^{\omega^\omega}},\varepsilon_0[22]=\omega^{\omega^{\omega^{\omega^\omega}}},\) \(\varepsilon_0[34]=\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}},\varepsilon_0[46]=\omega^{\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}}\). While in normal ordinal notation we need only \(\varepsilon_0[7]\) to get \(\omega^{\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}}\).

With those ordinals and those FSes, we can build a "graph hierarchy" like FGH. for large enough numbers, graph hierarchy can be lower-bounded by FGH. e.g. f_{e(0)}(2^^15) is smaller than f'_{e(0)}(2^^16) (here f' means graph hierarchy). However, for small numbers, we need special graphs, and there will even be graphs that don't follow the order but follow the graph minor - there will be an improvement.

So, here comes my bound for SCG(1).

Beginning

The max-vertex-number is the most number that we can use that many vertices in this graph. Sometimes the max-vertex-number decrease but the index remains, that means I start working on some parts of the unconnected graph, and other parts of it remain the same.

SCG 09

Note: The 19th graph doesn't follow my order before, but it's still available. That can improve a little.

After the 82nd graph, the "Y" reduces in Goucher's way in SSCG(2). At (3*2^(3*2^95)+72)th graph the "Y" reduces to empty. Now the number gets large enough.

Levels

Here are some graph ordinals we may use.

SCG 10

The first three graphs mean that m vertices get \(\omega\times\lfloor m/2-1\rfloor\). At the (3*2^(3*2^95)+73)th graph the "H" reduces, so there're 3*2^(3*2^95)+1 vertices available in graph at level below \(\omega^2\). Now we change this number into 2^(3*2^95) - about a third of the original one. If this number is used in FGH, it's small enough to flatten the difference between growth rate of FGH and graph hierarchy (and it's even weaker).

Result

So we get SCG(1) > \(f_{\varepsilon_22}(f_{\varepsilon_02}(f_{\varepsilon_0+1}(f_{\varepsilon_0}(f_{\omega^\omega+1}(f_{\omega^5+\omega^2+\omega}(f_{\omega^23+1}(f_{\omega^22+1}(f_{\omega^2+\omega3+1}(f_{\omega^2+1}(f_{\omega^2}(2^{3\times2^{95}})))))))))))\).

SCG(2)

My sequence for SCG(2) is quite simple. First graph is the level \(\vartheta(\Omega^\omega)+1\) graph, then second graph is two triple-edges. Then a triple-edge reduces in my way in SCG(1), while the other remains the same. Now we still have a triple-edge at level SVO. Then it reduces in normal way.

So my result is SCG(2) > \(f_{\vartheta(\Omega^\omega)}(f_{\varepsilon_22}(f_{\varepsilon_02}(f_{\varepsilon_0+1}(f_{\varepsilon_0}(f_{\omega^\omega+1}(f_{\omega^5+\omega^2+\omega}(f_{\omega^23+1}(f_{\omega^22+1}(f_{\omega^2+\omega3+1}(f_{\omega^2+1}(f_{\omega^2}(2^{3\times2^{95}}))))))))))))\). This bound is too small comparing to TREE(3). I don't know which one is larger, SCG(2) or TREE(3).

SSCG(3)

My ordering for SSCG is not the same as SCG.

Beginning

The max-vertex-number is the most number that we can use that many vertices in this graph. Sometimes the max-vertex-number decrease but the index remains, that means I start working on some parts of the unconnected graph, and other parts of it remain the same.

SCG 11

It's too complex to show the connected part of the graph on a table, so I stop here. But we can go further if I can show next graphs more clear.

Levels

We don't have self-loops or multiple edges in SSCG, but this just affects a little. To maximize the length of my sequence, some graphs may not follow the normal ordering.

SCG 12

Result

So I get a "weak" lower bound for SSCG(3). It's SSCG(3) > \(f_{\vartheta(\Omega^{\omega^2}+\vartheta(\Omega^{\omega^2}2)^{\omega^2}+1)+1}(f_{\vartheta(\Omega^{\omega^2}+\Omega^62+\Omega^4\omega+\Omega^4+\Omega^3+\Omega^2+\Omega+1,1)}(f_{\vartheta(\Omega^{\omega^2}+2)+\omega}(f_{\vartheta(\Omega^{\omega^2}+1)+\omega}(n))))\) for large n (above \(\vartheta(\Omega^{\omega^2},\varphi(\omega^24,0,0))\)) FGH level but below \(\vartheta(\Omega^{\omega^2},\varphi(\omega^24,3,0))\)) FGH level.

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.