En 1850, Thomas Penynton Kirkman, matemático cuando no cumplía con su responsabilidad principal como vicario en 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 necesario arreglar ellos cada día, de modo que ninguno de los dos ande 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 [ellos] 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.
El objetivo aquí es trazar triángulos en la parte superior de estas líneas de manera que los triángulos satisfagan dos requisitos: Primero, no hay dos triángulos que compartan un borde. (Los sistemas que cumplen con este requisito se denominan sistemas triples de Steiner). Y segundo, asegúrese de que cada pequeño subconjunto de triángulos utilice una cantidad suficientemente grande de nodos.
La forma en que los investigadores hicieron esto quizás se entienda mejor con una analogía.
Digamos que en lugar de hacer triángulos con bordes, estás construyendo casas con ladrillos de Lego. Los primeros edificios que haces son extravagantes, con refuerzos estructurales y ornamentación elaborada. Una vez que hayas terminado con estos, déjalos a un lado. Servirán como un "absorbedor", una especie de reserva estructurada.
Ahora empieza a hacer edificios con los ladrillos que te quedan, procediendo sin mucha planificación. Cuando su suministro de Legos disminuye, es posible que se encuentre con algunos ladrillos sueltos o casas que no sean sólidas estructuralmente. Pero dado que los edificios absorbentes están tan exagerados y reforzados, puede arrancar algunos ladrillos aquí y allá y usarlos sin provocar una catástrofe.
En el caso del sistema triple de Steiner, estás tratando de crear triángulos. Su absorbedor, en este caso, es una colección de bordes cuidadosamente elegida. Si no puede ordenar el resto del sistema en triángulos, puede usar algunos de los bordes que conducen al absorbente. Luego, cuando termines de hacer eso, descompones el absorbedor en triángulos.
La absorción no siempre funciona. Pero los matemáticos han jugado con el proceso, encontrando nuevas formas de esquivar los obstáculos. Por ejemplo, una poderosa variante llamada absorción iterativa divide los bordes en una secuencia anidada de conjuntos, de modo que cada uno actúa como absorbente para el siguiente más grande.
“Durante la última década más o menos ha habido mejoras masivas”, dijo Conlon. "Es algo así como una forma de arte, pero realmente lo han llevado al nivel de arte elevado en este punto".
El problema de Erdős era complicado incluso con la absorción iterativa. “Quedó bastante claro bastante rápido por qué este problema no se había resuelto”, dijo Mehtaab Sawhney, uno de los cuatro investigadores que lo resolvieron, junto con ashwin sah, quien junto con Sawhney es estudiante de posgrado en el Instituto Tecnológico de Massachusetts; miguel simkin, becario postdoctoral en el Centro de Ciencias y Aplicaciones Matemáticas de la Universidad de Harvard; y mateo kwan, matemático del Instituto de Ciencia y Tecnología de Austria. "Hubo tareas técnicas bastante interesantes y bastante difíciles".
Por ejemplo, en otras aplicaciones de absorción iterativa, una vez que terminas de cubrir un conjunto, ya sea con triángulos, para sistemas triples de Steiner, o con otras estructuras para otros problemas, puedes considerarlo resuelto y olvidarte de él. Las condiciones de Erdős, sin embargo, impidieron que los cuatro matemáticos hicieran eso. Un grupo problemático de triángulos podría involucrar fácilmente nodos de múltiples conjuntos absorbentes.
“Un triángulo que elegiste hace 500 pasos, necesitas recordar de alguna manera cómo pensar en eso”, dijo Sawhney.
Lo que los cuatro finalmente descubrieron fue que si elegían sus triángulos con cuidado, podrían eludir la necesidad de realizar un seguimiento de cada pequeña cosa. “Lo que es mejor hacer es pensar en cualquier conjunto pequeño de 100 triángulos y garantizar que ese conjunto de triángulos se elija con la probabilidad correcta”, dijo Sawhney.
Los autores del nuevo artículo son optimistas de que su técnica puede extenderse más allá de este problema. Ellos tienen ya aplicaron su estrategia a un problema sobre Cuadrados latinos, que son como una simplificación de un sudoku.
Más allá de eso, hay varias preguntas que eventualmente pueden dar lugar a métodos de absorción, dijo Kwan. "Hay tantos problemas en la combinatoria, especialmente en la teoría del diseño, donde los procesos aleatorios son una herramienta realmente poderosa". Uno de esos problemas, la conjetura de Ryser-Brualdi-Stein, también se trata de cuadrados latinos y espera una solución desde la década de 1960.
Aunque la absorción puede necesitar un mayor desarrollo antes de que pueda resolver ese problema, ha recorrido un largo camino desde su inicio hace 30 años, dijo maya stein, subdirector del Centro de Modelamiento Matemático de la Universidad de Chile. "Es algo realmente genial de ver, cómo evolucionan estos métodos".
