Get best of the week

La prueba de arco iris demuestra la presencia de componentes estándar en gráficos

Los matemáticos han demostrado que las copias de gráficos más pequeños siempre pueden cubrir idealmente gráficos más grandes.



El 8 de enero, tres matemáticos publicaron una prueba de un teorema de la combinatoria formulada hace casi 60 años, conocida como la hipótesis de Ringel. Hablando en términos generales, predice que los gráficos, construcciones que consisten en puntos y líneas, se pueden plegar idealmente a partir de piezas idénticas de menor tamaño.

Los matemáticos aceptaron con entusiasmo la confirmación de esta hipótesis.

"La buena fortuna es que este trabajo resuelve una hipótesis muy antigua que no puede ser verificada por otros métodos", dijo Gil Kalai , matemático de la Universidad Hebrea de Jerusalén, no relacionado con este trabajo.

La hipótesis de Ringel predice que los tipos especiales de gráficos complejos, con billones de vértices y bordes, pueden ser "mosaicos", es decir. cubierta completa, con copias separadas de gráficos más pequeños de cierto tipo. Desde un punto de vista conceptual, esta pregunta es similar a la siguiente: ¿puedo revestir completamente el piso de la cocina con las mismas copias de las losetas de la tienda? En la vida real, la mayoría de los tipos de azulejos no son adecuados para su cocina: para cubrir completamente el piso, debe combinar sus diferentes formas. Pero en el mundo de la teoría de gráficos, la hipótesis predice que siempre se puede enlosar un gráfico.

Y en la cocina, y en los gráficos, es importante dónde coloca exactamente el primer mosaico. El nuevo trabajo destaca este tema crucial, y de tal manera que es sorprendente y sorprendentemente intuitivo.

Bosque con árboles


En combinatoria, los matemáticos estudian cómo los vértices (puntos) y los bordes (líneas) se combinan para formar objetos más complejos llamados gráficos. Puede hacer muchas preguntas sobre gráficos. Uno de los básicos: ¿en qué casos los gráficos más pequeños y simples se integran idealmente en los más grandes y complejos?

"Tienes un conjunto de piezas de rompecabezas y no sabes si puedes ensamblarlo a partir de estas piezas", dijo Jacob Fox de la Universidad de Stanford.

En 1963, el matemático alemán Gerhard RingelPlanteó una pregunta simple pero más amplia de este tipo. Comencemos, dijo, con cualquier número impar de vértices mayor que 3 (para la plausibilidad de la hipótesis, el número de vértices debe ser impar, como veremos más adelante). Conéctelos con bordes para que cada vértice se conecte con todos los demás. Luego obtenemos un objeto llamado gráfico completo .



Luego imagine una gráfica de un tipo diferente. Puede ser una forma simple: varios bordes conectados en una línea. O un camino con costillas ramificadas. Se pueden agregar ramas a otras ramas. Puede hacer un gráfico complejo arbitrariamente, evitando solo bucles cerrados. Tales gráficos se llaman árboles.



La pregunta de Ringel se relaciona con la relación de gráficos completos y árboles. Él dijo: primero, imagine una gráfica completa de 2n + 1 vértices (un número impar). Luego imagine cualquier árbol que consista en n + 1 vértices, y tales árboles pueden ser muy diferentes.

Ahora tome uno de estos árboles y colóquelo de modo que cada borde del árbol coincida con el borde del gráfico completo. Luego colocamos otra copia del mismo árbol en otra parte del gráfico completo.

Ringel predijo que actuando de esta manera, y comenzando en el lugar correcto, lo ideal sería unir todo el gráfico completo. Esto significa que cada borde del gráfico completo estará cubierto por el borde del árbol, y las copias de los árboles no se superpondrán.



“Puedo tomar copias del árbol. Puse una copia en el gráfico completo. Ella cubre algunas costillas. Luego repito el proceso. La hipótesis sugiere que esto puede cubrir todo ", dijo Benny Sudakov del Instituto Federal Suizo de Tecnología, coautor de la nueva evidencia, junto con Richard Montgomery de la Universidad de Birmingham y Alexei Pokrovsky del Birkbeck College de la Universidad de Londres.

Finalmente, Ringel predijo que el gráfico se puede colocar en mosaico independientemente de cuál de las muchas opciones de árbol utilizará. Tal afirmación puede parecer demasiado general. La conjetura de Ringel se aplica tanto a los gráficos completos con 11 vértices como a los gráficos completos con 11 billones + 1 vértices. Y cuanto mayor sea el gráfico completo, mayor será el número de árboles posibles que se pueden dibujar para n + 1 vértices. ¿Cómo puede cada uno de ellos idealmente unir el gráfico completo correspondiente?

Sin embargo, había razones para creer que la hipótesis de Ringel podría ser cierta. La primera confirmación fue que la aritmética combinatoria más simple no excluía tal opción: el número de aristas en un gráfico completo con 2n + 1 vértices siempre se puede dividir por completo por el número de aristas en un árbol con n + 1 vértices.

"El hecho de que el número de bordes de un gráfico completo se divide por el número de bordes de un árbol es muy importante", dijo Montgomery.

Los matemáticos encontraron rápidamente más evidencia de la plausibilidad de la hipótesis, lo que desencadenó una cadena de descubrimientos que finalmente condujeron a la prueba.

Colocar y girar


Uno de los árboles más simples es una estrella: un pico central con bordes que emanan de él. Pero difiere de la imagen típica de una estrella, porque los bordes no tienen que estar distribuidos uniformemente alrededor de la parte superior. Todos tienen que venir de un solo lugar y no deben cruzarse en ningún otro lugar, excepto en el pico central. Si desea probar la exactitud de la hipótesis de Ringel, entonces un árbol en forma de estrella será un punto de partida natural.



Y, por supuesto, los matemáticos descubrieron rápidamente que una estrella de n + 1 vértices siempre pavimenta idealmente un gráfico completo con 2n + 1 vértices. Este hecho es interesante en sí mismo, pero su prueba hizo que los matemáticos pensaran más.

Toma un ejemplo simple. Comencemos con 11 picos. Los colocamos en un círculo y conectamos cada vértice con todos los demás, obteniendo un gráfico completo.



Ahora considere la estrella que le corresponde: el punto central con cinco aristas que emanan de ella.



Ahora colocamos la estrella para que el vértice central coincida con uno de los vértices del gráfico completo. Cubriremos varios bordes, pero no todos. Ahora mueva la estrella un vértice, como si girara el dial de la brújula. Obtenemos una nueva copia de la estrella superpuesta en un conjunto de bordes completamente diferente del gráfico completo.

Rotaremos más la estrella. Para cuando regresemos a donde comenzamos, pavimentaremos todo el gráfico completo sin superponer estrellas, exactamente como lo predijo Ringel.



"Sabemos que una hipótesis no puede descartarse de inmediato, al menos si tomamos un árbol en forma de estrella", dijo Sudakov. "Además, incluso podemos demostrar esto muy bien: dibuje un gráfico en un círculo, cambie una estrella, obtenga nuevas copias y reemplace todo el gráfico".

Poco después de que Ringel presentara su hipótesis, el matemático eslovaco-canadiense Anton Kotzig utilizó este ejemplo para una predicción aún más audaz que la de Ringel. Ringel dijo que cada gráfico completo con un vértice 2n + 1 se puede colocar en mosaico con cualquier árbol con un vértice n + 1, Kotzig sugirió que se puede colocar en mosaico exactamente de la misma manera que con una estrella: colocando el árbol en un gráfico completo y simplemente girándolo.

La idea parecía poco realista. La estrella es simétrica, así que no importa cómo colocarla. La mayoría de los árboles están torcidos. Deben colocarse de una manera muy específica para que el método de rotación funcione.

"La estrella era una estructura simple que se podía colocar manualmente, pero si tienes un árbol extendido en tus manos con un montón de ramas de diferentes longitudes, es difícil imaginar cómo se puede colocar con cuidado", dijo Pokrovsky.

Para resolver la hipótesis de Ringel utilizando el método rotativo Kotsig, los matemáticos necesitaban descubrir cómo colocar la primera copia del árbol para que no se produjeran matorrales intransitables. Afortunadamente, encontraron una solución colorida.

La coloración del arco iris a menudo hace la vida más fácil. Le ayuda a organizar un calendario o distinguir rápidamente un contenedor de alimentos de otro en una familia numerosa. Resulta que esto también puede ser una forma efectiva de descubrir cómo colocar correctamente el primer árbol dentro de un gráfico completo.

Imagine nuevamente un gráfico completo con 11 vértices dispuestos en un círculo. Marque sus bordes con códigos de color de acuerdo con una regla simple que tenga en cuenta la distancia entre dos vértices.

Esta distancia está determinada por el número de pasos que se deben tomar para ir de un vértice a otro en un círculo (sin cortar el camino dentro del círculo). Por supuesto, en un círculo siempre puede ir en dos direcciones, por lo que definiremos la distancia como el camino más corto entre dos picos. Si estos son vértices vecinos, entonces la distancia entre ellos será 1, no 10. Si están separados por un vértice, entonces la distancia será 2.



Ahora coloreamos los bordes del gráfico de acuerdo con la distancia. Pintamos todos los bordes que conectan los picos ubicados a una distancia de 1 en un color, por ejemplo, azul. Pintamos todos los bordes que conectan los picos ubicados a una distancia de dos unidades en la otra, por ejemplo, amarillo.

Continuamos coloreando el gráfico para que todos los bordes que conectan los vértices que están a la misma distancia tengan el mismo color. Diferentes distancias serán codificadas en diferentes colores. Para un gráfico completo con 2n + 1 vértices, necesita n colores para esto. El resultado es una imagen hermosa y útil.



Poco después de que Ringel y Kotzig expusieran sus hipótesis, Kotzig se dio cuenta de que su color del gráfico completo podría ser una guía para colocar un árbol en él.

La idea es organizar el árbol para que cubra un borde de cada color y no cubra ningún color dos veces. Los matemáticos llaman a este arreglo una réplica del arco iris de un árbol. Dado que la coloración requiere n colores, y un árbol de n + 1 vértices tendrá n bordes, sabemos de inmediato que con una alta probabilidad se puede encontrar una copia del arco iris.



A fines de la década de 1960, los matemáticos entendieron que una copia del arco iris de un árbol tenía una propiedad especial: denota solo la posición desde la cual se puede tender un puente sobre el gráfico completo girando el árbol.

"Si haces una copia del arco iris, entonces todo funcionará", dijo Pokrovsky.

Después de eso, los matemáticos ya sabían que podían probar la hipótesis de Ringel al demostrar que cada gráfico completo con 2n + 1 vértices contenía una copia del arco iris de cualquier árbol con n + 1 vértices. Y si siempre existe una copia arcoiris, entonces siempre puedes unir el gráfico.

Sin embargo, demostrar que algo siempre existe es difícil. Para esto, los matemáticos tendrían que mostrar que los gráficos completos simplemente no pueden contener copias de árboles de arcoíris. Tomó más de 40 años, pero esto es precisamente lo que Sudakov y sus coautores lograron en un nuevo trabajo.

Embalaje perfecto


Supongamos que le dan una gráfica completa con 11 vértices y un árbol con seis. El gráfico completo está pintado en cinco colores diferentes. El árbol tiene cinco bordes. Su tarea es encontrar una copia arcoiris del árbol dentro del gráfico completo.

Simplemente puede poner los bordes del árbol en el gráfico a su vez. El primero es fácil de colocar: puede elegir cualquier borde de cualquier color para ello. El segundo será un poco más difícil. Puede estar en casi cualquier lugar, excepto por la costilla del mismo color que la que acaba de cubrir. Y cuanto más coloque los bordes del árbol, más difícil será la tarea. Al llegar a la última costilla, perderá por completo la elección del color: solo habrá una. Es de esperar que haya planeado todo con suficiente antelación.

Esta idea de que la tarea de encontrar una copia del arco iris de un árbol se vuelve más complicada a medida que coloca más y más bordes del árbol en el gráfico fue una parte necesaria del método que tres matemáticos usaron para resolver este problema. Buscaron formas de mantener la mayor flexibilidad posible hacia el final del proceso.

Desde el principio sabían que sería fácil encontrar copias del arco iris de árboles muy simples: árboles que parecían un camino largo, sin ramas o con un pequeño número de ellos. Lo más difícil fue colocar correctamente los árboles con muchos bordes convergentes en un punto, como estrellas, solo que con una forma más irregular e irregular. Colocarlos es como empujar una carriola en el baúl medio lleno de un automóvil.

"La dificultad comienza cuando intentas llenar un gráfico completo con cosas tan incómodas que parecen estrellas", dijo Pokrovsky.

Cualquiera que llene el maletero sabe que siempre debe comenzar con los objetos más complejos: maletas grandes y cosas grandes e inflexibles, como las bicicletas. Las chaquetas siempre pueden ser empujadas. Y los matemáticos han adoptado esta filosofía.

Imagina un árbol con 11 aristas. Seis de ellos convergen en un punto central. Casi todos los demás forman una sola forma, distante de la principal.



La parte más difícil de colocar es la parte del árbol que consiste en un pico con seis bordes. Por lo tanto, los matemáticos lo separaron del resto del árbol y lo colocaron primero para adjuntar esta parte más tarde, como si decidieran desmontar la cama antes de arrastrarla al segundo piso y luego volver a ensamblarla en la habitación deseada. Ni siquiera colocaron esta parte de la estrella en el gráfico una vez; encontraron varios lugares adecuados para colocar sus copias dentro del gráfico completo.

Y luego seleccionaron al azar una copia. Al hacerlo, garantizaron que el espacio libre restante en el gráfico también era aleatorio, es decir, con una distribución aproximadamente igual de bordes de diferentes colores. Fue en este lugar que necesitaban colocar el resto del árbol, el camino que primero dejaron de lado.

Se enfrentaron a restricciones al elegir las opciones para su colocación. El camino debe estar conectado a la estrella, esa parte del árbol que ya han colocado, y también debe cubrir colores que antes no estaban cubiertos por la estrella con la que se conecta.

Pero los matemáticos han dejado opciones para sí mismos. Podrían conectar el camino con casi cualquiera de las diversas copias de la estrella. Lo que es aún mejor, ya que el espacio alrededor de la estrella era aleatorio, tenían opciones para elegir diferentes colores para cubrir con el resto del árbol.

"Hacia el final de la construcción de árboles, cuando la situación se complica, no me queda un color obligatorio, sino una pequeña opción", dijo Montgomery.

Tres matemáticos completan su prueba con un argumento de la teoría de la probabilidad. Mostraron que después de incrustar las partes más complejas de los árboles, siempre que el espacio restante en la columna completa fuera esencialmente aleatorio, siempre sería posible encontrar una forma de construir el resto de los árboles para obtener una copia del arco iris.

"Ahora puedes forzar lo que dejaste desde el principio, como para absorber lo que queda del árbol y obtener un colorido arcoíris completo", dijo Noga Alon de la Universidad de Princeton.

Los matemáticos no han descrito la forma exacta de encontrar una copia del arco iris para cada árbol con n + 1 vértices en cada gráfico completo con 2n + 1 vértices. Sin embargo, demostraron que debe haber una copia del arco iris.

Y si siempre existe una copia del arcoíris, siempre puede unir el gráfico con el método predicho por Ringel. Por lo tanto, su hipótesis es cierta.

La prueba también proporciona nuevas herramientas para resolver problemas similares sin resolver en combinatoria, por ejemplo, el problema del "marcado elegante", que predice que un gráfico completo se puede colocar en mosaico incluso en condiciones más estrictas, según las cuales los árboles deben colocarse con mayor precisión.

"Muestra que los métodos en los que las personas han estado pensando durante mucho tiempo realmente tienen un gran potencial", dijo Fox. "Si los aplica correctamente, puede resolver problemas que antes parecían inexpugnables".

More articles:


All Articles