Ha sido un año emocionante en la investigación de la combinatoria. A principios de 2023, los matemáticos quedaron atónitos cuando dos de las mayores problemas en el campo se resolvieron en otros tantos meses. Ahora, una tercera pregunta importante ha surgido con una prueba de 14 páginas "que tiene absolutamente todas las ideas correctas", dijo Mehtaab Sawhney del Instituto Tecnológico de Massachusetts, quien agregó: “Es completamente impactante”.

Esa pregunta trata de los llamados números de Ramsey, cantidades fundamentales que reflejan los límites del posible desorden. Estos números miden el tamaño que pueden alcanzar las colecciones de vértices y aristas, llamadas grafos, antes de que inevitablemente den lugar a un patrón y una estructura.

Los matemáticos han estado estudiando los números de Ramsey, que son notoriamente difíciles de precisar, durante casi un siglo. Al hacerlo, han desarrollado técnicas que han llevado a avances en una variedad de disciplinas más allá de la teoría de grafos, incluida la teoría de números y la criptografía.

Pero la nueva prueba, publicado en línea a principios de este mes, marca un alejamiento de esas técnicas. No solo resuelve un problema que se ha resistido al progreso durante más de 40 años, sino que también presenta una hoja de ruta novedosa sobre cómo los matemáticos podrían abordar los problemas de Ramsey en el futuro.

La planificación de fiestas se encuentra con la teoría de grafos

Para entender qué es un número de Ramsey, imagina que estás organizando una fiesta.

¿A cuántas personas necesitaría invitar para garantizar que habrá un grupo de personas que se conocen entre sí, o un grupo que son todos extraños? Puede codificar esta pregunta en el lenguaje de los gráficos. Asigna un vértice a cada persona. Para n gente, obtienes n vértices. Conecta cada par de vértices con una arista. Colorea el borde rojo si las personas en cuestión se conocen y azul si son extraños.

Un grupo de conocidos mutuos o extraños está representado por una estructura llamada camarilla: un conjunto de vértices conectados por bordes del mismo color. el número de ramsey r(s, t) es el número mínimo de personas que debe invitar para que sea imposible evitar incluir un grupo de s conocidos o t extraños: en el lenguaje de la teoría de grafos, una camarilla roja de tamaño s o una camarilla azul de tamaño t.

Por ejemplo, sabemos que r(4, 5) = 25. Entonces puedes organizar una fiesta con 24 personas, algunas de las cuales se conocen, sin incluir un grupo de cuatro conocidos en común o cinco extraños. Pero agregue una persona más y no podrá evitar crear al menos una de estas estructuras.

Uno de los primeros avances de este año en combinatoria proporcionó un límite superior más estricto para los números de Ramsey "simétricos", donde las camarillas rojas y azules son del mismo tamaño. Con números de Ramsey asimétricos, el tema del nuevo resultado, los matemáticos fijan el tamaño de la camarilla roja y preguntan qué sucede cuando el tamaño de la camarilla azul se vuelve arbitrariamente grande.

Los matemáticos solo han podido calcular exactamente un puñado de los números de Ramsey más pequeños. Demostraron que r(4, 5) = 25 en 1995. Pero nadie sabe el valor de r(4, 6). Del mismo modo, a principios de la década de 1980, mostraron esa r(3, 9) = 36, pero r(3, 10) sigue siendo un problema abierto. (El caso simétrico es igual de difícil: r(4) = 18, pero el valor de r(5) no se conoce.)

Y así, los matemáticos, en cambio, intentan estimar los números de Ramsey, obteniendo límites superior e inferior para sus valores.

En la década de 1990, utilizaron técnicas para generar gráficos aleatoriamente para demostrar que si la camarilla roja se fija en 3 y la camarilla azul se hace cada vez más grande, el tamaño del número de Ramsey crece como el cuadrado del tamaño de la camarilla azul. En otras palabras, r(3, t) es de aproximadamente t².

La nueva prueba pregunta qué sucede cuando el tamaño de la camarilla roja se establece en 4, en lugar de 3. En la década de 1930, se estableció que r(4, t) no crece más rápido que alrededor t³. Pero el mejor límite inferior, encontrado en la década de 1970, es aproximadamente t^5/2 — considerablemente más pequeño.

Los esfuerzos por cerrar la brecha elevando el límite inferior o reduciendo el superior fracasaron durante décadas, hasta que un par de matemáticos agregaron un ingrediente clave.

Oculto a la vista

En 2019, sam mateo, entonces estudiante de posgrado en la Universidad Libre de Bruselas (VUB) buscaba inspiración. Su experiencia era en geometría finita, el estudio de arreglos de puntos, líneas y otras estructuras en espacios especialmente definidos. Pero aunque encontró el trabajo interesante, se sintió limitado por lo estrictas y exactas que debían ser estas construcciones geométricas.

Entonces vio un papel por dos matemáticos, Dhruv Mubayi de la Universidad de Illinois, Chicago y Jacques Verstraete de la Universidad de California, San Diego. Estaban repensando cómo abordar los problemas de Ramsey. Mientras que las técnicas tradicionales involucran la generación aleatoria de gráficos para obtener buenas estimaciones de los números de Ramsey, Mubayi y Verstraete comenzaron con construcciones "pseudoaleatorias" que parecen aleatorias, pero no lo son.

Algo hizo clic en Mattheus. Tal vez, pensó, su perspectiva geométrica podría ayudar. Durante los siguientes dos años, mientras terminaba su trabajo de posgrado, mantuvo esta idea en el fondo de su mente. Luego solicitó una beca Fulbright, que le permitiría realizar un postdoctorado con Verstraete en los EE. UU.

En 2022, poco después de que Mattheus recibiera la beca Fulbright (junto con otra beca), se mudó a UCSD y comenzó a trabajar con Verstraete en r(4,t). Los matemáticos querían elevar el límite inferior para encontrar el límite superior conocido. Para hacer eso, tendrían que encontrar un gráfico con casi t³ vértices que no tenían camarillas rojas de tamaño 4 o camarillas azules de tamaño t.

Para que su prueba funcione, reformularon el problema. Imagine simplemente eliminar todos los bordes azules. El objetivo ahora es encontrar un gráfico sin camarillas rojas de tamaño 4 y sin conjuntos independientes de tamaño t (es decir, conjuntos de t vértices sin aristas).

El trabajo de Mubayi y Verstraete de 2019 implicaba que si puede construir un gráfico pseudoaleatorio sin camarillas rojas de tamaño 4, entonces puede tomar partes aleatorias para obtener gráficos más pequeños sin grandes conjuntos independientes. Esto era precisamente lo que Mattheus y Verstraete querían encontrar. Al comenzar con un gráfico aún más grande, esperaban encontrar un gráfico con casi t³ vértices que cumplen sus criterios. “Dentro de estos gráficos se esconden mejores gráficos de Ramsey”, dijo Verstraete.

Para empezar, el problema era encontrar la construcción pseudoaleatoria correcta.

Los matemáticos tuvieron que llegar allí dando un rodeo. No comenzaron con un gráfico pseudoaleatorio. No comenzaron con un gráfico en absoluto.

En cambio, Mattheus recordó un objeto extraño llamado unital hermitiano, algo con lo que los geómetras finitos tienden a estar muy familiarizados, pero que es poco probable que un matemático que trabaje en combinatoria se encuentre alguna vez.

Un unital hermitiano es un conjunto especial de puntos en una curva, junto con líneas que pasan por esos puntos en configuraciones específicas. Fundamentalmente, también se puede representar como un gráfico que consta de muchas camarillas grandes pero que apenas se superponen.

Este gráfico es bien conocido y muchas de sus propiedades han sido estudiadas. Pero nunca se había considerado en el contexto de los problemas de Ramsey. “Es muy específico para este negocio de geometría finita”, dijo Mattheus.

El gráfico puede no parecer útil a primera vista, ya que contiene muchas clicas grandes. Pero una característica clave del unital hermitiano es que solo contiene camarillas de tamaño 4 cuyos vértices se agrupan de forma atípica. Debido a esta propiedad, fue relativamente fácil para los matemáticos destruir esas camarillas no deseadas eliminando bordes al azar.

Estas eliminaciones les dieron un nuevo gráfico sin camarillas de tamaño 4, pero aún contenía grandes conjuntos independientes. Mattheus y Verstraete ahora necesitaban demostrar que este gráfico era pseudoaleatorio. Al hacerlo, finalmente pudieron usar la prueba de 2019 como esperaban. Tomaron subgrafos al azar con aproximadamente t³ vértices, y podría garantizar que esos subgrafos estaban libres de conjuntos independientes de tamaño t.

Esto completó la prueba. “Esta construcción es absolutamente hermosa”, dijo Sawhney.

El trabajo anuncia un cambio en la forma en que los matemáticos piensan sobre los problemas de Ramsey. “Es muy, muy natural tratar de usar la aleatoriedad para tratar de impulsar las cosas y obtener el mejor salto posible”, dijo david conlon del Instituto de Tecnología de California. “Pero lo que esto realmente muestra es que la aleatoriedad solo te lleva hasta cierto punto”.