Funció SSCG de Friedman
En matemàtiques, un grafo subcúbico simple[1] és un grafo simple finito en el que cada vèrtiç té grau com a màxim tres. Supongam que tenim una seqüència de grafos simples subcúbicos G1, G2, ... de tal manera que cada grafo Gi té com a màxim i + k vèrtiços (per a algun sancer k) i per a cap i < j és Gi homeomórficamente integrable (és dir, és un gràfic menor de) Gj.
El teorema de Robertson-Seymour demostra que els grafos subcúbicos (simples o no) estan ben definits per incrustabilidad homeomórfica, lo que implica que una seqüència d'este tipo no pot ser infinita. Per lo tant, per a cada valor de k, hi ha una seqüència en una llongitut màxima. La SSCG(k) expressa la llongitut dels grafos subcúbicos simples. La funció SCG(k) expressa la llongitut de (general) subcúbicos generals.
La seqüència SSCG comença SSCG(0) = 2, SSCG(1) = 5, pero després creix ràpidament. SSCG(2) = 3 × 23 × 295 − 9 ≈ 103,5775 × 1028. SSCG(3) no només és més gran que ÁRBOL(3), sino que és més gran que ÁRBOLÁRBOL(3)(3).
Adam Goucher afirma que no hi ha diferència qualitativa entre les taxes de creiximent asintòtiques de SSCG i SCG. Escriu: "Està clar que SCG(n) ≥ SSCG (n), pero també pot resultar SSCG(4n + 3) ≥ SCG(n).
Referències
[editar | editar còdic]
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Función SSCG de Friedman» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.