La teoría de grafos es una disciplina de las matemáticas que, por diferentes motivos, actualmente tiene mucha popularidad. Para aquellos lectores que no se hagan idea de lo que estamos hablando, pueden pensar en el mapa del metro de una ciudad: tenemos unos puntos, que son las estaciones, conectados por otras líneas, que representarían las vías o los túneles. Cuando antes llegábamos a una ciudad que no conocíamos procurábamos hacernos con un plano del transporte y estimábamos cuál era la mejor ruta para desplazarnos en esa ciudad. Hoy lo hacen por nosotros algunas aplicaciones, pensando en la red de transporte como un grafo y utilizando algoritmos de recorrido mínimo. En este ABCdario de las matemáticas han aparecido en diferentes ocasiones y doy por seguro que seguirán apareciendo, por ser un objeto de estudio en constante desarrollo. Hoy aparecen de nuevo debido al reciente descubrimiento del noveno número de Dedekind, un número entero que consta de 42 dígitos y que se ha estado buscando durante más de 30 años. Vamos a acercarnos a este problema y su importancia proponiendo un reto al lector; pensemos en un cuadrado equilibrado sobre uno de sus vértices: El reto consiste en colorear algunos vértices de rojo de modo que nunca haya un vértice blanco en un nivel superior al que hay uno rojo. Por ejemplo, el coloreado que hemos descrito, con todos los vértices blancos, sería uno válido. Otro sería, por ejemplo, el siguiente: El cuadrado tiene dimensión 2 y el número de posibilidades que tenemos para colorear el cuadrado siguiendo las reglas enunciadas viene dado por el llamado segundo número de Dedekind, asociado a dimensión 2. Para quienes lo quieran intentar, adelantamos que ese número, en el caso propuesto, es 6. Noticia Relacionada estandar No Qué es la combinatoria y cómo consigue que las campanas nunca suenen en el mismo orden Pedro Alegría Cómo resolver el problema para que los clientes de un hotel ocupen todas las habitaciones sin repetir ninguna Antes de adentrarnos en el problema que se acaba de resolver (correspondiente a la novena dimensión) vamos a ver qué ocurre con los casos anteriores. El número de Dedekind correspondiente a dimensión 0 es 2: el «cuadrado» en dimensión 0 sería únicamente un punto y solo tenemos dos opciones: podemos colorearlo de rojo o dejarlo blanco. No hay más posibilidades. Si vamos a dimensión 1, el equivalente al cuadrado bidimensional sería un segmento. Este puede ser coloreado únicamente de 3 maneras distintas, siguiendo esas reglas: El de dimensión 2 ya lo hemos mencionado. El equivalente al cuadrado en el caso tridimensional es el cubo. Este caso es bastante más complejo y recomiendo que lo pensemos manipulando un cubo real (puede ser un cubo de Rubik, un dado o cualquier objeto cúbico). Si lo ponemos, como antes, sujeto sobre la esquina inferior, podemos apreciar 4 pisos: 1 vértice abajo, un segundo nivel en el que los vértices forman un triángulo equilátero, un tercer nivel formado por otros tres vértices, que forman un triángulo girado 180o respecto al anterior y un cuarto nivel con un único vértice. Hemos representado el primer piso en rosa, el segundo en violeta, el tercero en azul y el cuarto en negro. (En realidad coincidirían el vértice rosa con el negro, pero en nuestra representación lo hemos desplazado un poco). Retamos al lector a que encuentre las 20 maneras de colorear los vértices del cubo con las reglas descritas anteriormente: si aparece un punto rojo en un determinado nivel, no puede aparecer ningún blanco en un nivel superior. Si pasamos de la tercera a la cuarta dimensión, los problemas crecen: lo primero es hacernos una idea de cómo podemos representar el hipercubo, que sería el análogo al cubo pero en dimensión 4. Hay varias formas de representarlo y también recurrimos a la teoría de grafos para ello: podemos representar de forma plana objetos tridimensionales fijándonos en sus vértices y sus aristas. Por ejemplo, el cubo tridimensional puede representarse de forma plana por medio de su diagrama de Schelegel, que viene a ser quitar la tapa superior del cubo, asomarnos y ver qué queda: El diagrama equivalente para el hipercubo sería algo parecido al monumento a la Constitución que hay en Madrid: Con la necesaria dosis de abstracción deberíamos equilibrar el hipercubo sobre una esquina y contar el número de posibles coloraciones, que en este caso son 168. De este modo hemos obtenido la sucesión 2, 3, 6, 20, 168, … que es la que recoge los llamados números de Dedekind puesto que él mismo definió el problema en 1897 y calculó los 5 primeros términos de la sucesión, hasta el 168. El siguiente de estos números es 7581 y lo encontró Randolph Church en 1940. Seis años más tarde, en 1946, Morgan Ward descubrió el siguiente término de la sucesión, el 7.828.354. Pasaron casi 20 años antes de encontrar el número de Dedekind correspondiente a dimensión 7, y fue de nuevo Randolph Ward quien fue capaz de conseguir encontrar que era 2.414.682.040.998. la verificación de la corrección de este valor se completó 10 años más tarde, por Joel Berman and Peter Koehler. Observamos que el número de posibilidades de coloreado aumenta muy rápidamente: el número de posibilidades de coloreado del hipercubo en dimensión 8 es un número de 23 dígitos. Concretamente es el número 56.130.437.228.687.557.907.788 y fue encontrado por Doug Wiedemann en 1991 utilizando un ordenador Cray 2 durante 5 meses (recordemos que hablamos del uso del ordenador Cray 1 en el reto de calcular decimales de pi en un artículo anterior en este mismo ABCdario de las matemáticas). MÁS INFORMACIÓN noticia No Del ábaco a la máquina de Turing: los antepasados de tu ordenador y tu móvil noticia No El increíble ajedrecista de Torres Quevedo, el autómata que siempre daba jaque mate y realizaba «el trabajo cerebral de un hombre» Con un supercomputador Han pasado 32 años desde el hito anterior en esta aventura de encontrar los números de Dedekind. Pero se ha conseguido avanzar un paso más, puesto que Lennart Van Hirtum y Patrick De Causmaeker consiguieron este número el pasado 8 de marzo, aunque la noticia se acaba de publicar ahora, tras un periodo de necesaria comprobación, y se explicará a la comunidad matemática el próximo mes de septiembre, en un congreso sobre funciones Booleanas y sus aplicaciones que tendrá lugar en Noruega. Su proyecto empezó hace 3 años, cuando Van Hirtum pensó que, con el supercomputador Noctua situado en la Universidad de Paderborn (Alemania), sería capaz de abordar este problema utilizando una técnica desarrollada por su profesor De Causmaeker. Esta técnica permitía abordar en 8 minutos, utilizando un ordenador «normal» de sobremesa, el problema que en 1991 se resolvió a lo largo de 5 meses con el Cray 2 pero destacan que, sin embargo, para avanzar en el caso de dimensión 9 que han sido capaces de resolver ahora, un ordenador corriente necesitaría cientos o miles de años, puesto que el número de términos de la fórmula que queda crece exponencialmente. La imagen muestra las soluciones al reto propuesto Wikimedia Sea como fuere, han encontrado que el número 286 386 577 668 298 411 128 469 151 667 598 498 812 366 es, precisamente, el noveno número de Dedekind que se ha estado buscando durante 32 años. ¿Cuándo encontraremos el décimo? SOBRE EL AUTOR Fernando Blasco es profesor de Matemática Aplicada de la Universidad Politécnica de Madrid, presidente de la Comisión de Divulgación de la Real Sociedad Matemática Española (RSME) y miembro del Comité de Sensibilización Pública de la Sociedad Matemática Europea. La sección ABCdario de las Matemáticas es una sección que surge de la colaboración con la Comisión de Divulgación de la Real Sociedad Matemática Española (RSME).
