Get best of the week

Rainbow Coloring son los mejores amigos de los matemáticos

Recientemente, los colores del arco iris han ayudado a llevar a cabo una nueva prueba. Y no son la primera vez que son útiles.



La codificación de colores del cuadrado latino y su gráfico puede decir mucho sobre ellos.

Recientemente, hablamos de una nueva prueba de la hipótesis de Ringel . Parte de la evidencia estaba relacionada con el uso de colores del arco iris, una forma especial de codificación de colores para visualizar información. Sin embargo, estos libros para colorear han sido utilizados por los matemáticos durante mucho tiempo para facilitar la resolución de acertijos, y ahora están tratando de aplicar esta técnica al problema asociado con el anterior.

La hipótesis de Ringel es un problema del campo de la combinatoria relacionado con la construcción de gráficos: puntos (vértices) conectados por líneas (bordes). Predice una relación especial entre gráficos grandes de cierto tipo con vértices 2n + 1 y gráficos proporcionalmente más pequeños con vértices n + 1.

Comencemos, por ejemplo, con 11 picos. Conecte cada vértice con todos los demás para obtener el llamado gráfico completo A continuación, tome seis de los vértices disponibles y conéctelos, como nos plazca, solo para que no tengamos bucles cerrados. Así obtenemos el llamado "madera".


Ejemplos de gráficos y árboles completos

La hipótesis de Ringel dice que las copias de cualquier árbol pueden cubrir idealmente, o enlosar, todos los bordes del gráfico completo correspondiente, tal como puede enlosar el piso de la cocina con los mismos azulejos.



Al igual que con el piso de la cocina, para tener éxito es necesario elegir la ubicación correcta de la primera loseta. Los tres matemáticos que obtuvieron el color de prueba codificaron los bordes del gráfico completo en función de la distancia entre los vértices para encontrar esta ubicación.



Luego trataron de organizar el árbol dentro del gráfico completo para que cubriera un borde de cada color. Habiendo demostrado que tal disposición de "arco iris" es posible en cualquier caso, demostraron que el mosaico ideal predicho por Ringel siempre funciona.

Sin embargo, esta técnica de coloración del arco iris no vino al rescate por primera vez.

En el siglo XVIII, Leonard Euler se interesó en algo como el Sudoku para niños. Toma un cuadrado de 3x3 celdas. Euler lo llenó para que en cada fila y cada columna hubiera números del 1 al 3, sin repetirse nunca. Este rompecabezas se llama cuadrado latino . Los patrones y técnicas descubiertos por Euler y otros matemáticos al estudiar cuadrados latinos tienen una conexión con muchas áreas diferentes de las matemáticas.



Entonces Euler se preguntó: ¿es posible elegir tres celdas, una de cada columna y cada fila, para que los números en ellas no se repitan? Suponga que puede seleccionar una celda de la primera columna de la primera fila que contiene 1, una celda de la segunda fila de la segunda columna que contiene 3, y de la tercera fila de la tercera columna que contiene 2. Entonces, seleccionamos tres celdas, cada una de las cuales pertenece a diferentes filas y columnas, y contiene su número - 1, 3, 2. Este conjunto de celdas se llama transversal.



Euler quería saber si es posible dividir toda la cuadrícula de 3x3 (o cuadrícula cuadrada de cualquier tamaño) completamente en conjuntos transversales, de modo que cada conjunto tenga un número de cada fila y cada columna. Es decir, en el caso de un cuadrado de 3x3, me gustaría esperar que podamos encontrar tres conjuntos transversales diferentes que cubran todas las celdas del cuadrado.

Como resultado, los matemáticos han descubierto que una forma de explorar este problema es convertir un cuadrado en un gráfico. Para hacer esto, dibuja tres vértices a la izquierda, denotando tres columnas. Luego dibujamos tres vértices a la derecha, que representan las líneas. Dibuja los bordes que conectan cada vértice a la derecha con cada vértice a la izquierda. Cada borde, que es una combinación de una fila y columna en particular, representa una de nueve celdas. Por ejemplo, el borde entre el vértice superior derecho y el vértice superior izquierdo corresponde a la celda de la primera fila de la primera columna (celda superior izquierda del cuadrado latino).



Ahora sacamos los lápices de colores y codificamos los colores de las costillas de acuerdo con los números del cuadrado que denotan. Supongamos que coloreamos las líneas que denotan 1 con azul, rojo con 2, amarillo con 3. Si 1 está en la celda superior izquierda, entonces el borde entre los vértices superiores será azul.



Veamos los colores de los bordes. ¿Es posible elegir tres bordes de cada uno de los tres colores para que comiencen y terminen en diferentes vértices? Este conjunto se llama coincidencia de arcoíris. Si lo encuentra, queda claro que en el cuadrado latino correspondiente hay una transversal. Además, si encuentra tres correspondencias de arcoíris diferentes, queda claro que todo el cuadrado latino consiste en transversales.



La coloración del arco iris ayudó a los investigadores a estudiar problemas en el pasado, y también se convirtió en un elemento clave en la nueva prueba de la hipótesis de Ringel. También juegan un papel en una tarea aún más compleja, la graciosa hipótesis de marcado .

Para comprender la esencia del problema, primero dibuje seis vértices y luego conéctelos para formar un árbol. Asigne un número a cada vértice de cualquier manera. Luego marque cada borde con la diferencia entre los números de los vértices que conecta. Es decir, por ejemplo, si un borde conecta los vértices 6 y 2, entonces marcamos este borde con el número 4.

Su objetivo es hacer que las etiquetas de borde vayan en secuencia y sus números no se repitan. En este caso, 1, 2, 3, 4, 5. Si puede hacer esto, entonces existirá un marcado elegante para su árbol.



En la década de 1960, Gerhard Ringel , el que presentó la hipótesis, y Anton Kotsig, juntos sugirieron que cualquier árbol, independientemente del número de bordes o formas, puede marcarse con gracia.

La hipótesis de marcado elegante implica la hipótesis de Ringel, es decir, si la primera hipótesis es verdadera, entonces la hipótesis de Ringel también es cierta. Para comprender esto, volvamos a un árbol de seis vértices marcado con gracia y un gráfico completo de 11 vértices. Distribuimos estos 11 vértices alrededor de la circunferencia y los numeramos del 1 al 11. Ahora colocaremos una copia del árbol en el gráfico completo para que las etiquetas de los vértices coincidan: el vértice 5 del árbol se superpone al vértice 5 del gráfico completo, y así sucesivamente. Esta ubicación es una copia del arco iris de un árbol marcado con gracia.



Entonces, si sabe que los árboles con el número de vértices n + 1 siempre se pueden marcar con gracia, entonces sabe que siempre se pueden colocar dentro del gráfico completo correspondiente con vértices 2n + 1 para obtener una copia del árbol en forma de arco iris. Y tal ubicación será exactamente la posición con la que comenzará el proceso de mosaico de Ringel.

"Si encuentra un marcado elegante, puedo decirle cómo encontrar su copia del arco iris", dijo Benny Sudakov, del Instituto Federal Suizo de Tecnología, uno de los tres autores de la prueba de la hipótesis de Ringel.

Por supuesto, los matemáticos finalmente pudieron probar la verdad de la hipótesis de Ringel sin tener que probar la hipótesis del marcado elegante, dejando esta pregunta sin respuesta.

"El marcado elegante es un tema atractivo y hermoso en sí mismo, y aún permanece abierto", dijo Sudakov.

Sin embargo, los métodos que condujeron a la prueba de la hipótesis de Ringel probablemente se pueden aplicar a un marcado elegante, y los matemáticos están ansiosos por descubrir hasta qué punto estos métodos pueden llevarlos.

More articles:


All Articles