{{infobox function

|image=Graph minor example.svg

|growthrate=>* \(\Pi^1_1\)-\(\text{CA}_0\)

|notation=\(\text{SCG}(n)\)

|author=Harvey Friedman

|year=2006}}

The **subcubic graph numbers** are the outputs of a fast-growing combinatorial function.^{[1]} They were devised by Harvey Friedman, who showed that it eventually dominates every recursive function provably total in the theory of \(\Pi^1_1\)-\(\text{CA}_0\), and is itself provably total in the theory of Template:Pi11.

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.

## Definition Edit

A **subcubic graph** is a finite graph in which each vertex has a valence of at most three. (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 a graph minor of *B* iff we can derive *A* from the following process: start with *B*, remove vertices and edges, and contract edges.^{[2]} 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).

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 Edit

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 Template:U.

- \(\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 proved 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,000}2 symbols in \(\Pi^1_1\)-\(\text{CA}_0\). It is therefore far larger than TREE(3).

**SCG(n) **is computable,therefore it is naturaly surpassed by \(\Sigma(n)\) for a not very large n.

## Matrix interpretation Edit

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 Edit

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. Adam P. Goucher has shown that SSCG(2) << TREE(3) << SSCG(3).^{[3]} Moreover, 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).

SCG(n) and SSCG(n) have comparable growth rates: Goucher proved that \(SSCG(4n+3) \geq SCG(n)\).^{[4]}

===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}}\)

## Sources Edit

- ↑ Harvey Friedman, FOM 279:Subcubic Graph Numbers/restated
- ↑ Technically a topological minor, but topological minors and graph minors are equivalent for subcubic graphs.
- ↑ Adam Goucher, Graph minors
- ↑ Adam Goucher, TREE(3) and impartial games (see comment)