En las estructuras muy grandes siempre aparecen patrones

En los últimos tiempos las matemáticas están viviendo un impulso interdisciplinar incentivado por la colaboración de los matemáticos con físicos, ingenieros y, como es el caso que nos ocupa, informáticos. Este esfuerzo ha dado frutos recientemente en la llamada conjetura del girasol, un problema de combinatoria formulado hace 60 años por los matemáticos Paul Erdös y Richard Rado.

Veamos con un ejemplo de que trata el problema. Partimos de tres conjuntos de números del mismo tamaño (cinco): {1,2,5,8,12}, {2,6,7,8,14} y el {2,3,4,8,11}. Los tres 5-conjuntos tienen elementos comunes, el 2 y el 8. Así, la intersección común de los tres conjuntos tiene tamaño 2. Ningún elemento excepto el 2 y el 8 pertenece a dos o más 5-conjuntos. Si dibujamos los tres 5-conjuntos en forma de flor, obtenemos un girasol: los pétalos son los tres 5-conjuntos y el centro del girasol –denominado núcleo– es la intersección común. También consideramos como girasoles los casos degenerados en los que los pétalos no tienen elementos comunes. En este caso, tendrán el núcleo vacío.

Podemos dar así la definición general de un girasol: es una familia de conjuntos (los pétalos), con el mismo número de elementos, que cumplen que si un elemento pertenece a dos de ellos, entonces este elemento pertenece a todos (y serán los elementos comunes, que definen el núcleo del girasol). Esto quiere decir que no puede haber dos pétalos con elementos comunes que no estén en el núcleo del girasol.

El estudio de girasoles se inició con el trabajo de Paul Erdös y de Richard Rado en los años 60 del siglo pasado. Ambos demostraron que en cualquier gran colección de conjuntos (no importa como estén escogidos) aparece siempre este tipo de configuración. De manera más formal, el lema de los girasoles de Erdös y Rado afirma que, fijado el tamaño de los subconjuntos, k, y el número de pétalos, r (en el ejemplo anterior eran k=5 y r=3), entonces hay un número, f(k,r), que depende de estos dos valores, para el que se puede afirmar que toda familia de k-conjuntos con más de f(k,r) elementos debe contener un girasol con r pétalos. Dicho de otro modo, si tenemos más de f(k,r) k-conjuntos, será imposible evitar la existencia de un girasol con r pétalos. Por ejemplo, si k=5 y r=3 se sabe que f(k,r)=160. Por lo tanto, si tomamos 160 (o más) 5-conjuntos como queramos, siempre aparecerá al menos un girasol con tres pétalos.

Este resultado puede interpretarse como que en familias de conjuntos muy grandes no puede existir un desorden absoluto, ya que es inevitable que existan girasoles, que son objetos estructurados. Sin embargo, la prueba de Erdös y Rado no ofrece una buena estimación de lo que significa muy grandes, es decir, de la función f(k,r). Precisamente la llamada conjetura del girasol establece una buena estimación para dicha función: ésta ha de ser menor que c(r)k para una función c(r) que depende únicamente de r.

Desde el año 1960 nadie ha dado con el ingrediente fundamental para la resolución de la conjetura. En 2009 el medallista Fields Timothy Gowers propuso en su blog estudiarla en el marco de los proyectos colaborativos Polymath. Estos proyectos pretenden atacar problemas abiertos en distintas áreas de las matemáticas empleando la discusión en línea (en la web de Polymath). En el año 2015, después de grandes éxitos de la iniciativa en otros problemas, el profesor israelí Gil Kalai animó de nuevo a trabajar en el problema a través de su blog, involucrando a importantes matemáticos. En los comentarios del post discuten del tema el mismo Gowers y el medallista Fields Terence Tao.

A finales de agosto de 2019, para sorpresa de la comunidad matemática, apareció en el repositorio arXiv el primer avance significativo en muchos años de este problema

A finales de agosto de 2019, para sorpresa de la comunidad matemática, apareció en el repositorio arXiv el primer avance significativo en muchos años de este problema, que reducía significativamente el valor de f(k,r). El trabajo, propuesto en colaboración entre matemáticos e informáticos teóricos, utiliza una combinación astuta de técnicas probabilísticas y herramientas del área de la complejidad computacional y ha conseguido reducir por primera vez de manera significativa el orden de magnitud obtenido por Erdös y Rado de la función f(k,r). La colaboración interdisciplinar ha sido la clave del éxito.

Aunque no resuelve la conjetura ofrece un abanico de nuevas técnicas que pueden abrir un camino a la resolución final del problema, y es una contribución relevante a la denominada Teoría de Ramsey. Esta disciplina explora la aparición de patrones en estructuras muy grandes de diverso tipo.

Juanjo Rue es profesor del Departamento de Matemáticas de la Universitat Politècnica de Catalunya, y miembro de la Barcelona Graduate School of Mathematics.

Edición y coordinación: Ágata A. Timón García-Longoria (ICMAT)

Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: "Un matemático es una máquina que transforma café en teoremas".

Puedes seguir a Materia en Facebook, Twitter, Instagram o suscribirte aquí a nuestra newsletter