El 15 de marzo, intrigantes anuncios de seminarios enviaron rumores a través del campo de la combinatoria, el estudio matemático de contar. Tres colaboradores tenían previsto dar charlas coordinadas al día siguiente. julian sahasrabudhe se dirigiría a matemáticos en Cambridge, Inglaterra, mientras Simón Griffiths compartiría la noticia en Río de Janeiro y marcelo campos en São Paulo. Las tres charlas tenían títulos idénticos y resúmenes crípticos de dos oraciones que hacían referencia a "progresos recientes en un viejo problema de Erdős". Mientras Paul Erdős, matemático húngaro fallecido en 1996, planteaba cientos de problemas durante su carrera, los combinatoristas adivinaron rápidamente el tema específico del que el trío planeaba hablar. Corrieron rumores sobre algo llamado el número de Ramsey, una de las cantidades más difíciles de calcular en todas las matemáticas.

Los números de Ramsey han generado toda una disciplina llamada teoría de Ramsey, que busca patrones ineludibles en una amplia gama de sistemas.

Por ejemplo, supongamos que intenta repartir todos los números enteros entre varios cubos y desea evitar colocar secuencias de números espaciados uniformemente en cualquiera de los cubos. La teoría de Ramsey muestra que fallará (a menos que tenga infinitos cubos). La teoría se puede aplicar a casi cualquier cosa que puedas contar. Su lección central es que “no se puede crear un sistema completamente caótico”, dijo Benny Sudakov, matemático del Instituto Federal Suizo de Tecnología de Zúrich.

El número de Ramsey cuantifica qué tan grande debe ser un ejemplo paradigmático antes de que inevitablemente surjan patrones particulares. Pero a pesar de su centralidad, nadie ha podido calcular el número de Ramsey para todos excepto para el instancias más simples. Lo mejor que han podido hacer es encontrar límites (o límites) sobre lo que podría ser. Incluso entonces, el límite superior establecido por primera vez por Erdős y un colaborador hace casi un siglo apenas se había movido.

Luego, en los seminarios del 16 de marzo y en un artículo publicado más tarde esa noche, los investigadores anunciaron que habían mejorado el límite superior del número de Ramsey en una cantidad exponencial.

“Estaba anonadado”, dijo Yuval Wigderson, matemático de la Universidad de Tel Aviv, al enterarse del nuevo resultado. “Estuve literalmente temblando durante media hora o una hora”.

Las líneas del partido

La teoría de Ramsey comúnmente hace preguntas sobre los números enteros o sobre los gráficos. Un gráfico, en este contexto, se refiere a conjuntos de puntos llamados nodos, conectados por líneas llamadas aristas, que pueden tener propiedades como longitud o, como en el caso de los números de Ramsey, color.

Un gráfico completo es complicado y simple: cada nodo está conectado a todos los demás nodos. El número de Ramsey describe cuántos nodos debe contener un gráfico completo para que se le obligue a tener una estructura particular. Digamos que a los bordes de un gráfico completo se les asigna uno de dos colores: rojo o azul. Y supongamos que intenta colorear los bordes de una manera que evite conectar un grupo de nodos con bordes del mismo color. En 1930, Frank Ramsey demostró que si un gráfico es lo suficientemente grande, es imposible evitar la creación de lo que los matemáticos llaman una camarilla monocromática: un grupo de nodos cuyos bordes comunes son todos rojos o azules.

¿Qué tan grande, exactamente, debe ser un gráfico antes de que una camarilla monocromática se vea obligada a emerger? La respuesta depende del tamaño de la camarilla. Ramsey demostró que existe un número, ahora llamado número de Ramsey, que representa el número mínimo de nodos para los que debe existir una camarilla monocromática de un tamaño determinado, sin importar el color de los bordes.

Pero el tamaño del número de Ramsey es difícil de precisar. En 1935, cinco años después de que Ramsey demostrara que existe, Erdős y George Szekeres proporcionaron un límite superior nuevo y más estricto sobre qué tan grande es el número de Ramsey para una camarilla de un tamaño determinado. Pero desde entonces, los matemáticos apenas han podido mejorar el cálculo de Erdős y Szekeres.

Para obtener una mejor intuición de lo que esto significa, considere un ejemplo clásico, en el que los nodos representan invitados en una fiesta. Colorea el borde entre dos invitados de rojo si se han conocido antes, y de azul si no lo han hecho. Puede elegir el tamaño de camarilla que desee: invite a suficientes personas a la fiesta y no puede evitar invitar a un grupo de personas que se conocen entre sí (una camarilla en varios sentidos de la palabra) o invitar a un grupo de personas que nunca se han conocido antes.

“Lo más simple que puedes tener en un gráfico es una camarilla monocromática”, dijo María Chudnovsky, matemático de la Universidad de Princeton. “Es sorprendente que en cada gráfico enorme puedas encontrar uno grande de esos. No está del todo claro”.

Los primeros números de Ramsey son relativamente simples de calcular. Digamos que desea saber el tamaño del gráfico más pequeño que inevitablemente debe contener una camarilla de tamaño dos, o R(2) para los matemáticos. Dado que un gráfico completo con dos nodos son solo dos nodos conectados por una arista, y esa arista tiene que ser roja o azul, R(2) es 2. Más generalmente, R(k), o el número de Ramsey de k, es el número mínimo de nodos más allá del cual un gráfico no puede evitar contener una camarilla de tamaño k.

No es tan difícil demostrar que el número de Ramsey para una camarilla de tamaño 3, o R(3), es 6 (ver gráfico). Pero no fue hasta 1955 que R(4) se fijó en 18. R(5) sigue siendo desconocido: es al menos 43 y no más grande que 48. Aunque estos números son pequeños, no se puede examinar todos los colores posibles. de la pregunta, dijo David Conlon del Instituto de Tecnología de California. Considere la cantidad de colores en un gráfico completo con 43 nodos. “Tienes 903 aristas; cada uno de ellos se puede colorear de dos maneras”, explicó. “Así que obtienes 2⁹⁰³, que es astronómicamente grande”.

A medida que aumenta el tamaño de la camarilla, la tarea de precisar el número de Ramsey se vuelve más difícil. Erdős bromeó diciendo que una guerra total con extraterrestres matemáticamente exigentes sería más fácil que intentar averiguar R(6), que está entre 102 y 165. El rango de incertidumbre crece rápidamente: según estimaciones compiladas por Stanisław Radziszowski, R(10) podría ser tan pequeño como 798 y tan grande como 23,556. Pero los objetivos de los matemáticos van mucho más allá del número de Ramsey de 10. Quieren una fórmula que dé una buena estimación de R(k), incluso —o especialmente— cuando k es extremadamente grande.

“No conozco a nadie en combinatoria que no haya pensado en este problema al menos un poco”, dijo Wigderson. “Creo que este problema es realmente especial”.

orden en la corte

Frank Ramsey fue una figura ecléctica y brillante que murió cuando tenía 26 años. Apenas unas semanas antes de morir, el Actas de la Sociedad Matemática de Londres publicado el papel en el que introdujo los números de Ramsey. Ese trabajo ni siquiera era sobre gráficos, sino sobre un problema de lógica matemática. Ramsey demostró que un enunciado que satisface ciertas condiciones tiene que ser verdadero al menos algunas veces. Una de esas condiciones era que hubiera un gran "universo" de escenarios para probar la afirmación. Como trampolín para este resultado, Ramsey demostró que el número de Ramsey es finito.

Cinco años más tarde, Erdős y Szekeres demostraron que el número de Ramsey de k es menos de 4^k. Y 12 años después de eso, Erdős mostró que es más grande que $latex sqrt{2}^k$. Para hacer eso, calculó las posibilidades de que un gráfico con bordes de colores aleatorios contenga una camarilla monocromática. Esta técnica "probabilística" se volvió enormemente influyente en la teoría de grafos. También atrapó a R(k) entre dos porterías que crecen exponencialmente: $latex sqrt{2}^k$ y $latex 4^k$.

A medida que pasaban las décadas, numerosos matemáticos intentaron reducir la brecha entre los posibles valores del número de Ramsey. Algunos tuvieron éxito: en 1975, Joel Spencer duplicó el límite inferior. y una serie de artículos de Con Lon, andres thomason y ashwin sah empujado hacia abajo el límite superior por un factor de aproximadamente $latex 4^{log(k)^2}$ para 2020. Pero en comparación con los tamaños de los límites del número de Ramsey, estos ajustes fueron pequeños. Por el contrario, cualquier reducción al 4 en la fórmula de Erdős y Szekeres R(k) <4^k sería una mejora exponencial, creciendo rápidamente como k se hace más grande.

"Parece una pequeña y linda pregunta", dijo rober morris, matemático del IMPA, el Instituto de Matemáticas Puras y Aplicadas de Brasil, en Río de Janeiro, coautor del nuevo resultado con Campos, Griffiths y Sahasrabudhe. “Es un poco sutil de apreciar. Pero a la gente realmente le importa”. Esto es posiblemente un eufemismo. “Si lo hubieran probado en 1936, la gente habría dicho: OK, entonces, ¿cuál es el problema?”. dijo Béla Bollobás, quien fue asesor de doctorado de Morris y Sahasrabudhe en la Universidad de Memphis. “Desde entonces, se ha demostrado que es un problema muy grande, porque a lo largo de los años, se han escrito varios miles de artículos sobre diversas variantes del problema de Ramsey”. Como liana yepremyan, matemático de la Universidad de Emory, dijo: "Los números de Ramsey crean ese puente entre la combinatoria, la probabilidad y la geometría".

Teoría de juego

 En agosto de 2018, Sahasrabudhe fue becario postdoctoral de Morris en IMPA. Los dos esperaban comenzar un nuevo proyecto con Griffiths, quien enseña en la cercana Pontificia Universidad Católica, cuando un artículo de Conlon llamó su atención. El artículo esbozaba una posible estrategia para conseguir una mejora exponencial del número de Ramsey. Griffiths, Morris y Sahasrabudhe comenzaron a jugar con la idea.

“Fue muy emocionante al principio”, recordó Sahasrabudhe. Solo les tomó alrededor de un mes, dijo, diseñar un bosquejo de su argumento.

Su plan era construir sobre las ideas utilizadas en la prueba original de Erdős y Szekeres de que $latex R(k) < 4^k$. Para probar que el número de Ramsey es como máximo $latex 4^k$, imagina jugar un juego en un gráfico completo con $latex 4^k$ nodos. El juego tiene dos jugadores. Primero, tu oponente colorea cada borde de rojo o azul, con la esperanza de colorear los bordes de una manera que evite crear una camarilla monocromática de k nodos

Una vez que tu oponente termine de colorear, es tu trabajo buscar una camarilla monocromática. Si encuentras uno, ganas.

Para ganar este juego, puedes seguir una estrategia simple. Ayuda pensar (metafóricamente) en clasificar sus nodos en dos cubos. Los nodos en un cubo formarán una camarilla azul y los nodos en el otro formarán una camarilla roja. Se eliminarán algunos nodos, y nunca más se volverá a saber de ellos. Al principio, ambos cubos están vacíos y cada nodo es candidato para entrar en cualquiera de ellos.

Comience con cualquier nodo que le guste. Luego mira los bordes de conexión. Si la mitad o más de los bordes son rojos, elimine todos los bordes azules y los nodos a los que están conectados. Luego ponga su elección original en el cubo "rojo". Todos los bordes rojos de este nodo todavía están vivos y bien, adheridos al resto del gráfico desde el interior del cubo. Si más de la mitad de los bordes son azules, elimina de manera análoga los bordes y nodos rojos y los coloca en el cubo azul.

Repita hasta que no le queden nodos. (Dado que el gráfico está completo, cada nodo restante en cualquier punto se conecta a ambos cubos hasta que se coloca en uno de ellos).

Cuando termines, mira dentro de los cubos. Debido a que un nodo entró en el cubo rojo solo después de que se eliminaron sus vecinos azules, todos los nodos en el cubo rojo están conectados por bordes rojos, forman una camarilla roja. Asimismo, el cubo azul forma una camarilla azul. Si su gráfico original tiene al menos $latex 4^k$ nodos, es posible probar que uno de estos cubos debe contener al menos k nodos, garantizando una camarilla monocromática en el gráfico original.

Este argumento es ingenioso y elegante, pero te hace construir dos camarillas, una azul y otra roja, aunque realmente solo necesitas una. Sería más eficiente ir siempre en rojo, explicó Conlon. Según esta estrategia, elegiría un nodo en cada paso, borraría sus bordes azules y lo arrojaría al cubo rojo. El cubo rojo se llenaría rápidamente y acumularías una camarilla roja de k nodos en la mitad del tiempo.

Pero su estrategia tiene que funcionar para cualquier coloración rojo-azul, y es difícil saber si siempre puede encontrar un nodo con muchos bordes rojos. Entonces, siguiendo la sugerencia de Conlon, se corre el riesgo de encontrarse con un nodo que casi no tiene bordes rojos adjuntos. Eso lo obligaría a eliminar una gran parte del gráfico a la vez, dejándolo luchando para construir su camarilla antes de quedarse sin nodos. Para llevar a cabo la sugerencia de Conlon, Griffiths, Morris y Sahasrabudhe necesitaban probar que este riesgo era evitable.

Un examen de libro abierto

Al actualizar su juego, Griffiths, Morris y Sahasrabudhe siguieron una ruta un poco más tortuosa. En lugar de construir una camarilla monocromática directamente lanzando nodos en sus baldes rojos y azules, primero se enfocaron en construir una estructura llamada libro rojo.

Un libro, en la teoría de grafos, se compone de dos partes: hay una camarilla monocromática, llamada "columna vertebral", y un segundo grupo distinto de nodos llamados "páginas". En un libro rojo, todos los bordes que conectan los nodos dentro del lomo son rojos, al igual que los bordes que unen el lomo a las páginas. Sin embargo, los bordes que conectan los nodos dentro de las páginas pueden ser cualquier combinación de colores. Conlon había señalado en su artículo de 2018 que si puede encontrar una camarilla roja dentro de las páginas de un libro, entonces podría combinarla con el lomo para obtener una camarilla roja más grande. Esto le permite descomponer una búsqueda de una camarilla roja grande en dos búsquedas más fáciles. Primero, busca un libro rojo. Luego busque una camarilla en las páginas del libro.

Griffiths, Morris y Sahasrabudhe querían ajustar el algoritmo ganador del juego para que construyera un libro rojo en lugar de una camarilla roja. Aunque se decidieron por este plan solo unas semanas después de su proyecto, les llevaría años hacerlo funcionar. Todavía necesitaban evitar la amenaza de perder todos sus bordes rojos.

“Estuvimos estancados durante mucho tiempo”, dijo Campos, quien se unió al proyecto en 2021.

Este enero, los cuatro matemáticos acordaron cambiar a otra versión del problema. Esa versión suena más complicada, pero resultó ser más fácil.

Todo el tiempo, el equipo se había centrado en el número R de Ramsey (k), también conocido como el número de Ramsey "diagonal". Una gráfica de tamaño R(k) debe contener k nodos, todos conectados por bordes del mismo color, pero no importa si ese color es rojo o azul. Por otro lado, el número de Ramsey “fuera de la diagonal” R(k, l) mide qué tan grande debe ser un gráfico antes de que contenga una camarilla roja con k nodos, o una camarilla azul con l nodos. En lugar de seguir solucionando el problema de la diagonal, el grupo decidió probar la versión fuera de la diagonal. Esto resultó revelador.

“Durante mucho tiempo, parecía que todas las puertas que empujabas estaban cerradas con cerrojo o, al menos, eran bastante difíciles de atravesar”, dijo Griffiths. “Y después de ese cambio, sentías que todas las puertas estaban abiertas. De alguna manera, todo parecía funcionar”. En la versión fuera de la diagonal, encontraron una manera de eliminar un montón de bordes azules a la vez siguiendo un protocolo particular, lo que aumentó la densidad de los bordes rojos y condujo a un límite mejorado en el número de Ramsey fuera de la diagonal. Este método, denominado argumento de “incremento de densidad”, se había utilizado previamente para resolver otros problemas importantes en combinatoria, pero no se había utilizado en el problema del número de Ramsey.

Luego, los cuatro matemáticos usaron el nuevo límite en el número de Ramsey fuera de la diagonal para despejar el camino para el resultado diagonal. A principios de febrero, finalmente habían reducido el límite del número de Ramsey en un factor exponencial, un logro que los matemáticos habían buscado durante casi un siglo. Y lo hicieron modernizando la misma línea argumental que habían planteado Erdős y Szekeres en 1935.

épsilon, épsilon

Luego de las charlas del 16 de marzo, los asistentes comenzaron a confirmar los rumores. Fotos de la charla de Sahasrabudhe circularon a través de llamadas telefónicas y mensajes privados, incluso en un mensaje vago pero sugerente en el blog del matemático Gil Kalai. Campos, Griffiths, Sahasrabudhe y Morris afirmaron haber demostrado que $latex R(k) < 3.993^k$. Esa noche, los cuatro autores publicó su artículo en línea, permitiendo a los matemáticos ver la nueva prueba por sí mismos.

“Creo que muchos de nosotros no esperábamos ver tal mejora en nuestra vida, esencialmente”, dijo Matija Bucic, matemático de la Universidad de Princeton y del Instituto de Estudios Avanzados. “Creo que es un resultado absolutamente asombroso”.

Muchos expertos tienen la esperanza de que, con la caída de la barrera exponencial, sigan rápidamente más avances. Los autores del nuevo artículo intencionalmente no llevaron su método al límite, para evitar nublar su argumento con detalles innecesarios. “Estoy muy interesado en hasta dónde puede llegar realmente el método, porque no tengo idea”, dijo Campos.

“Es una prueba absolutamente ingeniosa, absolutamente maravillosa y un avance genuino. Así que ahora espero que se abran las compuertas”, dijo Bollobás. “Estoy convencido de que dentro de tres años el debate será sobre posibles mejoras. ¿Podemos mejorar 3.993 a 3.9? ¿Quizás a 3.4? ¿Y qué hay de 3?

La nueva prueba tiene 56 páginas y la comunidad de combinatoria tardará semanas en verificar cada detalle por completo. Pero los colegas son optimistas. “Este grupo de autores, son personas muy serias. Y son personas que son muy, muy buenas en cosas muy técnicas”, dijo Wigderson.

Cuando se trata de sus colaboradores, Griffiths está de acuerdo. “Es un privilegio trabajar con gente brillante, ¿no? Y creo que eso es por lo que me siento muy agradecido”, dijo. “Si me lo hubieran dejado a mí, podría haber tomado otros cinco años para obtener los detalles correctos”.