Función SSCG de Friedman
# Función SSCG de Friedman

En matemáticas, un grafo subcúbico simple es un gráfico simple finito en el que cada vértice tiene grado como máximo tres. Supongamos que tenemos una secuencia de grafos simples subcúbicos $G_1,$ $G_2,$ ... de tal manera 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 (es decir, es un gráfico menor de) $G_j.$

El teorema de Robertson-Seymour demuestra que los grafos subcúbicos (simples o no) están bien definidos por incrustabilidad homeomórfica, lo que implica que una secuencia de este tipo no puede ser infinita. Por lo tanto, para cada valor de k, hay una secuencia con una longitud máxima. La SSCG(k) expresa la longitud de los grafos subcúbicos simples. La función SCG(k) expresa la longitud de (general) subcúbicos generales.

La secuencia SSCG comienza SSCG(0) = 2, SSCG(1) = 5, pero luego crece rápidamente. SSCG(2) = 3 × $2^{3×295}$ − 9 ≈ $10^{3,5775×1028}.$ SSCG(3) no sólo es más grande que ÁRBOL(3), sino que es más grande que $ÁRBOL^{ÁRBOL(3)}(3).$

Adam Goucher afirma que no hay diferencia cualitativa entre las tasas de crecimiento asintóticas de SSCG y SCG. Escribe: "Está claro que SCG(n) ≥ SSCG (n), pero también puede resultar SSCG(4n + 3) ≥ SCG(n).

