Problemas Abiertos

Hoy traemos dos problemas de combinatoria geométrica en el corazón de la Teoría de Ramsey que han merecido la atención de matemáticos de la talla de Paul Erdős.

1. El problema del final feliz

El clásico pasatiempos infantil “une los puntos” (donde hay que unir unos puntos numerados con líneas rectas en orden para revelar un dibujo final) puede parecer de lo menos desafiante, y en general de poco interés desde el punto de vista matemático. Sin embargo, todo es cuestión de plantear la pregunta adecuada. Dado un conjunto de puntos en el plano, diremos que están en configuración general si no hay tres de ellos que estén alineados. Llamaremos polígono a la figura cerrada resultante de unir estos puntos (saliendo de cada punto únicamente dos líneas) de manera que no haya dos de ellas que se crucen. Y aún más, diremos que este polígono es convexo si al alargar los segmentos que conforman sus lados, las prolongaciones tampoco cortan a ningún otro lado. De lo contrario, diremos que el polígono es cóncavo.

“Si situamos cinco puntos en el plano en configuración general, siempre es posible seleccionar cuatro de ellos formando un cuadrilátero convexo.” - Esther Klein

Por aquel entonces, ella formaba parte de un club de jóvenes estudiantes, aficionados a las matemáticas, que contaba entre sus miembros a George Szekeres, Paul Erdős o Paul Turán, que luego serían algunos de los matemáticos más conocidos del siglo XX. A los dos primeros les interesó especialmente la cuestión. Tal y como lo cuentan Szekeres y Erdős en su artículo de 1935, Esther Klein dio una prueba de su observación y planteó el problema en general: ¿cuántos puntos en configuración general harán falta para poder dibujar siempre un polígono convexo de $n$ lados? ¿Será siempre posible si partimos de una cantidad suficientemente grande de puntos?

En el mismo artículo, Szekeres y Erdős conjeturaron que para cada número de lados $n$, la mínima cantidad de puntos necesarios en configuración general es precisamente $2^{n-2}+1$. Hoy en día, la conjetura se ha comprobado únicamente hasta $n=6$: en este caso, $2^{6-2}+1=17$ puntos determinan siempre un hexágono convexo. Como prueba de la complejidad del problema, este último resultado fue demostrado tras una búsqueda exhaustiva a ordenador dirigida por el mismo Szekeres y Peters. La prueba fue publicada en un artículo un año después de la muerte del primero en el 2005. De manera similar a la observación original de Klein con $n = 4$, consiguieron reducir el problema a una cantidad finita de casos para la configuración de los puntos y se llegó a que 17 eran suficientes para siempre poder construir un hexágono convexo.

Por otro lado, los esfuerzos de las matemáticas más clásicas han llegado a resultados generales en $n$, acercándose a una prueba definitiva de la conjetura. En su artículo original, Szekeres y Erdős probaron que la cantidad de puntos que harían falta no sólo sería siempre una cantidad finita, sino que era como mucho $\begin{pmatrix} 2n - 4 \\ n - 2 \end{pmatrix}$ un resultado que se obtiene a partir del Teorema de Ramsey. Más tarde, en 1960, lograron demostrar que el $2^{n-2}+1$ de su conjetura es de hecho una cota inferior para el problema. Esto demuestra que, por ejemplo, hay configuraciones de 8 puntos que no permiten dibujar un pentágono convexo ya que $2^{5-2}+1=9>8$.

Con el objetivo de alcanzar la igualdad, desde entonces el punto de foco ha estado en afinar más las cotas superiores. La dificultad se encuentra en que, aunque la teoría de Ramsey proporcione cotas generales, estas son muy alejadas de lo que afirma la conjetura de Erdős y Szekeres. La más precisa que se ha demostrado hasta el momento se publicó en el 2020 y es:

La conclusión insatisfactoria de estos resultados amarga un poco lo que en principio fue conocido como “El problema del final feliz”. Este nombre fue el apodo que le dio Erdős, que estaba convencido que trabajar en ello fue lo que unió a sus dos compañeros Esther Klein y George Szekeres, que se casaron en 1937 y siguieron juntos hasta el fallecimiento de ambos, separados por una hora.

2. Familias intersecadas

Consideremos un conjunto $A$ de $n$ puntos en el plano que, del mismo modo que en el problema anterior, se encuentran en configuración general. Consideremos que unimos ahora todos los puntos de $A$ a través de segmentos. Llamamos familia interesecada a un subconjunto de estos segmentos tal que todos ellos se cortan entre sí.

El problema de las familias intersecadas (en inglés: crossing families) consiste en dar una cota inferior para el tamaño de la familia intersecada más grande entre los segmentos resultantes de unir todos los puntos de un conjunto. Esto es: dado un conjunto de $n$ puntos en configuración general, ¿de qué tamaño debe existir necesariamente una familia intersecada de segmentos uniendo tales puntos? En el siguiente ejemplo, se ha resaltado en rojo la familia intersecada más grande. Como se observa, para este conjunto de seis puntos, la familia es de tamaño tres y, sin embargo, resulta fácil construir conjuntos de igual o mayor cantidad de puntos tales que no hay en ellos familias intersecadas de más de dos segmentos.

En 1994, se publica un trabajo en el que colaboraron siete matemáticos, entre los cuales, como adelantábamos, se incluyen Erdős, y también Daniel J. Kleitman, (asesor y cameo en la archiconocida película El indomable Will Hunting). En esta publicación llegaron a probar la siguiente proposición: para todo conjunto de n puntos en configuración general, existe necesariamente una familia intersecada de al menos $\sqrt{\frac{n}{12}}$ segmentos. Así, podemos asegurar que para un conjunto de 13 puntos existirá una familia intersecada de dos segmentos (esto es, hay segmentos que se cortan), ¡pero no podemos asegurar que existirá una familia intersecada de tres segmentos para conjuntos de 48 puntos! Si no os parece un resultado lo bastante fuerte, es porque no lo es: por algo estamos hablando de un problema abierto. Para llegar a esta conclusión, Erdős y compañía consideraron primero un caso en el que los puntos se distinguen con dos colores y solo pueden unirse puntos de colores diferentes. Con esta restricción lograron probar que existe una familia intersecada de tamaño $\sqrt{\frac{n}{24}}$, e incluso diseñaron un algoritmo relativamente sencillo para construir tal familia. De esta cota deducen después la general sin distinción de colores.

Sin embargo, incluso los propios autores del trabajo tenían fundadas sospechas de que este no era, ni por asomo, el mejor resultado que se podía obtener. Creían que debía existir una cota inferior, incluso lineal (en relación al número de puntos), para la familia intersecada más grande posible. Esta creencia la basaron en que, si generamos conjuntos de puntos aleatorios por ordenador, obtenemos siempre familias intersecadas mayores de lo que la tímida cota de $\sqrt{\frac{n}{12}}$ asegura. ¿El siguiente paso? Se buscan $t > \frac{1}{2}$ y $C > 0$ (idealmente $t = 1$) para los que pueda asegurarse que: para todo conjunto de puntos en el plano en configuración general, al unir todos ellos por segmentos, existe una familia intersecada de tamaño al menos $Cn^{t}$.