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

Author

Felix Fröhlich, Mar 05 2018

Keywords

• nonn

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.

Examples

			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.
		

Links

• 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

Crossrefs

Cf. A090529, A300402, A300404.