Grafos expansores: teoría de redes | Tangente

El grafo es una noción esencial en matemáticas. Aquí nos interesaremos por grafos formados por un número finito de vértices, cada uno de ellos unido a otros vértices mediante una o varias aristas. Estas pueden estar orientadas.

Un grafo puede representar, por ejemplo, una red de comunicación —como la red de tranvías de la ciudad de Zúrich o la red de metro parisina—, la red neuronal de un animal —como el sistema nervioso del gusano Caenorhabditis Elegans, el único animal cuya red se conoce de forma explícita y completa— o incluso un árbol genealógico (véase les Graphes, Bibliothèque Tangente 54, 2015).

Para el tipo de cuestiones y aplicaciones que más nos interesan, supondremos que las aristas de los grafos que aparezcan no están orientadas.

Ciertos grafos, llamados expansores, poseen propiedades tan notables que su propia existencia parece paradójica. De hecho, ¡parece que más de un matemático pensó en un primer momento que no podían existir! Además, tienen aplicaciones extraordinarias en campos muy diversos de las matemáticas y la informática (combinatoria, geometría, aritmética, teoría de nudos…).

La historia de los grafos expansores es enteramente moderna, pues comienza a finales de la década de 1960. Demuestra de forma brillante la unidad de las matemáticas. Incluso hoy, en una época en la que la investigación está cada vez más especializada y a menudo resulta conceptualmente difícil, pueden surgir nuevas ideas revolucionarias que sean elementales y accesibles a un público amplio.

Intuitivamente, un grafo expansor combina dos propiedades que parecen contradictorias: por una parte, permite desplazarse con gran eficacia para unir dos vértices cualesquiera, incluso si de pronto desaparecieran muchas aristas del grafo; por otra, el «coste» de la red no es desmesurado: el número de aristas es relativamente «pequeño» respecto al número de vértices (¡no se trata, por tanto, de unir simplemente todos los vértices entre sí!). Más precisamente, a un grafo G se le puede asociar una determinada constante positiva h(G), llamada número de Cheeger de G (véase el recuadro). Si h(G) > 0, esto significa que el grafo es conexo: siempre es posible unir cualquier par de vértices siguiendo aristas del grafo. Pero cuanto mayor es h(G), más «robusto» es el grafo: por ejemplo, si h(G) vale al menos 1/10, siempre se pueden unir dos partes del grafo de tamaño similar, ¡incluso después de eliminar una de cada diez aristas del grafo!

Decir que se dispone de grafos expansores significa, por tanto, que se sabe construir, para un número N arbitrariamente grande, un grafo con al menos N vértices, en el que cada vértice está unido, como mucho, a un número fijo «pequeño» de otros vértices (por ejemplo, a lo sumo a otros seis vértices), y cuyo número de Cheeger es siempre al menos 1/10 (u otro valor fijo estrictamente positivo).

el número de aristas es muy superior al número de vértices.

basta un solo incidente para cortar la red en dos partes desconectadas.

Durante mucho tiempo, el descubrimiento de los grafos expansores, y en particular la demostración de la existencia de estos objetos, se atribuyó a Mark Semenóvich Pinsker, en relación con un problema de informática teórica. En efecto, en 1973 Pinsker introdujo los grafos expansores como objetos auxiliares que le permitían llevar a buen término cierta construcción, y demostró que una sucesión de grafos cada vez mayores «tomada al azar», en la que cada vértice tiene siempre como máximo cuatro vecinos, posee la propiedad de ser expansora. Sin embargo, mucho más recientemente Larry Guth (re)descubrió un fascinante artículo de Yanis Barzdin y Andréi Kolmogórov, publicado en 1967, unos años antes que el de Pinsker. En él se encuentra no solo una definición esencialmente equivalente a la de los grafos expansores —una diferencia es que Barzdin y Kolmogórov utilizan grafos orientados—, así como la demostración de su existencia, sino también la primera aplicación de los grafos expansores fuera de la combinatoria y la informática teórica. Esta aplicación es, además, especialmente elegante.

Pero la historia continúa. Tanto Barzdin y Kolmogórov como Pinsker demostraron la existencia de grafos expansores… sin proporcionar ejemplos concretos. Se limitaron a afirmar que, si se construye un grafo «sin pensar», hay buenas probabilidades de que sea expansor. Este tipo de construcción aleatoria, aunque es perfectamente aceptable cuando se trata de demostrar la existencia de ciertos objetos, puede plantear dos tipos de problemas.

Para empezar, es posible que, en una aplicación concreta, no se pueda elegir libremente los grafos que se necesitan. De poco sirve saber que existe un grafo expansor si lo que se plantea es comprobar que un grafo concreto posee una buena propiedad de expansión.

Además, desde el punto de vista intelectual siempre resulta natural preguntarse si una construcción aleatoria puede sustituirse por una versión explícita y determinista.

Ya en 1973, Grigori Aleksándrovich Margulis logró construir ejemplos explícitos de grafos expansores. Para ello utilizó un argumento extraordinariamente elegante que establecía un vínculo entre la expansión de ciertos grafos y nociones profundas de álgebra y geometría. Desde entonces se han descubierto muchas otras construcciones, pero la existencia de los grafos expansores sigue teniendo un lado misterioso.

Entre las numerosas aplicaciones de los grafos expansores, dos de las más bellas están directamente relacionadas con el artículo original de Barzdin y Kolmogórov. La primera fue su motivación, y la segunda, ligada a un problema de teoría de nudos, fue descubierta por Mijaíl Gromov y Larry Guth.

Barzdin describe así la motivación en las notas a las obras de Kolmogórov:

Más precisamente, Barzdin y Kolmogórov consideran un grafo finito, con N vértices, en el que cada vértice tiene —digamos— como máximo seis vecinos. Un grafo así siempre puede representarse en el espacio de modo que dos aristas no se crucen, salvo quizá en un vértice común. Si suponemos que los vértices y las aristas están representados «físicamente» mediante bolas o tubos de 1 cm de radio, la cuestión pasa a ser:

¿Cuál es el menor radio R > 0 posible para poder representar el grafo en el espacio dentro de un cubo de lado R?

Barzdin y Kolmogórov obtienen dos resultados:

– Siempre se puede representar un grafo en un cubo de lado aproximadamente N^1/2;

– Si el grafo es expansor (si su constante de Cheeger es «suficientemente grande»), entonces no se puede representar el grafo en un cubo de lado inferior a aproximadamente N^1/2.

Así, Barzdin y Kolmogórov demuestran en cierto modo que los grafos expansores son «lo más complicados posible». Su demostración es relativamente elemental, una vez que se conoce la definición exacta de la constante de Cheeger (véase el recuadro).

El primer resultado de Barzdin y Kolmogórov ya era conocido, de hecho, por algunos especialistas en informática «aplicada», para quienes es importante disponer de un algoritmo eficaz que permita representar físicamente una red en un espacio tridimensional.

El segundo resultado, en cambio, no tendría ningún interés si los grafos expansores no existieran. Por tanto, para comprobar que su enunciado tiene contenido, los dos matemáticos rusos demostraron a continuación la existencia de tales grafos. Sin embargo, también está claro que aquí no es en absoluto necesario construirlos explícitamente ni disponer de ejemplos explícitos.

Cada vértice está unido a algunos otros vértices elegidos al azar.

La segunda aplicación de los grafos expansores es especialmente elegante, en parte porque el enunciado del resultado final no menciona en absoluto ningún grafo. Se trata de una cuestión planteada por Gromov en la década de 1980, relativa a una manera geométrica de medir la complejidad de los nudos. Situemos uno de estos nudos en el espacio. Gromov define la distorsión del nudo como el mayor cociente A/B, donde A es la distancia entre dos puntos del nudo al recorrer el propio nudo, y B es la distancia «en línea recta» entre esos dos puntos.

Ahora, desplacemos el nudo arbitrariamente por el espacio e incluso permitámonos estirarlo cuanto queramos. A cada posición le corresponde una distorsión, y la distorsión intrínseca del nudo es la menor de las distorsiones posibles cuando hacemos que el nudo adopte todas las posiciones posibles. Si un nudo tiene una gran distorsión, significa que es extraordinariamente complicado, pues —con independencia de cómo lo representemos en el espacio— habrá puntos «cercanos» en línea recta que, en realidad, están muy alejados a lo largo del nudo.

Al igual que ocurre con los grafos expansores, la existencia de nudos tan complicados no es en absoluto evidente. Gromov había preguntado:

¿Existen nudos de distorsión arbitrariamente grande?

Gromov y Guth, utilizando las propiedades de expansión de ciertos grafos particulares, logran responder afirmativamente a la pregunta.

Cabe preguntarse si, dado un grafo G explícito, se puede calcular rápidamente su constante de Cheeger h(G) y comprobar así si posee buenas propiedades de expansión. La definición proporciona un método evidente para calcular h(G), pero es extraordinariamente ineficiente: tal como está formulado, requiere un número de operaciones aproximadamente igual a 2^N, donde N es el número de vértices de G. Por suerte, existe otra constante asociada al grafo, mucho más fácil de calcular, que permite al menos obtener estimaciones de la constante de Cheeger h(G). Sin embargo, quedan muchas cuestiones abiertas en este campo en plena… expansión.