I'm trying to understand the SSCG($k$) function, but I don't understand few things…
I'm understand the idea of graph minor, but I don't understand the meaning of $k$ (what is a length of a graph?).
But I don't understand what this functions gives you as a result (I know it's set of graphs, but I don't understand what common to those graphs)
I try to figure out what are the $SSCG(0)=2$ and $SSCG(1)=5$.
If someone here can tell me what are they (those sets of graphs) – I think it will be much more clear to me, and explain to me at simple language the idea of the $SSCG$ function (with some examples of which graphs are include at k=1 or k=2 for example…).
Thank you!
P.S. – I'm talking about the $SSCG$ and not the $SCG$ 🙂
Best Answer
The function $SSCG(k)$ does not give a set of graphs, it is a function that takes in a natural number $k$, and returns a natural number $SSCG(k)$ (we now explain how).
A graph is said to be a simple subcubic graph if it is a simple graph in which every vertex has degree at most $3$. To explain $SSCG$, we introduce our own new definition. Let $S = (G_1, G_2, \dots, G_n)$ be a sequence of graphs. The length of the sequence is the number of graphs in it. We call the sequence $k$-valid if it satisfies the following things:
By a version of the Robertson-Seymour Theorem, there is a finite upper bound on the length of a $k$-valid sequence. So we define $SSCG(k)$ to be the maximum length among all $k$-valid sequences. Note that, for whatever reason, the empty graph $\emptyset$ with no vertices is counted as a graph.
To understand what's going on here, let's calculate $SSCG(0)$ and $SSCG(1)$ explicitly.
To find $SSCG(0)$, it suffices to find all $0$-valid sequences. The first graph $G_1$ of a $0$-valid sequence has at most $1+0 = 1$ vertices. Since $G_1$ is simple, it must either be the empty graph, or $K_1$. The empty graph is a minor of every graph, so no graph can come after it in a valid sequence. So the sequence with $G_1=\emptyset$ has length $1$. But what if $G_1=K_1$? Note that $K_1$ is a minor of every graph that has at least one vertex, so the only graph that can come after $K_1$ in a valid sequence is the empty graph, and we get the sequence $(G_1, G_2) = (K_1, \emptyset)$ with length $2$. This exhausts all possibilities, so we see that the max length of a $0$-valid sequence is $2$, so $SSCG(0) = 2$.
Now let's try $SSCG(1)$. By requirement 2 for a $1$-valid sequence, we know that the first graph $G_1$ of any $1$-valid sequence has at most $1+1 = 2$ vertices. So our only possibilities are $\emptyset, K_1, K_2$ and $I_2$ (where we let $I_k$ be the graph with $k$ vertices and no edges). By the previous argument, we know any sequence starting with $\emptyset$ or $K_1$ has length at most $2$. So let's consider a sequence starting with $G_1 = I_2$. Since $I_2$ is a minor of any graph with $2$ or more vertices, we must have $|V(G_2)| < 2$, so $G_2 = K_1$ or $G_2 = \emptyset$ and we see that any sequence starting with $I_2$, such as $(I_2, K_1, \emptyset)$ has length at most $3$. Finally, consider the $1$-valid sequences that start with $G_1 = K_2$. The graph $K_2$ is a minor of any graph that has at least one edge, so $G_2$ cannot have any edges (nor can $G_i$ for any other $i>1$). We know that $G_2$ must have at most $2+1 = 3$ vertices, so $G_2 \in \{K_1, I_2, I_3\}$. We have already shown that if our sequence has $I_2$, we can only get another $2$ graphs in it ($K_1$ and $\emptyset$), so we try $G_2 = I_3$. Because $I_3$ is a minor of every graph with at least $3$ vertices, we have that $G_3$ has at most $2$ vertices and no edges. The best we can do is to set $G_3 = I_2$. Using the previous arguments, this gives us a sequence $(K_2, I_3, I_2, K_1, \emptyset)$ of length $5$, and we can't do better. So $SSCG(1) = 5$.
I found this page a lot more useful than the wikipedia page for understanding this.