En la disciplina matemática de la teoría de grafos , una coincidencia de arco iris en un gráfico con bordes coloreados es una coincidencia en la que todos los bordes tienen colores distintos.
Dado un gráfico con aristas coloreadas G = ( V , E ) , un arco iris que coincide con M en G es un conjunto de aristas no adyacentes por pares, es decir, no hay dos aristas que compartan un vértice común, de modo que todas las aristas del conjunto tengan colores distintos.
Una coincidencia de arco iris máxima es una coincidencia de arco iris que contiene el mayor número posible de aristas.
Las coincidencias de arcoíris son de particular interés dada su conexión con transversales de cuadrados latinos .
Denotemos por K n , n el gráfico bipartito completo en n + n vértices. Cada coloración adecuada de n aristas de K n , n corresponde a un cuadrado latino de orden n . Una coincidencia de arco iris corresponde entonces a una transversal del cuadrado latino, es decir, una selección de n posiciones, una en cada fila y en cada columna, que contienen entradas distintas.
Esta conexión entre transversales de cuadrados latinos y coincidencias de arco iris en K n , n ha inspirado un interés adicional en el estudio de las coincidencias de arco iris en gráficos sin triángulos . [1]
Una coloración de aristas se llama propia si cada arista tiene un solo color y cada dos aristas del mismo color no tienen ningún vértice en común.
Una coloración adecuada de los bordes no garantiza la existencia de una combinación perfecta del arco iris. Por ejemplo, considere el gráfico K 2,2 : el gráfico bipartito completo en 2+2 vértices. Supongamos que los bordes ( x 1 , y 1 ) y ( x 2 , y 2 ) son de color verde, y los bordes ( x 1 , y 2 ) y ( x 2 , y 1 ) son de color azul. Esta es una coloración adecuada, pero sólo hay dos combinaciones perfectas, y cada una de ellas está coloreada por un solo color. Esto plantea la pregunta: ¿cuándo se garantiza que existe una gran coincidencia de arcoíris?
Gran parte de la investigación sobre esta cuestión se publicó utilizando la terminología de transversales latinas en cuadrados latinos . Traducido a la terminología de coincidencia de arcoíris:
Una conjetura más general de Stein es que existe una coincidencia de arco iris de tamaño n – 1 no sólo para una coloración de borde adecuada, sino para cualquier coloración en la que cada color aparece exactamente en n bordes. [2]
Se han demostrado algunas versiones más débiles de estas conjeturas:
Wang preguntó si existe una función f ( d ) tal que cada gráfico G con el color de borde adecuado y un grado mínimo d y al menos f ( d ) vértices debe tener un arco iris coincidente de tamaño d . [9] Obviamente son necesarios al menos 2 vértices d , pero ¿cuántos son suficientes?
Supongamos que cada arista puede tener varios colores diferentes, mientras que cada dos aristas del mismo color aún no deben tener ningún vértice en común. En otras palabras, cada color es una combinación . ¿Cuántos colores se necesitan para garantizar la existencia de una combinación de arcoíris?
Drisko [12] estudió esta cuestión utilizando la terminología de rectángulos latinos . Demostró que, para cualquier n ≤ k , en el gráfico bipartito completo K n , k , cualquier familia de 2 n – 1 coincidencias (=colores) de tamaño n tiene una coincidencia de arco iris perfecta (de tamaño n ). Aplicó este teorema a preguntas sobre acciones grupales y conjuntos de diferencias .
Drisko también demostró que pueden ser necesarias 2 n – 1 coincidencias: considere una familia de 2 n – 2 coincidencias, de las cuales n – 1 son { ( x 1 , y 1 ), ( x 2 , y 2 ), ..., ( x n , y n )} y los otros n – 1 son {( x 1 , y 2 ), ( x 2 , y 3 ), …, ( x n , y 1 ) }. Entonces, la coincidencia de arco iris más grande es de tamaño n – 1 (por ejemplo, tome un borde de cada una de las primeras n – 1 coincidencias).
Alon [13] demostró que el teorema de Drisko implica un resultado más antiguo [14] en la teoría de números aditivos .
Aharoni y Berger [15] generalizaron el teorema de Drisko a cualquier gráfico bipartito, a saber: cualquier familia de 2 n – 1 coincidencias de tamaño n en un gráfico bipartito tiene una coincidencia de arco iris de tamaño n .
Aharoni, Kotlar y Ziv [16] demostraron que el ejemplo extremo de Drisko es único en cualquier gráfico bipartito.
En gráficos generales, 2 n – 1 coincidencias ya no son suficientes. Cuando n es par, se puede agregar al ejemplo de Drisko la coincidencia { ( x 1 , x 2 ), ( y 1 , y 2 ), ( x 2 , x 3 ), ( y 2 , y 3 ), … } y obtener una familia de coincidencias 2 n – 1 sin ninguna coincidencia de arco iris.
Aharoni, Berger, Chudnovsky, Howard y Seymour [17] demostraron que, en un gráfico general, 3 n – 2 coincidencias (=colores) siempre son suficientes. No se sabe si esto es ajustado: actualmente el mejor límite inferior para n par es 2 n y para n impar es 2 n – 1 . [18]
Una coincidencia fraccionaria es un conjunto de aristas con un peso no negativo asignado a cada arista, de modo que la suma de los pesos adyacentes a cada vértice sea como máximo 1. El tamaño de una coincidencia fraccionaria es la suma de los pesos de todas las aristas. Es una generalización de una combinación y se puede utilizar para generalizar tanto los colores como la combinación del arco iris:
Se sabe que, en un gráfico bipartito, el tamaño máximo de coincidencia fraccionaria es igual al tamaño máximo de coincidencia. Por tanto, el teorema de Aharoni y Berger [15] es equivalente al siguiente. Sea n cualquier número entero positivo. Dada cualquier familia de 2 n - 1 coincidencias fraccionarias (= colores) de tamaño n en un gráfico bipartito, existe una coincidencia fraccionaria de arco iris de tamaño n .
Aharoni, Holzman y Jiang extienden este teorema a gráficas arbitrarias de la siguiente manera. Sea n cualquier número entero positivo o semientero. Cualquier familia de 2 n coincidencias fraccionarias (= colores) de tamaño al menos n en un gráfico arbitrario tiene una coincidencia fraccionaria de arco iris de tamaño n . [18] : Thm.1.5 El 2 n es el más pequeño posible para coincidencias fraccionarias en gráficos arbitrarios: el caso extremo se construye utilizando un ciclo de longitud impar.
Para el caso de coincidencias fraccionarias perfectas, ambos teoremas anteriores pueden derivarse del colorido teorema de Caratheodory .
Para cada arista e en E , sea 1 e un vector de tamaño | V | , donde para cada vértice v en V , el elemento v en 1 e es igual a 1 si e es adyacente a v y 0 en caso contrario (por lo que cada vector 1 e tiene 2 unos y | V | -2 ceros). Cada coincidencia fraccionaria corresponde a una combinación cónica de aristas, en la que cada elemento es como máximo 1. Una combinación cónica en la que cada elemento es exactamente 1 corresponde a una coincidencia fraccionaria perfecta . En otras palabras, una colección F de aristas admite una coincidencia fraccionaria perfecta, si y sólo si 1 v (el vector de | V | unos) está contenido en el casco cónico de los vectores 1 e para e en F .
Considere un gráfico con 2 n vértices y suponga que hay 2 n subconjuntos de aristas, cada uno de los cuales admite una coincidencia fraccionaria perfecta (de tamaño n ). Esto significa que el vector 1 v está en el casco cónico de cada uno de estos n subconjuntos. Según el colorido teorema de Caratheodory , existe una selección de 2 n aristas, una de cada subconjunto, cuyo casco cónico contiene 1 v . Esto corresponde a una coincidencia fraccionaria perfecta del arco iris. La expresión 2 n es la dimensión de los vectores 1 e ; cada vector tiene 2 n elementos.
Ahora supongamos que la gráfica es bipartita. En un gráfico bipartito, existe una restricción sobre los vectores 1 e : la suma de los elementos correspondientes a cada parte del gráfico debe ser 1. Por lo tanto, los vectores 1 e viven en un espacio dimensional (2 n – 1) . Por lo tanto, el mismo argumento anterior es válido cuando solo hay 2 n – 1 subconjuntos de aristas.
Un hipergrafo r-uniforme es un conjunto de hiperaristas, cada uno de los cuales contiene exactamente r vértices (por lo que un hipergrafo 2-uniforme es solo un gráfico sin bucles automáticos). Aharoni, Holzman y Jiang extienden su teorema a tales hipergrafías de la siguiente manera. Sea n cualquier número racional positivo. Cualquier familia de ⌈ r ⋅ n ⌉ coincidencias fraccionarias (= colores) de tamaño al menos n en un hipergrafo uniforme r tiene una coincidencia fraccionaria de arco iris de tamaño n . [18] : Thm.1.6 El ⌈ r ⋅ n ⌉ es el más pequeño posible cuando n es un número entero.
Un hipergrafo r-partido es un hipergrafo r -uniforme en el que los vértices se dividen en r conjuntos disjuntos y cada hiperborde contiene exactamente un vértice de cada conjunto (por lo que un hipergrafo bipartito es un gráfico simplemente bipartito). Sea n cualquier número entero positivo. Cualquier familia de rn – r + 1 coincidencias fraccionarias (=colores) de tamaño al menos n en un hipergrafo r -partito tiene una coincidencia fraccionaria de arco iris de tamaño n . [18] : Thm.1.7 El rn – r + 1 es el más pequeño posible: el caso extremo es cuando n = r – 1 es una potencia prima , y todos los colores son aristas del plano proyectivo truncado de orden n . Entonces, cada color tiene n 2 = rn – r + 1 aristas y una coincidencia fraccionaria de tamaño n , pero cualquier coincidencia fraccionaria de ese tamaño requiere todas rn – r + 1 aristas. [19]
Para el caso de coincidencias fraccionarias perfectas, ambos teoremas anteriores pueden derivarse del colorido teorema de la carateodoria de la sección anterior. Para un hipergrafo r uniforme general (que admite una coincidencia perfecta de tamaño n ), los vectores 1 e viven en un espacio dimensional ( rn ) . Para un hipergrafo r -uniforme r -partido, las restricciones de r -partición implican que los vectores 1 e viven en un ( rn – r + 1) -espacio dimensional.
Los resultados anteriores son válidos sólo para coincidencias fraccionarias del arco iris . Por el contrario, el caso de las coincidencias de integrales de arco iris en r -hipergrafos uniformes se comprende mucho menos. El número de coincidencias requeridas para una coincidencia de arco iris de tamaño n crece al menos exponencialmente con n .
Garey y Johnson han demostrado que calcular una coincidencia máxima del arco iris es NP completo incluso para gráficos bipartitos con bordes coloreados . [20]
Se han aplicado combinaciones de arcoíris para resolver problemas de embalaje . [21]
