Los hipergráficos revelan una solución a un problema de 50 años

El objetivo aquí es dibujar triángulos en estas líneas para que los triángulos satisfagan dos requisitos: primero, ningún triángulo tiene un borde común (los sistemas que cumplen este requisito se denominan sistemas triples de Steiner). Y segundo, asegúrese de que cualquier pequeño subconjunto de triángulos utiliza un número suficientemente grande de nodos.

Cómo los investigadores hicieron esto quizás se entienda mejor por 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 ellos, déjalos a un lado. Servirán como un "absorbedor", un tipo de acciones estructuradas.

Ahora empieza a hacer edificios con los ladrillos que te quedan, procediendo sin mucha planificación. Cuando sus suministros de Lego se agotan, puede terminar con algunos ladrillos perdidos o casas que son estructuralmente inestables. Pero dado que los edificios absorbentes están tan dominados y reforzados, puede sacar algunos ladrillos aquí y allá y usarlos sin causar un desastre.

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 seleccionada. Si encuentra que no puede clasificar el resto del sistema en triángulos, puede usar algunos de los bordes que conducen al absorbedor. Luego, cuando haya terminado con eso, divide el absorbedor en triángulos.

La absorción no siempre funciona. Pero los matemáticos han jugado con el proceso, encontrando nuevas formas de sortear los obstáculos. Por ejemplo, una poderosa variante llamada absorción iterativa divide los bordes de una secuencia anidada de conjuntos para que cada uno actúe como absorbente para el siguiente más grande.

"Durante la última década, ha habido mejoras tremendas", dijo Conlon. "Es una especie de forma de arte, pero realmente lo han llevado al nivel de arte elevado en este punto".

El problema de Erdős fue difícil incluso con la asimilación iterativa. "Quedó claro bastante rápido por qué este problema no se resolvió", dijo. Mehtaab Sawneyuno de los cuatro investigadores que lo resolvieron, junto con ashwin sahquien, como Sawney, es estudiante de posgrado en el MIT; miguel simkinbecario postdoctoral en el Centro de Ciencias Matemáticas y Aplicaciones de la Universidad de Harvard; y mateo kwanmatemá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 haya terminado de cubrir un conjunto, ya sea con triángulos para sistemas ternarios de Steiner, o con otras estructuras para otros problemas, puede considerarlo resuelto y olvidarse de él. Sin embargo, las condiciones de Erdős impidieron que los cuatro matemáticos hicieran esto. Un grupo problemático de triángulos puede incluir fácilmente nodos de múltiples conjuntos absorbentes.

"Un triángulo que elegiste hace 500 pasos, tienes que recordar de alguna manera cómo pensar en él", dijo Sawney.

Lo que los cuatro finalmente se dieron cuenta fue que si elegían sus triángulos con cuidado, podían pasar por alto la necesidad de realizar un seguimiento de cada pequeña cosa. se selecciona con la probabilidad correcta”, dijo Sawney.

Los autores del nuevo artículo son optimistas de que su técnica puede extenderse más allá de este único problema. ya han implementado su estrategia de un problema para cuadrados latinosque son como una simplificación de un sudoku.

Más allá de eso, hay varios problemas que en última instancia pueden dar lugar a métodos de absorción, dijo Quan. “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 ha estado esperando una solución desde el 1960

Si bien la aplicación puede necesitar un mayor desarrollo antes de que resuelva este problema, ha recorrido un largo camino desde su creación, dijo maya steinsubdirector del Centro de Modelamiento Matemático de la Universidad de Chile: "Es algo realmente genial ver cómo se están desarrollando estos métodos".

historia original reimpreso con permiso de Revista Cuanta, publicación editorialmente independiente de Fundación Simons cuya misión es mejorar la comprensión pública de la ciencia al cubrir los desarrollos y tendencias de investigación en matemáticas y ciencias físicas y de la vida.