Los grafos expansores

La noción de 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 conectado con 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 de París), 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 también 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, las aristas de los grafos que aparecerán se supondrán no orientadas.

**

**

La expansión en los grafos ======================================================================================================

Algunos grafos particulares, llamados expansores, poseen propiedades tan notables que su propia existencia parece paradójica. De hecho, ¡más de un matemático parece haber pensado inicialmente que no podían existir! Además, tienen aplicaciones extraordinarias en ámbitos 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 espectacular la unidad de las matemáticas. Incluso hoy, en una época en la que la investigación está cada vez más especializada y suele ser conceptualmente difícil, es posible que surjan nuevas ideas revolucionarias que sean elementales y accesibles a un público amplio.

Intuitivamente, un grafo expansor reúne dos propiedades que parecen contradictorias: por una parte, permite desplazarse con gran eficacia para conectar dos vértices cualesquiera, incluso si muchas aristas del grafo desaparecieran de repente; por otra, el «coste» de la red no es desmesurado, es decir, el número de aristas es relativamente «pequeño» en comparación con el número de vértices (¡no se trata, pues, de conectar sencillamente todos los vértices entre sí!). Más precisamente, a un grafo G se le puede asociar una cierta constante positiva h(G), llamada el número de Cheeger de G (véase FOCUS). Si h(G) > 0, esto significa que el grafo es conexo: siempre es posible conectar 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 conectar dos partes de tamaño similar del grafo, ¡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á conectado, como mucho, con un número fijo «pequeño» de otros vértices (por ejemplo, con un máximo de otros seis vértices) y cuyo número de Cheeger es siempre al menos 1/10 (o cualquier otro valor positivo fijo).

Una historia accidentada ==================================================================================================

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 Semenovitch Pinsker, a propósito de un problema de informática teórica. En efecto, Pinsker introdujo en 1973 los grafos expansores como objetos auxiliares que le permitían llevar a buen término una determinada 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 ha (re)descubierto un fascinante artículo de Yanis Barzdin y Andreï Kolmogorov, 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 —con la diferencia de que Barzdin y Kolmogorov 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.

=

Primeras construcciones =================================================================================================

Sin embargo, la historia continúa. Tanto Barzdin y Kolmogorov como Pinsker demuestran la existencia de grafos expansores… sin proporcionar ejemplos concretos. Se limitan a afirmar que, si se construye un grafo «sin pensarlo», tiene muchas probabilidades de ser 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 se trata de comprobar que un grafo particular posee una buena propiedad de expansión.

Además, siempre es natural preguntarse si una construcción aleatoria puede sustituirse por una versión explícita y determinista.

Ya en 1973, Gregori Aleksandrovitch Margulis logró construir ejemplos explícitos de grafos expansores. Para ello utilizó un argumento extremadamente 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 conservando un aspecto misterioso.

Una pequeña cuestión de geometría ==========================================================================================================

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 Kolmogorov. La primera fue su motivación, y la segunda, vinculada a un problema de teoría de nudos, fue descubierta por Mikhaïl Gromov y Larry Guth.

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

Más precisamente, Barzdin y Kolmogorov 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 valor posible de R > 0 para poder representar el grafo en el espacio dentro de un cubo de lado R?

Barzdin y Kolmogorov obtienen dos resultados:

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

–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 N^1/2, aproximadamente.

Así, Barzdin y Kolmogorov demuestran en cierto modo que los grafos expansores son «tan complicados como sea posible». Su demostración es relativamente elemental, siempre que se conozca la definición exacta de la constante de Cheeger (véase FOCUS).

El primer resultado de Barzdin y Kolmogorov ya era conocido, en realidad, por algunos informáticos «aplicados», para quienes es importante disponer de un algoritmo eficaz que permita representar físicamente una red en un espacio tridimensional.

El segundo resultado, por su parte, no tendría ningún interés si los grafos expansores no existieran. Por tanto, para comprobar que no se trata de una afirmación vacía, los dos matemáticos rusos demuestran después la existencia de tales grafos. En cambio, también está claro que aquí no es en absoluto necesario construir explícitamente ni disponer de ejemplos explícitos.

El teorema de Gromov–Guth ====================================================================================================

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 ambos puntos.

Ahora, desplacemos el nudo arbitrariamente en el espacio, permitiéndonos incluso 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 al considerar todas las posiciones posibles del nudo. Si un nudo tiene una gran distorsión, significa que es extraordinariamente complicado, pues —sea cual sea la forma en que lo presentemos en el espacio— habrá puntos «cercanos» en línea recta que, en realidad, están muy alejados a lo largo del nudo.

Como sucede con los grafos expansores, la existencia de nudos tan complicados no es en absoluto evidente. Gromov había preguntado, en efecto:

¿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 extraordinariamente ineficaz: tal como está, 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, siguen abiertas muchas cuestiones relativas a este campo en plena… expansión.