En 1850, Thomas Penyngton Kirkman, matemático cuando no cumplía con su principal responsabilidad como vicario de la Iglesia de Inglaterra, describió su “problema de colegialas”: “Quince señoritas en una escuela salen de tres en tres durante siete días seguidos: es se requiere que los arreglen diariamente, de modo que dos no caminen dos veces de frente”.
Para un matemático moderno, este tipo de problema se imagina mejor como una hipergrafía: un conjunto de nodos reunidos en grupos de tres o más. Las 15 colegialas son nodos, y cada grupo de “tres en fondo” se puede considerar como un triángulo, con tres líneas o aristas, que conectan tres nodos.
El problema de Kirkman esencialmente pregunta si hay una disposición de estos triángulos que conecte a todas las colegialas entre sí, pero con la restricción adicional de que no hay dos triángulos que compartan un borde. Compartir bordes implicaría que dos colegialas tienen que caminar juntas más de una vez. Esta restricción significa que cada niña camina con dos nuevos amigos todos los días durante una semana, de modo que cada pareja posible se junta exactamente una vez.
Este problema y otros similares han seducido a los matemáticos durante los casi dos siglos desde que Kirkman planteó su pregunta. En 1973, el legendario matemático Paul Erdős planteó uno similar. Preguntó si es posible construir una hipergrafía con dos propiedades aparentemente incompatibles. Primero, cada par de nodos debe estar conectado exactamente por un triángulo, como con las colegialas. Esta propiedad hace que el gráfico sea denso con triángulos. El segundo requisito obliga a que los triángulos se extiendan de forma muy precisa. (Específicamente, requiere que para cualquier grupo pequeño de triángulos, haya al menos tres nodos más que triángulos). «Tienes este comportamiento ligeramente contradictorio donde tienes un objeto general denso que no tiene partes densas», dijo David Conlon. , matemático del Instituto de Tecnología de California.
Este enero, en una intrincada prueba de 50 páginas, cuatro matemáticos demostraron que siempre es posible construir una hipergrafía de este tipo siempre que tenga suficientes nodos. “La cantidad de tecnicismos por los que pasaron solo para obtener esto fue increíble”, dijo Allan Lo, matemático de la Universidad de Birmingham. Conlon estuvo de acuerdo: «Es un trabajo realmente impresionante».
El equipo de investigación construyó un sistema que satisfizo los requisitos diabólicos de Erdős al comenzar con un proceso aleatorio para elegir triángulos y diseñarlo con extremo cuidado para satisfacer sus necesidades. “La cantidad de modificaciones difíciles que se incluyen en la prueba es realmente asombrosa”, dijo Conlon.
Su estrategia fue construir cuidadosamente la hipergrafía a partir de triángulos individuales. Por ejemplo, imagina nuestras 15 colegialas. Dibuja una línea entre cada par.
