10,029 Pages

# Hyp cos

My favorite wikis
• ## TREE into SCG without diamond graph minor

February 14, 2018 by Hyp cos

Define SCGD(n) as the maximal length of sequence of graphs (G1, G2, ..., Gm) such that

1. The degree of every vertex of every Gi is at most 3.
2. For all i, Gi has at most n+i vertices.
3. For all i < j, Gi is not graph minor of Gj.
4. For all i, the diamond graph (K4 with one edge removal) is not graph minor of Gi.

SCGD function grows much slower than SCG function, but not slower than TREE function.

Here I'll show encoding of n-colored trees (the objects of TREE function) into subcubic graphs without diamond graph as minor (the objects of SCGD function).

The root (colored m) with k children is encoded into(if it has less than 2 children, still let k=2)

A non-root node (colored m) with k children is encoded into(if it has less than 2 children, still let k=2)

To deco…

• ## Catching hierarchy fails

January 16, 2018 by Hyp cos

Catching hierarchy fails beyond $$C_1(\Omega)$$ (or $$C_{\Omega_2}(\Omega)$$).

Recall the definition:

1. $$C_\pi(0)=\psi_\pi(\Omega_\omega)$$.
2. If $$C_\pi(\alpha)=\psi_\pi(\beta)$$, then $$C_\pi(\alpha+1)=\psi_\pi(\gamma)$$ where $$\psi(\gamma)$$ is the least ordinal that $$g_{\psi(\gamma)}$$ is comparable to $$f_{\psi(\gamma)}$$ and $$\gamma>\beta$$, and both $$\psi_\pi(\beta)$$ and $$\psi_\pi(\gamma)$$ are full-simplified.
3. $$\pi$$ is the diagonalizer of $$C_\pi()$$ function.
4. For limit $$\alpha$$, $$C_\pi(\alpha)[n]=C_\pi(\alpha[n])$$.

But what's $$C_1(\Omega)$$? The $$\Omega$$ works as the diagonalizer of C(), which is outside, so $$C_1(\Omega)$$ refers to the outside C().

1. If $$\beta$$ is a successor ordinal, then let $$\beta=\gamma+1=\lambda[n_1]_S[n_2]_S\cdots[n_k]_S[]_S$$ where $$n_k>0$$ ($$k\ge0$$). $$\alpha Read more > • ## Are these functions well-defined? October 21, 2017 by Hyp cos Here are two extensions of subcubic graph function, but I don't know whether they are well-defined. Graph A is called a graph minor of graph B if A can be obtained from B by these 3 operations: 1. Delete an edge; 2. Delete an isolated vertex; 3. Edge contraction - for an edge ab, delete this edge, and replace vertex a and b by one vertex connecting to the edges which a or b formerly connect to. (If a and b are linked by another edge, it will become a self-loop after edge contraction.) Graph A is called a topological minor of graph B if A can be obtained from B by these 3 operations: 1. Delete an edge; 2. Delete an isolated vertex; 3. Smoothing - for a (degree=2) vertex a which links to b and c, delete vertex a, and replace edge ab and ac by one edge bc. For (unlabeled) subcubic graphs, graph m… Read more > • ## General fundamental sequences for OCFs October 2, 2017 by Hyp cos In definitions of some ordinal collapsing functions (OCFs), there is always a series of \(C_n(\text{some arguments})$$ sets. $$C_0(\text{something})$$ may contains some argument in the "something", and may contains a "large" ordinal for collapsing; $$C_{n+1}(\text{something})$$ is usually obtained from $$C_n(\text{something})$$ by applying some operations with some limitations (avoiding "loop" definition); and $$C(\text{something})$$ is the union of all $$C_n(\text{something})$$. By this structure, we can define general fundamental sequences for OCFs.

Here this "general" definition works on the notation using a weakly compact cardinal. The definition of the ordinal notation is:

Let $$K$$ denote the weakly compact cardinal, $$\Omega_0=0$$ and…