En matemáticas , un gráfico subcúbico simple (SSCG) es un gráfico simple finito en el que cada vértice tiene un grado como máximo de tres. Supongamos que tenemos una secuencia de gráficos subcúbicos simples G 1 , G 2 , ... tal que cada gráfico G i tiene como máximo i + k vértices (para algún número entero k ) y para no i < j es G i incrustable homeomórficamente en ( es decir, es una gráfica menor de) G j .
El teorema de Robertson-Seymour demuestra que los gráficos subcúbicos (simples o no) están bien fundamentados por la incrustabilidad homeomórfica, lo que implica que tal secuencia no puede ser infinita. Entonces, para cada valor de k , hay una secuencia con longitud máxima. La función SSCG ( k ) [1] denota esa longitud para gráficos subcúbicos simples. La función SCG ( k ) [2] denota esa longitud para gráficos subcúbicos (generales).
La secuencia SCG comienza SCG (0) = 6, pero luego explota a un valor equivalente af ε 2 * 2 en la jerarquía de rápido crecimiento .
La secuencia SSCG comienza SSCG (0) = 2, SSCG (1) = 5, pero luego crece rápidamente. SSCG (2) = 3 × 2 (3 × 2 95 ) - 8 ≈ 3.241704 ⋅ 10 35775080127201286522908640066 y su expansión decimal termina en ... 11352349133049430008.
SSCG (3) es mucho más grande que TREE (3) y TREE TREE (3) (3). [a] Adam P. Goucher afirma que no hay diferencia cualitativa entre las tasas de crecimiento asintótico de SSCG y SCG. Él escribe "Está claro que SCG ( n ) ≥ SSCG ( n ), pero también puedo probar SSCG (4 n + 3) ≥ SCG ( n )". [3]
Ver también
Notas
- ^ La función TREE anida TREE (3) veces con 3 en la parte inferior