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 G1, G2, ... de tal manera que cada grafo Gi tiene como máximo i + k vértices (para algún entero k) y para ningún i < j es Gi homeomórficamente integrable (es decir, es un gráfico menor de) Gj.
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 × 23 × 295 − 9 ≈ 103,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).
Datos: Q21014376
