Para cada tamaño de grupo, hay un número mínimo de personas que son todos amigos, o todos extraños, entre sí. Pero los números exactos son extremadamente difíciles de calcular. Crédito: La buena brigada/Getty
Si invitas a seis personas a una fiesta, al menos tres de ellas se conocerán, o al menos tres nunca se han visto antes. Pero, ¿a cuántas personas necesita invitar para asegurarse de que un cierto número de ellos sean todos amigos o todos extraños?
Este es un problema de larga data en la combinatoria, la rama de las matemáticas que cuenta las formas en que se puede organizar un conjunto de objetos. La respuesta ideal es sorprendentemente difícil y desconocida excepto en algunos casos simples. Pero un equipo de cuatro matemáticos ahora ha encontrado el mejor límite superior hasta ahora, y la mejora más sustancial a una solución anterior que data de 1935.
«Todos los combinatorialistas se han esforzado mucho en responder a esta pregunta, y creo que es justo decir que es uno de los dos o tres principales problemas abiertos en la combinatoria extrema, o tal vez incluso el verdadero problema principal». tuiteó el matemático Tim Gowers de la Universidad de Cambridge, Reino Unido.
El comentario de Gowers se produjo después de un seminario en Cambridge el 16 de marzo impartido por su colega de departamento Julian Sahasrabudhe. En una divulgación coordinada, dos de los tres compañeros de trabajo de Sahasrabudhe: Robert Morris del Instituto de Matemáticas Puras y Aplicadas (IMPA) en Río de Janeiro, Brasil, su estudiante de doctorado Marcelo Campos y Simon Griffiths de la cercana Pontificia Universidad Católica (PUC) — también describieron sus resultados en seminarios en IMPA y en São Paulo, Brasil, el mismo día. De lo contrario, el trabajo hasta ahora solo se ha presentado en una preimpresión1 de 57 páginas que no ha sido revisada por pares.
fiesteros
El problema del partido fue planteado por primera vez en 1930 por el matemático y lógico británico Frank Ramsey. Una forma de expresar esto es imaginar un número R de personas reunidas en una habitación, cada una de las cuales es amiga o desconocida para las demás. Digamos que estás buscando un grupo de tamaño k que son todos amigos o todos extraños. para una dada kcual es el mas pequeño R(k) ¿Se garantiza que esto satisfaga esta condición? Desde hace tiempo se sabe que cualquier grupo de 6 personas contiene al menos 3 amigos o 3 extraños en común, y que cualquier grupo de 18 contiene al menos 4 amigos o 4 extraños. Pero ya para el número 5, la solución exacta R(5) es desconocido excepto que tiene que estar entre 43 y 48.
El problema se puede mapear en la teoría matemática de las redes, los objetos abstractos formados por nodos y enlaces que los conectan. Cada nodo representará a una persona en el grupo, y dos personas cualesquiera están conectadas por un enlace, que está codificado por colores: rojo si dos personas se conocen y azul si no. Entonces, la pregunta es: ¿qué tan grande debe ser una red para garantizar que contiene al menos un subconjunto completamente azul o completamente rojo de un tamaño determinado?
Los matemáticos Paul Erdős y George Szekeres demostraron en 1935 que R(k) es como mucho 4k. Este límite está lejos de ser óptimo: por ejemplo, para k = 4, da 44 = 256, mientras que se sabe que 18 sería suficiente. Pero la fórmula al menos da un límite superior que se cumple para cualquier k.
La pregunta que ha atormentado a los combinatorialistas desde entonces es si este límite superior se puede hacer más pequeño, si se puede demostrar que existe algún límite. Wk para el cual C es menor que 4. Incluso reducirlo en una pequeña cantidad, dice Sahasrabudhe, “sería una mejora exponencial sobre lo que se sabía. [previously]”, lo que significa que la revisión de los límites W es la mejor manera posible de mejorar los resultados anteriores.
Los cuatro investigadores ahora han demostrado que el límite superior se puede reducir al menos a (3.9995)k. El resultado podría tener ramificaciones importantes para otras áreas de las matemáticas, en particular, para el estudio de redes que tienen un elemento de aleatoriedad, que puede surgir en problemas del mundo real que van desde la epidemiología hasta problemas de optimización y programación, así como para números. .teoría y geometría.
libros y redes
La colaboración de los cuatro investigadores comenzó en 2018, cuando Sahasrabudhe visitó IMPA. Inspirándose en el trabajo sobre el teorema de Ramsey del combinatorialista David Conlon del Instituto de Tecnología de California en Pasadena, el equipo pudo esbozar rápidamente un esquema de cómo sería una prueba. “Esto resultó ser solo el comienzo de un largo camino por delante”, dice Sahasrabudhe.
El trabajo de Conlon sugirió un enfoque que involucraba redes auxiliares conocidas como ‘libros’. Los investigadores comenzaron a crear un algoritmo para construir los libros, pero el desafío era descartar excepciones «patológicas». No fue hasta enero de este año que se sintieron seguros de haber encontrado una forma de solucionar el problema. “A principios de febrero, teníamos una buena idea de cómo podíamos usar estas ideas para impulsar una mejora exponencial”, dice Sahasrabudhe. “Estábamos listos para salir a bolsa a mediados de marzo”.
Su prueba aún no ha sido verificada por otros, advierte. “Ahora que el documento es público, la comunidad entrará en un período de validación, simplificación, asimilación y mejora de nuestro trabajo. Será emocionante ver a dónde otros toman las ideas”.
«Los autores usaron métodos elementales de una manera extremadamente inteligente», dijo Gowers. Naturaleza. Él espera que el resultado se mantenga. “Tenían un fuerte incentivo para ser cuidadosos y, según me dijeron, fueron extremadamente cuidadosos. Los cuatro son matemáticos increíbles que han hecho un trabajo maravilloso en el pasado”. Agrega que la presentación de Sahasrabudhe tenía «una historia muy convincente sobre lo que estaba pasando».
«La prueba era muy diferente del tipo de argumento que estaba tratando de encontrar», agrega Gowers, «y no creo que nunca lo hubiera encontrado».
“Este es un problema que ha resultado persistentemente difícil a pesar de haber sido muy bien estudiado durante casi cien años”, dice Conlon. «Tu progreso es un éxito impresionante».
Añadir comentario