El enrevesado problema matemático de los girasoles

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 elevado a w conjuntos, debe contener un girasol. Si los conjuntos son S₁ , …, S elevado a w, entonces la intersección de todos ellos K = S₁ ∩ … ∩ Sᵣ se llama el núcleo y los complementarios S₁\K, …, S elevado a w \K son los pétalos.

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)elevado a w, 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) elevado a 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:

Manuel de León Rodríguez es profesor de Investigación del CSIC, Real Academia de Ciencias, Instituto de Ciencias Matemáticas (ICMAT-CSIC)

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. Este artículo ha sido publicado también en The Conversation .