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 ¨Cdenominado n¨²cleo¨C 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