La conjetura de los girasoles

Los matemáticos han mostrado siempre una gran predilección por los girasoles. Por ejemplo, por la relación entre las espirales a izquierda y derecha de sus semillas, que siguen siempre el patrón marcado por la sucesión de Fibonacci. No es pues de extrañar que Paul Erdös y Richard Rado conjeturaran en 1960 un excitante problema sobre estas plantas, que acaba de tener un avance muy importante.

Paul Erdös.
Richard Rado.

El problema que plantearon Erdös y Rado preguntaba con qué frecuencia uno esperaría encontrar patrones que se asemejaran a los girasoles al analizar una colección muy grande de objetos.

Intentaremos, en los párrafos que siguen, dar una explicación más detallada del problema.

Primero tendremos que definir lo que los matemáticos entendemos por un girasol: “Un girasol de r pétalos es una colección de r conjuntos tales que la intersección de cada par es igual a la intersección de todos”.

Lo que Erdös y Rado probaron en su día es lo que se llama el lema del girasol: para un r fijado, r mayor o igual que 3, cualquier familia de conjuntos de w elementos con al menos wᵂ conjuntos, debe contener un girasol. Si los conjuntos son S₁ , …, Sᵣ , entonces la intersección de todos ellos K = S₁ ∩ … ∩ Sᵣ se llama el núcleo y los complementarios S₁\K, …, Sᵣ\K son los pétalos.

Un ejemplo de girasol.

El resultado se ve en toda su dimensión si pensamos que para 100 puntos necesitaríamos 1001¹⁰⁰ conjuntos, una cantidad enorme. Así que Erdös y Rado, tras probar su lema, conjeturaron que debía haber una cota mucho más baja, que debería existir una constante c(r) tal que si el número de conjuntos de la familia dada era mayor o igual que c(r)ᵂ, entonces esa familia debería contener un girasol.

Ellos pensaban que el problema era muy sencillo, pero no consiguieron probarlo. No ha habido resultados significativos hasta ahora, 60 años después de formularse la conjetura.

La prueba de este resultado es interesante porque combina matemáticas fundamentales con la teoría de la computación. Los autores del artículo en cuestión combinaron sus experiencias en ambos campos y, mediante el uso de las llamadas funciones booleanas, consiguieron encontrar una cota satisfactoria. Basta con (log w)ᵂ para garantizar un girasol.

Recordemos que una función booleana lleva palabras (codificadas con ceros y unos) en un 0 o en un 1. Es decir, funciones f: Bⁿ –> B, donde B = {0, 1}.

Si alguien se pregunta qué interés puede tener un problema como este para el resto de la humanidad que no se dedica a las matemáticas, diremos que este es doble. Por una parte, es un ejemplo de cómo cuando aumentamos los datos aparecen, como venidos de la nada, patrones. Por otra, es un mestizaje entre matemáticas y computación que muestra como esta última descansa precisamente en los fundamentos de las matemáticas más abstractas.

En este vídeo podemos asistir a una conferencia sobre el tema impartida por uno de los autores del citado artículo, Jiapeng Zhang, de la Universidad de Harvard:

Este problema es el objeto del proyecto Polymath número 10: Improving the bounds for the Erdos-Rado sunflower lemma, puesto en marcha el 2 de noviembre de 2015.


Una versión de este artículo fue publicada originalmente en el blog Matemáticas y sus fronteras, de la Fundación para el Conocimiento madrid+d.