Puntos y trazos: ¡que empiece la fiesta de las matemáticas!

Es difícil saber cuándo te atraparán las matemáticas. Todo puede empezar de forma muy sencilla, por ejemplo tras una larga llamada telefónica a una administración poco disponible. Inconscientemente, coges un bolígrafo mientras suena en bucle una melodía de Vivaldi y empiezas a garabatear un dibujo. Podrías obtener, por ejemplo, el dibujo de al lado.

Has colocado ocho puntos y trazado ocho segmentos de entre todos los que pueden unir esos puntos. La forma de «nueve» parece anodina, pero hay una particularidad que llama la atención: ¡todos los segmentos trazados tienen la misma longitud! Una vez colgado el teléfono, completas con avidez el dibujo añadiendo otros dos segmentos, también de la misma longitud, uno de ellos dentro del bucle del «nueve», y constatas que no puedes añadir más sin incorporar nuevos puntos.

Surge una pregunta matemática natural: fijado el número n de puntos, ¿cuántos segmentos de la misma longitud que unan esos n puntos —colocados a tu gusto y con ingenio— se pueden trazar como máximo?

Para n = 3, el problema es fácil: el triángulo equilátero proporciona una configuración en la que todos los segmentos que se pueden trazar tienen la misma longitud.

Para n = 4, el cuadrado proporciona cuatro segmentos de la misma longitud —los lados—, pero enseguida se advierte que se puede hacer mejor y obtener cinco segmentos de la misma longitud uniendo dos triángulos equiláteros por uno de sus lados. Un razonamiento geométrico permite después demostrar que no se pueden tener seis segmentos de la misma longitud que unan cuatro puntos —y este es un pequeño desafío que se deja a la perspicacia de los lectores—.

Pruebas con pocos puntos.

Para n = 5, se pueden obtener siete segmentos de la misma longitud añadiendo un triángulo equilátero a uno de los lados exteriores, pero ¿no se puede hacer mejor siendo más ingenioso?

Mientras haces intentos de dibujos con números de puntos algo mayores, logras calcular algunos valores óptimos para pequeños valores de n. Te preguntas qué ocurre cuando n se hace realmente grande. Dicho de otro modo, ¿a qué velocidad evoluciona el número máximo de segmentos de la misma longitud al variar el número de puntos? Al hacerlo, y sin saberlo, ¡redescubres una conjetura del ilustre matemático húngaro Paul Erd?s sobre la estimación asintótica de esta cantidad!

Erd?s había anunciado, en efecto, en un brevísimo artículo de 1946 que «parecía probable» que el número de segmentos fuera asintóticamente menor que n^a para todo a > 1. Incluso ofrecía, como era su costumbre, una recompensa de quinientos dólares a quien fuera capaz de demostrar o refutar esta conjetura. Señal de que el resultado debe de ser importante para los matemáticos: esta recompensa es una de las más generosas que propuso.

Esta afirmación nacida de la intuición de Erd?s sigue siendo hoy una cuestión abierta. El mejor resultado de que disponemos data de... 1984: el número máximo de segmentos está asintóticamente acotado superiormente por n^4/3. Es un hermoso resultado obtenido por los matemáticos Joel Spencer, Endre Szemerédi —además, premio Abel en 2012— y William Trotter. Lazlo Székely mejoró la demostración en 1997, pero conviene tener muy presente que aún quedan muchos valores posibles para el exponente a entre 1 y 4/3. La conjetura de Erd?s sigue en pie...

Como ocurre a menudo al abordar cuestiones de grafos, podemos fijarnos en el grafo de Petersen. Es fácil de recordar, pues parece salido de un ritual satánico. Más en serio, resulta ser un temible contraejemplo para muchas intuiciones matemáticas.

El grafo de Petersen y su aspecto satánico.

Desde el punto de vista que nos ocupa, en cambio, parece muy decepcionante: los segmentos no tienen todos la misma longitud, aunque sí los del pentágono central. Sin embargo, al girar hábilmente los puntos exteriores y «estirar un poco» la figura, se consigue que todos los segmentos tengan la misma longitud. Se modifica el esquema, pero se conservan los segmentos que unían los puntos: estos permanecen «conectados», «unidos» cuando los puntos se mueven. Obtenemos así otra representación del grafo de Petersen, que esta vez posee la propiedad buscada.

Otra representación del grafo de Petersen. Esta vez, todos los segmentos tienen la misma longitud.

En términos técnicos, se llama grafo de distancia unidad a un grafo que admite un dibujo en el que todos los segmentos tienen la misma longitud. He aquí una segunda pregunta matemática aparentemente anodina: ¿son todos los grafos de distancia unidad? Dicho de otro modo, ¿existe, para cualquier dibujo de un grafo, un desplazamiento de los puntos que haga que todos los segmentos trazados tengan la misma longitud? La respuesta es negativa, y ya lo sabes si resolviste el pequeño desafío del principio. En efecto, con cuatro puntos se pueden trazar como máximo cinco segmentos de la misma longitud; por tanto, si se toman cuatro puntos y se unen mediante seis segmentos —es decir, si se trazan todos los segmentos posibles—, se obtiene un grafo que, incluso tras desplazar los puntos, seguirá teniendo dos segmentos de longitudes distintas.

Modifiquemos entonces la pregunta: ¿cómo reconocer los grafos de distancia unidad? El problema es bastante difícil, incluso muy difícil. Para convencerte, observa este grafo muy particular, llamado grafo de Heawood.

El grafo de Heawood, con sus catorce puntos y veintiún segmentos.

En este esquema, no todos los segmentos tienen la misma longitud. Es una propiedad fácil de comprobar. En cambio, ¡a ver quién es capaz de decir si existe una representación del grafo de Heawood en la que todos los segmentos tengan la misma longitud! Encontrar una representación adecuada es difícil, pero comprobar que una representación lo es resulta fácil. En 2013, el matemático alemán Marcus Schaefer demostró que este problema es NP-completo, es decir, a grandes rasgos, que pertenece a la clase de problemas equivalentes que se consideran muy difíciles de resolver, pero cuyas soluciones admiten verificaciones sencillas.

Dicho esto, se puede demostrar que el grafo de Heawood sí es un grafo de distancia unidad.

También se puede explicar cómo distinguir los grafos que no son de distancia unidad a partir del ejemplo de cuatro puntos en el plano. Es imposible construir un dibujo en el que los seis segmentos tengan la misma longitud; no es del todo cierto, o más bien lo es en el plano. Si esta vez hacemos un dibujo en tres dimensiones, resulta fácil construir un tetraedro regular cuyos lados tienen todos la misma longitud.

Para un grafo cualquiera, tres dimensiones no siempre bastan, e introducimos la noción de dimensión mínima del espacio en el que el grafo admite una representación cuyos segmentos tienen todos la misma longitud (véase el recuadro). Partíamos de un dibujo garabateado durante una espera telefónica, ¡y aquí estamos proyectados a la cuarta dimensión o más allá! Desde luego, nunca se sabe cuándo nos atraparán las matemáticas...