El número de Graham

Piensa un número grande, muy grande, el número (con algún nombre o significado) más grande del que hayas visto, leído u oído algo. Quizás te haya venido a la cabeza un billón, que es un 1 seguido de 12 ceros. Sí, es grande, pero seguro que también has escuchado a alguien nombrar al trillón, que es un millón de billones (formado entonces por un 1 seguido de 18 ceros) y que, por tanto, es mayor que un billón.



El número de Graham, que recibe su nombre del matemático Ronald Graham, es una cota superior de la solución de un determinado problema en la teoría de Ramsey, concretamente el siguiente:






Considérese un hipercubo n-dimensional, y conéctese cada par de vértices para obtener un grafo completo con 2^n vértices. Posteriormente, coloréese cada una de las aristas de negro o de rojo. ¿Cuál es el menor valor de n para el cual toda manera de colorear las aristas necesariamente da lugar a un subgrafo completo de un solo color con 4 vértices que forman un plano?



Graham y Rothschild [1971] demostraron que este problema tiene una solución, N*, y dieron como acotación de la misma 6 ≤ N* ≤ N, siendo N un número determinado, definido explícitamente y muy grande. Sin embargo, Graham revisó esta cota superior al alza, la cual fue publicada (y apodada número de Graham) por Martin Gardner en la revista Scientific American de noviembre de 1977 de la siguiente manera:



En una demostración no publicada, Graham ha establecido recientemente … una cota tan vasta que tiene el registro de ser el mayor número jamás usado en una demostración matemática seria.


Ahora bien, ¿cuál es el número de Graham?

Aquí tenéis un vídeo (en inglés) en el que el propio matemático explica qué es el número de Graham:

Por si no lo has entendido, hacemos un pequeño resumen. Lo que hace Graham es duplicar cubos para aumentar el número de dimensiones, uniendo los vértices de modo que nunca las líneas que los unen y que forman un mismo plano tengan el mismo color. Hay un número máximo de dimensiones para la que esto se puede evitar.


Sabemos que en 12 dimensiones sí podríamos evitarlo, por lo que tendríamos que irnos a 13. ¿El problema? Que no podemos calcularlo, ni con el ordenador más potente del mundo. ¿Por qué? En 13 dimensiones tenemos 8192 vértices, que son 33.550.336 segmentos para unir todos los vértices. Para calcular las formas de combinar planos en dos dimensiones tenemos que elevar 2 a 33.550.336, y eso es incalculable.

El número de Graham es tan grande que no se puede calcular.