Función SSCG de Friedman

La función SSCG de Friedman es una función matemática definida por Harvey Friedman . Se define por${\displaystyle {\text{SSCG}}(k)}$como el entero más grande${\displaystyle n}$que cumplen con lo siguiente:

Hay una secuencia${\displaystyle G_{1},\ldots ,G_{n}}$de gráficos subcúbicos simples tales que cada${\displaystyle G_{i}}$tiene como máximo${\displaystyle i+k}$vértices y para no${\displaystyle i<j}$es${\displaystyle G_{i}}$incrustable homeomórficamente en${\displaystyle G_{j}}$.

Posteriormente, Friedman definió los grafos subcúbicos más generales.${\displaystyle {\text{SCG}}(k)}$.

En matemáticas , especialmente en teoría de grafos , un grafo subcúbico simple ( SSCG ) es un grafo simple finito en el que cada vértice tiene un grado de como máximo tres. Supongamos que tenemos una secuencia de grafos subcúbicos simples.${\displaystyle G_{1}}$,${\displaystyle G_{2}}$, ... de tal manera que cada gráfico${\displaystyle G_{i}}$tiene como máximo${\displaystyle i+k}$vértices (para algún entero)${\displaystyle k}$) y para no${\displaystyle i<j}$es${\displaystyle G_{i}}$incrustable homeomórficamente en (es decir, es un menor de grafos de)${\displaystyle 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. Entonces, al aplicar el lema de Kőnig al árbol de tales secuencias bajo extensión, para cada valor de${\displaystyle k}$Hay una secuencia con longitud máxima. La función${\displaystyle {\text{SSCG}}(k)}$denota esa longitud para gráficos subcúbicos simples. La función${\displaystyle {\text{SCG}}(k)}$denota esa longitud para grafos subcúbicos (generales).

Harvey Friedman definió dos funciones: SSCG y SCG.

Friedman definió${\displaystyle {\text{SSCG}}(k)}$como el entero más grande${\displaystyle n}$que satisface lo siguiente: ^{[ 1 ]}

Hay una secuencia${\displaystyle G_{1},\ldots ,G_{n}}$de gráficos subcúbicos simples tales que cada${\displaystyle G_{i}}$tiene como máximo${\displaystyle i+k}$vértices y para no${\displaystyle i<j}$es${\displaystyle G_{i}}$incrustable homeomórficamente en${\displaystyle G_{j}}$.

Los primeros términos de la secuencia son

${\displaystyle \operatorname {SSCG} (0)=2,}$

${\displaystyle \operatorname {SSCG} (1)=5,}$ y

${\displaystyle \operatorname {SSCG} (2)=3\cdot 2^{3\cdot 2^{95}}\!\!-8=3\cdot 2^{118\,842\,243\,771\,396\,506\,390\,315\,925\,504}\!-8}$

${\displaystyle \qquad \qquad \;\approx \,3.241\,704\,229\cdot 10^{35\,775\,080\,127\,201\,286\,522\,908\,640\,065}}$

${\displaystyle \qquad \qquad \;\approx \,10^{3.5775\,\cdot \,10^{28}}.}$^{[ 2 ]}

Se ha demostrado que el próximo término,${\displaystyle {\text{SSCG}}(3)}$, es mayor que TREE(3) . ^{[ 3 ]} Friedman demostró que${\displaystyle {\text{SSCG}}(13)}$es mayor que el tiempo de parada de cualquier máquina de Turing que se pueda demostrar que se detiene en Π ¹ ₁ -CA ₀ con como máximo${\displaystyle 2\uparrow \uparrow 2000}$^[a] símbolos, y que no se puede probar que exista en esa teoría con menos de${\displaystyle 2\uparrow \uparrow 1000}$símbolos, donde${\displaystyle \uparrow \uparrow }$denota tetración . Lo hace usando una idea similar a la de una afirmación similar que demostró sobre${\displaystyle {\text{ÁRBOL}}(3)}$. ^{[ 1 ]}

Más tarde, Friedman se dio cuenta de que no había una buena razón para imponer la condición de "simple" a los gráficos subcúbicos. Relaja la condición y define${\displaystyle {\text{SCG}}(k)}$como el más grande${\displaystyle n}$satisfactorio: ^{[ 4 ]}

Hay una secuencia${\displaystyle G_{1},\ldots ,G_{n}}$de gráficos subcúbicos tales que cada${\displaystyle G_{i}}$tiene como máximo${\displaystyle i+k}$vértices y para no${\displaystyle i<j}$es${\displaystyle G_{i}}$incrustable homeomórficamente en${\displaystyle G_{j}}$.

El primer término de la secuencia es${\displaystyle {\text{SCG}}(0)=6}$, mientras que el próximo término${\displaystyle {\text{SCG}}(1)}$es mayor que el número de Graham . Además,${\displaystyle {\text{SCG}}(3)}$es más grande que${\displaystyle {\text{ÁRBOL}}^{{\text{ÁRBOL}}(3)}(3)}$. ^{[ 3 ]}

Adam P. Goucher afirma que no hay diferencia cualitativa entre las tasas de crecimiento asintótico de SSCG y SCG. Escribe: "Está claro que${\displaystyle {\text{SCG}}(n)\geq {\text{SSCG}}(n)}$, pero también puedo demostrarlo${\displaystyle {\text{SSCG}}(4n+3)\geq {\text{SCG}}(n)}$". ^{[ 5 ]}

• Teorema de Goodstein
• Teorema de Paris-Harrington
• Teorema de Kanamori-McAloon
• El teorema del árbol de Kruskal , que conduce a la función TREE similar.
• Juego de la Hidra

^{^} Friedman en realidad escribe esto como 2^[2000], que denota una pila exponencial de 2 de altura 2000 usando su notación. ^{[ 6 ]}