En la disciplina matemática de la teoría de grafos , una coincidencia de arco iris en un grafo con bordes coloreados es una coincidencia en la que todos los bordes tienen colores distintos.
Dado un grafo 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 en el conjunto tienen 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 combinaciones de arcoíris son de particular interés dada su conexión con las transversales de los cuadrados latinos .
Denotemos por K n , n el grafo bipartito completo de n + n vértices. Cada coloración propia de n aristas de K n , n corresponde a un cuadrado latino de orden n . Una correspondencia de arcoíris 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 las transversales de los cuadrados latinos y las correspondencias de arcoíris en K n , n ha inspirado un interés adicional en el estudio de las correspondencias de arcoíris en gráficos sin triángulos . [1]
Una coloración de aristas se denomina apropiada 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 las aristas no garantiza la existencia de una correspondencia perfecta de arcoíris. Por ejemplo, considere el grafo K 2,2 : el grafo bipartito completo en 2+2 vértices. Suponga que las aristas ( x 1 , y 1 ) y ( x 2 , y 2 ) están coloreadas de verde, y las aristas ( x 1 , y 2 ) y ( x 2 , y 1 ) están coloreadas de azul. Esta es una coloración adecuada, pero solo hay dos correspondencias perfectas, y cada una de ellas está coloreada por un solo color. Esto invoca la pregunta: ¿cuándo se garantiza que existe una correspondencia de arcoíris grande?
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 correspondencia de arcoíris:
Una conjetura más general de Stein es que existe una correspondencia de arcoíris de tamaño n – 1 no sólo para una coloración de aristas adecuada, sino para cualquier coloración en la que cada color aparezca en exactamente n aristas. [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 grafo G con aristas correctamente coloreadas con 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 d vértices, pero ¿cuántos son suficientes?
Supongamos que cada arista puede tener varios colores diferentes, mientras que dos aristas del mismo color no deben tener ningún vértice en común. En otras palabras, cada color es un arcoíris coincidente . ¿Cuántos colores se necesitan para garantizar la existencia de un arcoíris coincidente?
Drisko [12] estudió esta cuestión utilizando la terminología de los rectángulos latinos . Demostró que, para cualquier n ≤ k , en el grafo bipartito completo K n , k , cualquier familia de 2 n – 1 coincidencias (=colores) de tamaño n tiene una coincidencia 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 necesarios 2 n – 1 emparejamientos: considere una familia de 2 n – 2 emparejamientos, de los 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 el emparejamiento arco iris más grande es de tamaño n – 1 (por ejemplo, tome una arista de cada uno de los primeros n – 1 emparejamientos).
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, es decir: cualquier familia de 2 n – 1 emparejamientos de tamaño n en un gráfico bipartito tiene un emparejamiento arco iris de tamaño n .
Aharoni, Kotlar y Ziv [16] demostraron que el ejemplo extremal de Drisko es único en cualquier gráfico bipartito.
En los grafos generales, 2 n – 1 emparejamientos ya no son suficientes. Cuando n es par, se puede añadir al ejemplo de Drisko el emparejamiento { ( x 1 , x 2 ), ( y 1 , y 2 ), ( x 2 , x 3 ), ( y 2 , y 3 ), … } y obtener una familia de 2 n – 1 emparejamientos sin ningún emparejamiento arco iris.
Aharoni, Berger, Chudnovsky, Howard y Seymour [17] demostraron que, en un gráfico general, 3 n – 2 coincidencias (=colores) son siempre suficientes. No se sabe si esto es exacto: 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 coincidencia y se puede utilizar para generalizar tanto la coincidencia de colores como la del arco iris:
Se sabe que, en un grafo bipartito, el tamaño máximo de coincidencia fraccionaria es igual al tamaño máximo de coincidencia. Por lo tanto, el teorema de Aharoni y Berger [15] es equivalente al siguiente. Sea n cualquier entero positivo. Dada cualquier familia de 2 n – 1 coincidencias fraccionarias (=colores) de tamaño n en un grafo bipartito, existe una coincidencia fraccionaria arco iris de tamaño n .
Aharoni, Holzman y Jiang extienden este teorema a grafos arbitrarios de la siguiente manera. Sea n cualquier entero positivo o semientero. Cualquier familia de 2 n coincidencias fraccionarias (=colores) de tamaño al menos n en un grafo arbitrario tiene una coincidencia fraccionaria arco iris de tamaño n . [18] : Teoría 1.5 2 n es el valor más pequeño posible para coincidencias fraccionarias en grafos arbitrarios: el caso extremal se construye utilizando un ciclo de longitud impar.
Para el caso de emparejamientos fraccionarios perfectos, 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). Todo emparejamiento fraccionario 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 un emparejamiento fraccionario perfecto . En otras palabras, una colección F de aristas admite un emparejamiento fraccionario perfecto, si y solo si 1 v (el vector de | V | unos) está contenido en la envoltura cónica de los vectores 1 e para e en F .
Consideremos un grafo con 2 n vértices y supongamos que existen 2 n subconjuntos de aristas, cada uno de los cuales admite un emparejamiento fraccionario perfecto (de tamaño n ). Esto significa que el vector 1 v está en la envoltura cónica de cada uno de estos n subconjuntos. Por el colorido teorema de Caratheodory , existe una selección de 2 n aristas, una de cada subconjunto, que su envoltura cónica contiene 1 v . Esto corresponde a un emparejamiento fraccionario perfecto de 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 el grafo es bipartito. En un grafo bipartito, existe una restricción sobre los vectores 1 e : la suma de los elementos correspondientes a cada parte del grafo debe ser 1. Por lo tanto, los vectores 1 e viven en un espacio de (2 n – 1) dimensiones. Por lo tanto, el mismo argumento que el anterior se cumple cuando solo hay 2 n – 1 subconjuntos de aristas.
Un hipergrafo r-uniforme es un conjunto de hiperaristas cada una de las cuales contiene exactamente r vértices (por lo que un hipergrafo 2-uniforme es simplemente un grafo sin bucles propios). Aharoni, Holzman y Jiang extienden su teorema a tales hipergrafos 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 r -uniforme tiene una coincidencia fraccionaria arco iris de tamaño n . [18] : Teoría 1.6 El ⌈ r ⋅ n ⌉ es el más pequeño posible cuando n es un entero.
Un hipergrafo r-partito es un hipergrafo r -uniforme en el que los vértices están divididos en r conjuntos disjuntos y cada hiperarista contiene exactamente un vértice de cada conjunto (por lo que un hipergrafo 2-partito es simplemente un grafo bipartito). Sea n cualquier 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 arco iris de tamaño n . [18] : Teoría 1.7 El rn – r + 1 es el más pequeño posible: el caso extremal es cuando n = r – 1 es una potencia prima , y todos los colores son aristas del plano proyectivo truncado de orden n . Por lo tanto, 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 las aristas rn – r + 1 . [19]
Para el caso de emparejamientos fraccionarios perfectos, ambos teoremas anteriores pueden derivarse del teorema de carateodoría colorida en la sección anterior. Para un hipergrafo r -uniforme general (que admite un emparejamiento perfecto de tamaño n ), los vectores 1 e viven en un espacio ( rn ) -dimensional. Para un hipergrafo r -uniforme r -partito, las restricciones de r -partitez implican que los vectores 1 e viven en un espacio ( rn – r + 1) -dimensional.
Los resultados anteriores son válidos únicamente para emparejamientos fraccionarios de arcoíris . Por el contrario, el caso de emparejamientos integrales de arcoíris en hipergrafos r -uniformes es mucho menos conocido. La cantidad de emparejamientos necesarios para un emparejamiento de arcoíris de tamaño n crece al menos exponencialmente con n .
Garey y Johnson han demostrado que calcular una correspondencia arcoíris máxima es NP-completo incluso para gráficos bipartitos con aristas coloreadas . [20]
Los emparejamientos de arcoíris se han aplicado para resolver problemas de empaquetamiento . [21]
