Resuelven un problema matemático de casi un siglo

Investigadores descubrieron el secreto de los números de Ramsey

Los investigadores Jacques Verstraete, de la Universidad de California en San Diego, y Sam Mattheus, de la Universidad Libre de Bruselas, resolvieron el problema matemático de Ramsey o r(4,t) que ha dejado perplejo a los matemáticos del mundo desde la década de 1930.

Fiesta con invitados

El problema de Ramsey más conocido y sencillo es el denominado ‘teorema de amigos y extraños’. Para entenderlo debemos imaginar una fiesta en la que consideremos cuántas personas invitar con una cierta condición. Esto se puede escribir como ‘r(s,t)’; donde ‘r’ es el número mínimo de personas necesarias en la fiesta para que ‘s’ personas se conozcan o ‘t’ no sean completamente desconocidas entre sí.

La respuesta a r(3,3) es muy simple, pues es igual a 6. “Es un hecho natural, una verdad absoluta”, afirma Verstraete. “No importa cuál sea la situación o qué seis personas elijas: encontrarás tres personas que se conocen entre sí o tres personas que no se conocen. Es posible que puedas encontrar más, pero te garantizamos que habrá al menos tres en una camarilla u otra”, agrega el matemático.

Teoría aplicada a los gráficos

En el lenguaje matemático el teorema de Ramsey, r(s,t), se aplica a los gráficos: donde ‘s’ son los puntos que se unen con rectas y ‘t’ son los puntos a los que no los conectan rectas que podemos encontrar dentro de un gráfico cualquiera. La teoría de Ramsey señala que es seguro encontrar algún tipo de orden dentro de una gráfica suficientemente grande, ya sea un conjunto de puntos (camarillas) sin líneas entre ellos u otra camarilla unida por todas las líneas posibles entre ellos.

La solución de r(4,4) es 18 y se demuestra utilizando un teorema creado por los matemáticos Paul Erdös y George Szekeres en la década de 1930. Los problemas de Ramsey con más elementos son sencillos de plantear, pero las posibles soluciones son casi infinitas. Actualmente la solución de r(5,5) aún se desconoce. Los expertos plantean que, si suponemos que la respuesta es 45 puntos, habría que considerar un número prácticamente absurdo de gráficos, equivalente a un 1 seguido de 234 ceros.

“Debido a que estos números son muy difíciles de encontrar, los matemáticos buscan estimaciones”, explicó Verstraete. “Esto es lo que Sam y yo hemos logrado en nuestro trabajo reciente. ¿Cómo encontramos no la respuesta exacta, sino las mejores estimaciones de cuáles podrían ser estos números de Ramsey?”.

Recompensa a quien lo resuelva

El problema r(4,t) es una conjetura de Erdös, quien ofreció 250 dólares a la primera persona que pudiera resolverlo. Verstraete vio por primera vez el problema en un libro escrito por dos profesores de la UC en San Diego, Fan Chung y el fallecido Ron Graham. “Mucha gente ha pensado en r(4,t); ha sido un problema abierto durante más de 90 años”, puntualizó Verstraete. Se necesitó un gráfico pseudoaleatorio de geometría finita, llamado ‘configuración de O’Nan’, para resolver un problema de Ramsey de larga data.

Si quieres una fiesta en la que siempre habrá cuatro personas que se conocen o ‘t’ personas que no se conocen, necesitarás una cantidad de personas presentes aproximadamente igual a ‘t’ elevado al cubo. El artículo se está revisando actualmente en Annals of Mathematics y su archivo de preimpresión se encuentra en arXiv.

Perseverar

“Realmente nos llevó años resolverlo”, afirmó Verstraete. “Y hubo muchas ocasiones en las que nos quedamos estancados y nos preguntamos si seríamos capaces de resolverlo. Pero uno nunca debe darse por vencido, no importa cuánto tiempo tome”, subrayó. “Si descubres que el problema es difícil y estás estancado, significa que es un buen problema. Fan Chung dijo que un buen problema se defiende. No se puede esperar que simplemente se revele”, recalcó. “Recibí una llamada de Fan diciendo que me debe 250 dólares“, añadió el matemático.