Función SSCG de Friedman

En matemáticas, una gráfica subcubic simple es un simple gráfico finito en el que cada vértice tiene grado como máximo tres. Supongamos que tenemos una secuencia de simples gráficos subcubic G₁, G₂, ... de tal manera que cada gráfico G_i ha 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 gráfico menor de) G_j.

El teorema de Robertson-Seymour demuestra que los gráficos subcubic (simples o no) están bien fundados por incrustabilidad homeomorfo, lo que implica una secuencia de este tipo no puede ser infinito. Por lo tanto, para cada valor de k, hay una secuencia con una longitud máxima. El SSCG(k) función indica que la longitud de los gráficos subcubic simples. El SCG(k) función indica que la longitud de (general) gráficos subcubic.

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), pero es más grande que ÁRBOL(ÁRBOL(ÁRBOL(...ÁRBOL(3)...))) por alguna gran número de niveles de anidamiento de la función ÁRBOL. Adam Goucher afirma que no hay diferencia cualitativa entre las tasas de crecimiento asintóticas de SSCG y SCG. Él escribe: "Está claro que SCG(n) ≥ SSCG (n), pero también puede resultar SSCG(4n + 3) ≥ SCG(n).