Númberu de Graham

El númberu de Graham, que recibe'l so nome de Ronald Graham, ye un númberu grande que ye una cota cimera de la solución d'un determináu problema na teoría de Ramsey. Esti númberu consiguió cierta fama popular cuando Martin Gardner escribió na seición «Mathematical Games» (Xuegos Matemáticos) de la revista Scientific American en payares de 1977:

Nuna demostración ensin publicar, Graham estableció apocayá ... una cota tan vasta que tien el rexistru de ser el mayor númberu enxamás usáu nuna demostración matemática seria.^[1]

El Llibru Guinness de los récores, na so edición de 1980, repitió l'afirmación de Gardner, lo que contribuyó al interés popular d'esti númberu. El númberu de Graham ye enforma mayor qu'otros conocíos númberos grandes tales como'l gúgol, el gúgolplex ya inclusive'l númberu de Skewes y el de Moser. Ello ye que ye imposible, daes les llimitaciones d'espaciu y materia del nuesu universu, denota'l númberu de Graham o un aproximamientu razonable del mesmu nun sistema de numberación convencional. Inclusive les «torres d'esponentes» de la forma ${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$ revélense inútiles pa esti propósitu, anque'l númberu puede ser descritu con fórmules recursives per aciu de la notación flecha de Knuth o fórmules equivalentes, como fixo Graham. Los diez últimos díxitos del númberu de Graham son ...2464195387. Anguaño, considéraselu como'l númberu representáu matemáticamente más grande de toos.

Dende'l descubrimientu y usu del númberu de Graham, emplegáronse númberos tovía mayores n'otres demostraciones matemátiques, por casu, rellacionaes coles variaes formes finites de Friedman del teorema de Kruskal.

Problema de Graham

El númberu de Graham ta rellacionáu col siguiente problema perteneciente a la caña de les matemátiques conocida como la teoría de Ramsey:

Considérese un hipercubo n-dimensional, y conéctese cada par de vértices pa llograr un grafo completu con ${\displaystyle 2^{n}}$ vértices. Darréu, coloréese caúna de les arestes de negru o de colloráu. ¿Cuál ye'l menor valor de n pal cual toa manera de colorear les arestes necesariamente da llugar a un subgrafo completu d'un solu color con 4 vértices que formen un planu?

Graham y Rothschild [1971] demostraron qu'esti problema tien una solución, N*, y dieron como acotación de la mesma 6 ≤ N* ≤ N, siendo N un númberu determináu, definíu explícitamente y bien grande; sicasí, Graham (nun trabayu ensin publicar) revisó esta cota cimera a l'alza. Esta cota cimera revisada por Graham foi darréu publicada (y moteyada númberu de Graham) por Martin Gardner en [Scientific American, "Mathematical Games", payares de 1977].

La cota inferior foi darréu ameyorada por Exoo [2003], quien amosó que la solución ye siquier 11 y apurrió evidencia esperimental que suxería que yera siquier 12. Con esto, la estimación más conocida pa la solución N* ye 11 ≤ N* ≤ G, onde G ye'l númberu de Graham.