En matemáticas , un grafo subcúbico simple ( SSCG ) es un grafo simple finito en el que cada vértice tiene un grado de tres como máximo. Supongamos que tenemos una secuencia de grafos subcúbicos simples G 1 , G 2 , ... tales que cada grafo G i tiene como máximo i + k vértices (para algún entero k ) y para ningún i < j es G i homeomórficamente integrable en (es decir, es un grafo menor de) G j .
El teorema de Robertson-Seymour demuestra que los grafos subcúbicos (simples o no) están bien fundados por la incrustabilidad homeomórfica, lo que implica que dicha secuencia no puede ser infinita. Luego, al aplicar el lema de König al árbol de dichas secuencias bajo extensión, para cada valor de k hay una secuencia con longitud máxima. La función SSCG( k ) [1] denota esa longitud para grafos subcúbicos simples. La función SCG( k ) [2] denota esa longitud para grafos subcúbicos (generales).
La secuencia SCG comienza SCG(0) = 6, pero luego explota a un valor equivalente a f ε 2 *2 en la jerarquía de rápido crecimiento .
La secuencia SSCG comienza más lentamente que SCG, SSCG(0) = 2, SSCG(1) = 5, pero luego crece rápidamente. SSCG(2) = 3 × 2 (3 × 2 95 ) − 8 ≈ 3,241704 × 1035 775 080 127 201 286 522 908 640 065. Sus primeros y últimos 20 dígitos son 32417042291246009846...34057047399148290040. SSCG(3) es mucho más grande que TREE(3) y TREE TREE(3) (3), es decir, la función TREE anidó TREE(3) veces con 3 en la parte inferior.
Adam P. Goucher afirma que no existe diferencia cualitativa entre las tasas de crecimiento asintótico de SSCG y SCG. Escribe: "Está claro que SCG( n ) ≥ SSCG( n ), pero también puedo demostrar que SSCG(4 n + 3) ≥ SCG( n )." [3]
La función fue propuesta y estudiada por Harvey Friedman .