A300403 Smallest integer i such that SSCG(i) >= n.

0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset

1,6

Comments

The sequence grows very slowly.

A subcubic graph is a graph where each vertex has degree <= 3 (cf. Baaz et al., 2011, p. 419).

SSCG(n) gives the length of the longest sequence of simple subcubic graphs G_1, G_2, ..., G_i such that each G_i has at most i+n vertices and G_i is not a graph minor of G_j for any j > i.

Links

Table of n, a(n) for n=1..87.

M. Baaz, C. H. Papadimitriou, H. W. Putnam, D. S. Scott and C. L. Harper, Jr., Kurt Gödel and the Foundations of Mathematics: Horizons of Truth, Cambridge University Press, 2011, ISBN 978-0-521-76144-4.

Eric Weisstein's World of Mathematics, Simple Graph

Wikipedia, Friedman's SSCG function

Wikipedia, Graph minor

Example

SSCG(0) = 2, so a(n) = 0 for n <= 2.
SSCG(1) = 5, so a(n) = 1 for 3 <= n <= 5.
SSCG(2) = 3*2^(3*2^95)-8 ~ 10^(3.5775*10^28), so a(n) = 2 for 6 <= n <= 3*2^(3*2^95)-8.

Crossrefs

Cf. A090529, A300402, A300404.

Sequence in context: A044932 A211669 A065687 * A077433 A065685 A084100

Adjacent sequences: A300400 A300401 A300402 * A300404 A300405 A300406

Keyword

nonn

Author

Felix Fröhlich, Mar 05 2018

Status

approved