Lecture
In mathematics, a simple subcubic graph (SSCG) — is a finite simple graph in which every vertex has degree at most three. Suppose we have a sequence of simple subcubic graphs 
, 
, ... such that each graph 
has at most 
vertices (for some integer k) and for no 
is homeomorphically embeddable into (i.e. is a minor of) 
.
The Robertson–Seymour theorem proves that subcubic graphs (simple or not) are well-founded under homeomorphic embeddability, which implies that such a sequence cannot be infinite. Then, applying König's lemma to the tree of such sequences under extension, for each value of 
there exists a sequence of maximal length. The function SSCG(k) denotes this length for simple subcubic graphs. The function SCG(k) denotes this length for (general) subcubic graphs.
A sequence of subcubic graphs. The n-th graph in the sequence contains at most n+3 vertices, and no graph can be homeomorphically embedded into any later graph in the sequence. SSCG(3) is defined as the maximum possible length of such a sequence.
Harvey Friedman defined two functions: SSCG and SCG. He defined SSCG(k) as the largest integer 
satisfying the following conditions:
There is a sequence G1,…,Gn of simple subcubic graphs such that each has at most vertices and for no is homeomorphically embeddable into .
The first few terms of the sequence:
SSCG(0)=2,
SSCG(1)=5,
and
SSCG(2)= 
[ 2 ]
It has been shown that the next term SSCG(3) is greater than TREE(3).
Friedman showed that SSCG(13) is greater than the halting time of any Turing machine for which halting can be proved in Π1
1-CA 0 with at most 2↑↑2000 symbols, where ↑↑ denotes tetration. He does this using the same idea as in the case of 
.
He also notes that is completely negligible compared to SSCG(13).
Later Friedman realized that there is no reason to require «simplicity» for subcubic graphs. He relaxes this condition and defines SCG(k) as the largest n satisfying:
There is a sequence 
of subcubic graphs such that each has at most vertices and for no is homeomorphically embeddable into G_j .
The first term of the sequence is SCG(0)=6 
, while the next term SCG(1) 
is greater than Graham's number. Moreover, SCG(3) 
is greater than 
.
Adam P. Goucher asserts that there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes: «It is obvious that SCG(n)≥SSCG(n), but I can also prove SSCG(4n+3)≥SCG(n)".
Comments