El trabajo de Mirzakhani parte de una pregunta relacionada con el célebre problema de los cuatro colores. Este puede enunciarse del siguiente modo: dado un mapa geográfico cualquiera, ¿es posible colorear todos los países usando solo cuatro colores, de tal modo que dos naciones del mismo color nunca compartan frontera? (Por «frontera» debemos entender aquí «más que un punto».)

El primer paso para resolverlo consiste en reformularlo en términos de un grafo. Para ello, sustituimos cada país por un punto («vértice») y, después, conectaremos dos de ellos con una línea («arista») si y solo si los países correspondientes son adyacentes. De esta manera, habremos transformado nuestro mapa original en un grafo.

La teoría de grafos constituye un área muy fértil de las matemáticas. Ello se debe a que sus objetos son abstractos (las aristas y los vértices no poseen ninguna propiedad, más allá de que las primeras conectan los segundos), lo que permite derivar todo tipo de resultados. Y, en numerosas aplicaciones, conviene ignorar las características de los objetos y concentrarse solo en sus relaciones.

Por ejemplo, los resultados sobre coloraciones de grafos no afectan únicamente a los cartógrafos. En las redes de telefonía móvil, dos operadores cuyas áreas de influencia se superpongan no deberían utilizar la misma frecuencia si desean evitar interferencias. Una situación similar aparece en el diseño de programas informáticos; en este caso, los recursos limitados del sistema son los registros, los espacios de memoria del procesador que pueden modificarse con gran rapidez y en los que, por ejemplo, se van almacenando las sumas parciales.

Si se trata de mapas, redes de telefonía móvil y otros problemas, los grafos correspondientes son «simples»: contienen un número finito de vértices; ninguna arista conecta un vértice consigo mismo; entre dos vértices cualesquiera no media más que una arista; y estas no poseen características adicionales, como un número o un sentido de recorrido asociado. En este caso, sin embargo, sí habremos de asignar una propiedad a cada vértice: su color. Es como si, en cada vértice, alguien hubiera dispuesto un surtido de botes de pintura y tuviéramos que elegir uno de ellos, satisfaciendo la condición de que dos vértices conectados nunca pueden quedar pintados del mismo color.

En 1976, los matemáticos de la Universidad de Illinois en Urbana-Champaign Kenneth Appel y Wolfgang Haken demostraron, con ayuda de John B. Koch, el teorema de los cuatro colores. Este establece que todo grafo plano (es decir, que pueda representarse en un plano sin que sus aristas se crucen) es «4-coloreable»: puede colorearse usando solo cuatro colores. Por tanto, basta con que en cada vértice se encuentre disponible la misma paleta de cuatro tonalidades.

Dado que una parte considerable de la demostración de Appel y Haken se basaba en cálculos por ordenador, su resultado originó un debate sobre hasta qué punto deberíamos confiar en una prueba semejante. La cuestión quedó definitivamente zanjada en 2005, cuando Georges Gonthier, de Microsoft, y Benjamin Werner, de la Escuela Politécnica de París, presentaron una demostración formal del teorema usando el lenguaje de programación Coq.

Listas de colores

En los comienzos de su carrera, Mirzakhani se ocupó de una versión más enrevesada del problema de los cuatro colores: ¿podemos encontrar una coloración válida (es decir, en la que no haya dos vértices adyacentes del mismo color) si la paleta de colores disponibles es distinta en cada vértice?

El problema puede verse como una partida entre dos jugadores: un pintor, que intenta generar una coloración correcta con los colores suministrados en cada vértice, y un malvado proveedor, que selecciona los botes de pintura precisamente con el propósito de impedirlo. Que gane uno u otro dependerá de la estructura del grafo. Decimos que un grafo es «k-coloreable por listas» si el pintor siempre puede ganar, con la condición de que, en cada vértice, el proveedor suministre exactamente k colores (los cuales puede elegir a voluntad).

Todo grafo k-coloreable por listas es automáticamente k-coloreable, ya que colocar los mismos k colores en cada vértice es una de las opciones a disposición del proveedor, y el pintor tiene respuesta para todas ellas. No obstante, lo contrario no es cierto. A modo de ejemplo, consideremos el primer grafo representado aquí, al que llamaremos K_2,4 (véase la figura). Este grafo es 2-coloreable, ya que podemos pintar los vértices de la izquierda de amarillo y los de la derecha de azul. Sin embargo, no es 2-coloreable por listas: resulta sencillo comprobar que, si nuestro proveedor suministra en cada vértice los colores que se muestran en la figura, no podremos encontrar ninguna coloración válida.

En 1996, Mirzakhani presentó un grafo plano (y, por tanto, 4-coloreable en virtud del teorema de Appel y Haken) con 63 vértices que, sin embargo, no era 4-coloreable por listas. Paul Erdös, Arthur L. Rubin y Herbert Taylor ya habían sospechado la existencia de este tipo de grafos en 1979, y Margit Voigt, hoy en la Universidad de Ciencias Aplicadas de Dresde, lo había confirmado en 1993 con una estructura con 238 vértices. La construcción de Mirzakhani supuso una mejora, ya que se las arregló con un número considerablemente menor de vértices. Sin embargo, lo más interesante de su grafo es que —a diferencia del de Voigt— también es 3-coloreable, lo que sirvió para dar respuesta a una pregunta que por entonces aún se encontraba abierta. Por último, Carsten Thomassen, de la Universidad Técnica de Dinamarca, demostró que todo grafo plano es 5-coloreable por listas.

De 17 a 63 vértices

¿Cómo encontró Mirzakhani un grafo plano 3-coloreable que no era 4-coloreable por listas? El elemento principal de su construcción es el grafo B que reproducimos aquí (véase la figura). Sus 17 vértices pertenecen a dos clases: los «interiores», con cuatro vecinos y cuatro colores para elegir (los cuales constituyen la paleta completa de colores disponibles), y los «exteriores», con solo tres colores y tres o siete vecinos.

Puede verse sin gran esfuerzo que este grafo es 3-coloreable: si, por ejemplo, pintamos todos los vértices interiores de rojo y los exteriores alternativamente de amarillo y azul, no incurriremos en ninguna violación de las reglas. Sin embargo, si nos restringimos a las listas de colores que se indican en la figura, no podremos encontrar ninguna coloración válida. Para asegurarse de ello, en principio nuestro pintor tendría que probar una a una todas las combinaciones posibles. No obstante, es posible proceder más rápido de lo que parece, ya que hay conjuntos de coloraciones que se reducen a otras mediante, por ejemplo, una rotación del grafo y un intercambio de colores.

Una vez disponemos de este componente básico, la construcción del grafo de 63 vértices es sencilla. Primero tomamos cuatro copias de B y otro vértice más, el cual conectaremos con todos los vértices exteriores. Ahora elegimos cuatro nuevos colores, a los que llamaremos a, b, c y d, de manera que haya un total de ocho. En la primera copia de B añadimos a todos los vértices exteriores el color a como cuarto de la paleta; en la segunda incluiremos el color b, y así sucesivamente. Por último, el vértice extra recibirá los cuatro nuevos colores, a, b, c y d. De esta manera, obtenemos un grafo plano con 4×17+1=69vértices, en cada uno de los cuales hay una lista de cuatro colores.

El problema de coloración por listas que acabamos de obtener carece de solución. La razón se debe al papel que desempeña el vértice adicional. Supongamos que lo pintásemos del color a. En tal caso, a estaría prohibido para todos los vértices exteriores de la copia a de B. Por tanto, en este subgrafo nos enfrentaríamos al mismo problema de coloración por listas de B que, más arriba, vimos que carecía de solución. Lo mismo ocurre si al vértice adicional le asignamos uno de los colores restantes.

Así pues, el grafo de 69 vértices que hemos construido no es 4-coloreable por listas. En cambio, sí es fácilmente 3-coloreable. Para verlo, basta con aplicar la coloración mencionada antes a las cuatro copias de B y, después, teñir el vértice adicional de rojo, al igual que los vértices interiores.

Ya casi hemos terminado. Efectuando algunos pequeños retoques, podemos unir entre sí las cuatro copias de B y reducir en 6 el número de vértices. Por último, solo tendremos que modificar hábilmente las listas de colores tal y como indicamos aquí (véase la figura). El resultado es un grafo M con 69 – 6 = 63 vértices y listas de cuatro colores, tomadas de un total de cinco.

El nuevo grafo constituye una pequeña joya matemática. Hasta donde sabemos, no ha sido superado aún; es decir, no se conoce ningún grafo de menor tamaño que sea 3-coloreable pero no 4-coloreable por listas. El talento de Mirzakhani queda patente aquí gracias a la sutileza y la sencillez de la construcción.