Friedman's SSCG function

Friedman's SSCG function is a mathematical function defined by Harvey Friedman. It is defined by $SSCG (k)$ as the largest integer $n$ satisfying the following:

There is a sequence

G_{1}, \dots, G_{n}

of simple subcubic graphs such that each

G_{i}

has at most

i + k

vertices and for no

i < j

is

G_{i}

homeomorphically embeddable into

G_{j}

.

Later, Friedman defined the more general subcubic graphs $SCG (k)$ .

Background

In mathematics, especially graph theory, a simple subcubic graph (SSCG) is a finite simple graph in which each vertex has a degree of at most three. Suppose we have a sequence of simple subcubic graphs $G_{1}$ , $G_{2}$ , ... such that each graph $G_{i}$ has at most $i + k$ vertices (for some integer $k$ ) and for no $i < j$ is $G_{i}$ homeomorphically embeddable into (i.e. is a graph minor of) $G_{j}$ .

The Robertson–Seymour theorem proves that subcubic graphs (simple or not) are well-quasi-ordered by homeomorphic embeddability, implying such a sequence cannot be infinite. Then, by applying Kőnig's lemma on the tree of such sequences under extension, for each value of $k$ there is a sequence with maximal length. The function $SSCG (k)$ denotes that length for simple subcubic graphs. The function $SCG (k)$ denotes that length for (general) subcubic graphs.

Harvey Friedman defined two functions: SSCG and SCG.

SSCG function

Friedman defined $SSCG (k)$ as the largest integer $n$ satisfying the following:^[1]

There is a sequence

G_{1}, \dots, G_{n}

of simple subcubic graphs such that each

G_{i}

has at most

i + k

vertices and for no

i < j

is

G_{i}

homeomorphically embeddable into

G_{j}

.

The first few terms of the sequence are

SSCG (0) = 2,

SSCG (1) = 5,

and

SSCG (2) = 3 \cdot 2^{3 \cdot 2^{95}} - 8 = 3 \cdot 2^{118 842 243 771 396 506 390 315 925 504} - 8

\approx 3.241 704 229 \cdot 1 0^{35 775 080 127 201 286 522 908 640 065}

\approx 1 0^{3.5775 \cdot 1 0^{28}} .

^[2]

It has been shown that the next term, $SSCG (3)$ , is greater than TREE(3).^[3] Friedman showed that $SSCG (13)$ is greater than the halting time of any Turing machine that can be proved to halt in Π¹
₁-CA₀ with at most $2 ↑ ↑ 2000$ ^[a] symbols, and that it cannot be proved to exist in that theory with less than $2 ↑ ↑ 1000$ symbols, where $↑ ↑$ denotes tetration. He does this using a similar idea as with a similar statement he proved about $TREE (3)$ .^[1]

SCG function

Later, Friedman realized there was no good reason for imposing "simple" on subcubic graphs. He relaxes the condition and defines $SCG (k)$ as the largest $n$ satisfying:^[4]

There is a sequence

G_{1}, \dots, G_{n}

of subcubic graphs such that each

G_{i}

has at most

i + k

vertices and for no

i < j

is

G_{i}

homeomorphically embeddable into

G_{j}

.

The first term of the sequence is $SCG (0) = 6$ , while the next term $SCG (1)$ is bigger than Graham's number. Furthermore, $SCG (3)$ is bigger than ${TREE}^{TREE (3)} (3)$ .^[3]

Adam P. Goucher claims there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It's clear that $SCG (n) \geq SSCG (n)$ , but I can also prove $SSCG (4 n + 3) \geq SCG (n)$ ".^[5]

Notes

^{^ a} Friedman actually writes this as 2^[2000], which denotes an exponential stack of 2's of height 2000 using his notation.^[6]

References

1 2 Friedman, Harvey. "[FOM] 274:Subcubic Graph Numbers". Archived from the original on 7 April 2024.
↑ Sloane, N. J. A. (ed.). "Sequence A300403 (Smallest integer i such that SSCG(i) >= n.)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
1 2 "Immense Subcubic Graph Numbers - Numberphile" on YouTube
↑ Friedman, Harvey. "[FOM] 279:Subcubic Graph Numbers/restated". Archived from the original on 13 May 2024.
↑ TREE(3) and impartial games | Complex Projective 4-Space
↑ Friedman, Harvey. "[FOM] 271:Clarification of Smith Article". Ohio State University Department of Mathematics. Archived from the original on 26 Feb 2024.

[SSCG-1] 1 2 Friedman, Harvey. "[FOM] 274:Subcubic Graph Numbers". Archived from the original on 7 April 2024.

[2] Sloane, N. J. A. (ed.). "Sequence A300403 (Smallest integer i such that SSCG(i) >= n.)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[numberphile-3] 1 2 "Immense Subcubic Graph Numbers - Numberphile" on YouTube

[4] Friedman, Harvey. "[FOM] 279:Subcubic Graph Numbers/restated". Archived from the original on 13 May 2024.

[5] TREE(3) and impartial games | Complex Projective 4-Space

[6] Friedman, Harvey. "[FOM] 271:Clarification of Smith Article". Ohio State University Department of Mathematics. Archived from the original on 26 Feb 2024.

[1]

[2]

[3]

[4]

[5]

[6]

Background

SSCG function

SCG function

See also

Notes

References