cp's OEIS Frontend

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

%I A300403 #11 Feb 16 2025 08:33:53
%S A300403 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,
%T A300403 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,
%U A300403 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2
%N A300403 Smallest integer i such that SSCG(i) >= n.
%C A300403 The sequence grows very slowly.
%C A300403 A subcubic graph is a graph where each vertex has degree <= 3 (cf. Baaz et al., 2011, p. 419).
%C A300403 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.
%H A300403 M. Baaz, C. H. Papadimitriou, H. W. Putnam, D. S. Scott and C. L. Harper, Jr., <a href="https://books.google.com/books?id=Tg0WXU5_8EgC&amp;pg=PA419">Kurt Gödel and the Foundations of Mathematics: Horizons of Truth</a>, Cambridge University Press, 2011, ISBN 978-0-521-76144-4.
%H A300403 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SimpleGraph.html">Simple Graph</a>
%H A300403 Wikipedia, <a href="https://en.wikipedia.org/wiki/Friedman%27s_SSCG_function">Friedman's SSCG function</a>
%H A300403 Wikipedia, <a href="https://en.wikipedia.org/wiki/Graph_minor">Graph minor</a>
%e A300403 SSCG(0) = 2, so a(n) = 0 for n <= 2.
%e A300403 SSCG(1) = 5, so a(n) = 1 for 3 <= n <= 5.
%e A300403 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.
%Y A300403 Cf. A090529, A300402, A300404.
%K A300403 nonn
%O A300403 1,6
%A A300403 _Felix Fröhlich_, Mar 05 2018