The **subcubic graph numbers** are the outputs of a fast-growing combinatorial function.^{[1]} devised by Harvey Friedman.

One output of the sequence, **SCG(13)**, is a subject of extensive research. It is known to surpass TREE(3), a number that arises from a related sequence. Friedman showed that SCG(13) is larger than the halting time of any Turing machine at the blank tape, that can be proved to halt in at most \(2^{2000}\) symbols in \(\Pi^1_1\)-\(\text{CA}_0\).^{[1]}

## Definition[]

A **subcubic graph** is a finite graph in which each vertex has a valence of at most three, i.e. no vertex is connected to more than three edges. (For the sake of this article, subcubic graphs are allowed to be multigraphs, and are not required to be connected.) We also define the **graph minor** relation as follows: *A* is said to be a graph minor of *B* if we can derive *A* from the following process: start with *B*, remove vertices and edges, and contract edges.^{[note 1]} An example of a graph minor derivation is shown in the infobox of this article.

Given an integer *k*, suppose we have a sequence of subcubic graphs G_{1}, G_{2}, ... such that each graph G_{i} has at most *i* + *k* vertices and for no *i* < *j* is G_{i} homeomorphically embeddable into G_{j} (i.e. is a graph minor). This definition is analogous to the weak tree function, where the graph is a tree with at most *i* + *k* vertices.

The Robertson-Seymour theorem proves that subcubic graphs are well-quasi-ordered by homeomorphic embeddability, implying such a sequence cannot be infinite. So, for each value of *k*, there is a sequence with maximal length. We denote this maximal length using SCG(*k*).

## Specific values[]

It is possible to show that SCG(0) = 6. The first graph is one vertex with a loop,

the second is two vertices connected by a single edge, and the next four graphs consist of 3, 2, 1, and 0 unconnected vertices. All maximal sequences will peak and decline this way.

The following bounds have been claimed by Googology Wiki user Hyp cos.^{[2]}

- \(\text{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}(3\times2^{3\times2^{95}})))))))))))\).

- \(\text{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}(3\times2^{3\times2^{95}}))))))))))))\)

These bounds use a non-standard choice of fundamental sequences for ordinals — by using a particular, highly complex bijection between ordinals and small graphs, which we will denote here by \(f\), we define \(\alpha[n]=\max\{\beta: \beta<\alpha\text{ and } f(\beta)\text{ is a graph with }\leq n\text{ vertices}\}\).

Since the graph indices start at one, it is also valid to say that SCG(-1) = 1, consisting only of the empty graph.

Friedman stated that **SCG(13)** is greater than the halting time of any Turing machine such that it can be proven to halt in at most 2 ↑↑ 2,000^{[note 2]} symbols in \(\Pi^1_1\)-\(\text{CA}_0\).^{[1]} It is therefore far larger than TREE(3).

**SCG(n)** is computable, therefore it is naturally surpassed by \(\Sigma(n)\) for some n.

## Matrix interpretation[]

An alternate way of describing the SCG function is as follows. Define an *incidence matrix* as a matrix with entries in {0, 1, 2} where each column sums to exactly 2 and each row sums to at most 3. Given a nonnegative integer *k*, we construct a sequence of *n* incidence matrices M_{1}, M_{2}, ..., M_{n} such that each matrix M_{i} has at most *i* + *k* rows, and no matrix can be changed into an earlier one by repeated applications of any of the following processes:

- Reordering rows or columns.
- Deleting columns.
- Deleting rows, then deleting all columns that do not sum to 2.
- Take two rows
*A*and*B*such that*A*+*B*contains a 2 in position*i*for some*i*. Remove*A*and*B*, append*A*+*B*to the matrix, and finally remove column*i*.

SCG(*k*), then, is the largest possible value of *n*.

## Simple subcubic graph numbers[]

If we require the subcubic graphs to be simple (i.e. no loops or multiple edges), we get the **simple subcubic graph numbers**, denoted SSCG. Although this community believed that Adam P. Goucher has shown that SSCG(2) << TREE(3) << SSCG(3) in his article^{[4]}, it just contains a rough estimation without a proof. Moreover, the community believed that he has shown that even TREE^{n}(3) for even very large *n* (for example n=TREE(3)) does not compete at all with SSCG(3). Later, he proved that TREE(3) < SSCG(3) in a different blog post.^{[5]}

Goucher claimed that he had proved that \(\text{SSCG}(4n+3) \geq \text{SCG}(n)\) in his comment^{[6]} and hence SCG(n) and SSCG(n) have comparable growth rates. He later proved it in a later blog post.^{[5]}

Similar to the fact that there are many wrong claims on "the actual results on TREE with proofs", there are many statements on SCG which are said to be proved but do not have actual proofs. See also issues on analysis of TREE.

### Values and bounds[]

- SSCG(0) = 2
- SSCG(1) = 5
- SSCG(2) \(\geq 3 \cdot 2^{3 \cdot 2^{95}}-8 \approx 10^{3.5775 \cdot 10^{28}}\) (it is possible, that sequence of subcubic graphs that Adam P. Goucher has shown is really optimal, but it remains unproven.)
- SSCG(3) >
^{[7]}

## Footnotes[]

- ↑ Technically a topological minor, but topological minors and graph minors are equivalent for subcubic graphs.
- ↑ Friedman uses the notation 2
^{[n]}to denote an exponential stack of 2's of height*n*.^{[3]}

## Sources[]

- ↑
^{1.0}^{1.1}^{1.2}Harvey Friedman, FOM 279:Subcubic Graph Numbers/restated - ↑ User blog:Hyp cos/SCG(n) and some related
- ↑ https://cs.nyu.edu/pipermail/fom/2006-March/010233.html
- ↑ Adam Goucher, Graph minors
- ↑
^{5.0}^{5.1}Adam Goucher, Fast-Growing Functions Revisited - ↑ Adam Goucher, TREE(3) and impartial games (see comment)
- ↑ https://www.palomar.edu/math/wp-content/uploads/sites/134/2017/12/2.E-Finitely-big-numbers-KEY.pdf

## See also[]

**subcubic graph number**SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · Greedy clique sequence · Bop-counting function

TREE sequence TREE(3) · Greedy clique sequence · Friedman's finite trees · **Subcubic graph number** SCG(13) · Graham's number G(64)