Conjunto independiente del arco iris

En teoría de grafos , un conjunto independiente del arco iris ( ISR ) es un conjunto independiente en un grafo , en el que cada vértice tiene un color diferente .

Formalmente, sea $G = (V, E)$ un grafo y supongamos que el conjunto de vértices $V$ está dividido en $m$ subconjuntos $V 1, \dots, V m$ , llamados "colores". Un conjunto $U$ de vértices se denomina conjunto independiente del arco iris si satisface las dos condiciones siguientes: ^[1]

Es un conjunto independiente : cada dos vértices en $U$ no son adyacentes (no hay ninguna arista entre ellos);
Es un conjunto arco iris : $U$ contiene como máximo un único vértice de cada color $V i$ .

Otros términos utilizados en la literatura son conjunto independiente de representantes , ^[2] transversal independiente , ^[3] y sistema independiente de representantes . ^[4]

Como ejemplo de aplicación, considere una facultad con $m$ departamentos, donde algunos miembros de la facultad se desagradan entre sí. El decano quiere construir un comité con $m$ miembros, un miembro por departamento, pero sin ningún par de miembros que se desagraden entre sí. Este problema puede presentarse como la búsqueda de una ISR en un grafo en el que los nodos son los miembros de la facultad, los bordes describen las relaciones de "desagrado" y los subconjuntos $V 1, \dots, V m$ son los departamentos. ^[3]

Variantes

Se supone por conveniencia que los conjuntos $V 1, \dots, V m$ son disjuntos por pares. En general, los conjuntos pueden intersecarse, pero este caso se puede reducir fácilmente al caso de conjuntos disjuntos: para cada vértice $x$ , se forma una copia de $x$ para cada $i$ tal que $V i$ contenga $a x$ . En el grafo resultante, se conectan todas las copias de $x$ entre sí. En el nuevo grafo, los $V i$ son disjuntos y cada ISR corresponde a un ISR en el grafo original. ^[4]

El ISR generaliza el concepto de un sistema de representantes distintos (SDR, también conocido como transversal ). Cada transversal es un ISR en el que, en el grafo subyacente, están conectadas todas y solo las copias del mismo vértice de diferentes conjuntos.

Existencia de conjuntos independientes del arcoíris

Existen diversas condiciones suficientes para la existencia de un ISR.

Condición basada en el grado del vértice

Intuitivamente, cuando los departamentos $V i$ son más grandes y hay menos conflictos entre los miembros de la facultad, debería ser más probable que exista un ISR. La condición de "menor conflicto" está representada por el grado del vértice del grafo. Esto se formaliza mediante el siguiente teorema: ^[5]^{: Teoría 2}

Si el grado de cada vértice en $G$ es como máximo $d$ , y el tamaño de cada conjunto de colores es al menos $2 d$ , entonces $G$ tiene un ISR.

La $2 d$ es la mejor posible: hay gráficos con grado de vértice $k$ y colores de tamaño $2 d - 1$ sin un ISR. ^[6] Pero hay una versión más precisa en la que el límite depende tanto de $d$ como de $m$ . ^[7]

Condición basada en sets dominantes

A continuación, dado un subconjunto $S$ de colores (un subconjunto de ${V 1, ..., V m}$ ), denotamos por $U S$ la unión de todos los subconjuntos en $S$ (todos los vértices cuyo color es uno de los colores en $S$ ), y por $G S$ el subgrafo de $G$ inducido por $U S$ . ^[8] El siguiente teorema describe la estructura de los grafos que no tienen ISR pero son mínimos en sus aristas , en el sentido de que siempre que se les quita una arista, el grafo restante tiene una ISR.

Si $G$ no tiene ISR, pero para cada arista $e$ en $E$ , $Ge$ tiene un ISR, entonces para cada arista $e = (x, y)$ en $E$ , existe un subconjunto $S$ de los colores ${V 1, \dots, V m},$ y un conjunto $Z$ de aristas de $G S$ , tales que:
Los vértices $x$ $e y$ están ambos en $U S$ ;
La arista $e = (x, y)$ está en $Z$ ;
El conjunto de vértices adyacentes a $Z$ domina $G S$ ;
$| Z | \leq | S | - 1$ ;
$Z$ es coincidente : no hay dos aristas adyacentes al mismo vértice.

Condición de tipo Hall

A continuación, dado un subconjunto $S$ de colores (un subconjunto de ${V 1, \dots, V m}$ ), un conjunto independiente $I S$ de $G S$ se llama especial para $S$ si para cada subconjunto independiente $J$ de vértices de $G S$ de tamaño como máximo $| S | - 1$ , existe algún $v$ en $I S$ tal que $J \cup {v}$ también es independiente. En sentido figurado, $I S$ es un equipo de "miembros neutrales" para el conjunto $S$ de departamentos, que puede aumentar cualquier conjunto suficientemente pequeño de miembros no conflictivos, para crear un conjunto más grande de este tipo. El siguiente teorema es análogo al teorema del matrimonio de Hall : ^[9]

Si, para cada subconjunto S de colores, el grafo $G S$ contiene un conjunto independiente $I S$ que es especial para $S$ , entonces $G$ tiene un ISR.

Idea de demostración . El teorema se demuestra utilizando el lema de Sperner . ^[3]^{: Thm.4.2} Al símplex estándar con $m$ puntos finales se le asigna una triangulación con algunas propiedades especiales. Cada punto final $i$ del símplex está asociado con el conjunto de colores $V i$ , cada cara ${i 1, \dots, i k}$ del símplex está asociada con un conjunto $S = {V i 1, \dots, V ik}$ de colores. Cada punto $x$ de la triangulación está etiquetado con un vértice $g (x)$ de $G$ tal que: (a) Para cada punto $x$ en una cara $S$ , $g (x)$ es un elemento de $I S$ – el conjunto independiente especial de $S$ . (b) Si los puntos $x$ $e y$ son adyacentes en el 1-esqueleto de la triangulación, entonces $g (x)$ y $g (y)$ no son adyacentes en $G$ . Por el lema de Sperner, existe un subsímplex en el que, para cada punto $x$ , $g (x)$ pertenece a un conjunto de colores diferente; el conjunto de estos $g (x)$ es un ISR.

El teorema anterior implica la condición de matrimonio de Hall. Para ver esto, es útil enunciar el teorema para el caso especial en el que $G$ es el grafo lineal de algún otro grafo $H$ ; esto significa que cada vértice de $G$ es una arista de $H$ , y cada conjunto independiente de $G$ es una coincidencia en $H$ . La coloración de vértice de $G$ corresponde a una coloración de arista de $H$ , y un conjunto independiente del arco iris en $G$ corresponde a una coincidencia de arco iris en $H$ . Una coincidencia $I S$ en $H S$ es especial para $S$ , si para cada coincidencia $J$ en $H S$ de tamaño como máximo $| S | - 1$ , hay una arista $e$ en $I S$ tal que $J \cup {e}$ sigue siendo una coincidencia en $H S$ .

Sea $H$ un grafo con una coloración de aristas. Si, para cada subconjunto $S$ de colores, el grafo $H S$ contiene un $M S$ coincidente que es especial para $S$ , entonces $H$ tiene una coincidencia de arco iris.

Sea $H = (X + Y, E)$ un grafo bipartito que satisface la condición de Hall. Para cada vértice $i$ de $X$ , asigne un color único $V i$ a todas las aristas de $H$ adyacentes a $i$ . Para cada subconjunto $S$ de colores, la condición de Hall implica que $S$ tiene al menos $| S |$ vecinos en $Y$ , y por lo tanto hay al menos $| S |$ aristas de $H$ adyacentes a vértices distintos de $Y$ . Sea $I S$ un conjunto de $| S |$ tales aristas. Para cualquier coincidencia $J$ de tamaño como máximo $| S | - 1$ en $H$ , algún elemento $e$ de $I S$ tiene un punto final diferente en $Y$ que todos los elementos de $J$ , y por lo tanto $J \cup {e}$ también es una coincidencia, por lo que $I S$ es especial para $S$ . El teorema anterior implica que $H$ tiene un arco iris coincidente $M R$ . Por definición de los colores, $M R$ es una coincidencia perfecta en $H$ .

Otro corolario del teorema anterior es la siguiente condición, que involucra tanto el grado del vértice como la longitud del ciclo: ^[3]^{: Teorema 4.3}

Si el grado de cada vértice en $G$ es como máximo 2, y la longitud de cada ciclo de $G$ es divisible por 3, y el tamaño de cada conjunto de colores es al menos 3, entonces $G$ tiene una ISR.

Demostración. Para cada subconjunto $S$ de colores, el grafo $G S$ contiene al menos $3| S |$ vértices, y es una unión de ciclos de longitud divisible por 3 y caminos. Sea $I S$ un conjunto independiente en $G S$ que contiene cada tercer vértice en cada ciclo y cada camino. Entonces $| I S |$ contiene al menos $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}3| S | ⁄ 3 = | S |$ vértices. Sea $J$ un conjunto independiente en $G S$ de tamaño como máximo $| S | - 1$ . Como la distancia entre cada dos vértices de $I S$ es al menos 3, cada vértice de $J$ es adyacente a como máximo un vértice de $I S$ . Por lo tanto, hay al menos un vértice de $I S$ que no es adyacente a ningún vértice de $J$ . Por lo tanto, $I S$ es especial para $S$ . Por el teorema anterior, $G$ tiene una ISR.

Condición basada en la conectividad homológica

Una familia de condiciones se basa en la conectividad homológica del complejo de independencia de los subgrafos. Para enunciar las condiciones se utiliza la siguiente notación:

$Ind(G)$ denota el complejo de independencia de un grafo $G$ (es decir, el complejo simplicial abstracto cuyas caras son los conjuntos independientes en $G$ ).
$η H (X)$ denota la conectividad homológica de un complejo simplicial $X$ (es decir, el entero más grande $k$ tal que los primeros $k$ grupos de homología de $X$ son triviales), más 2.
$[m]$ es el conjunto de índices de colores, ${1, \dots, n}.$ Para cualquier subconjunto $J$ de $[m]$ , $V J$ es la unión de los colores $V J$ para $J$ en $J$ .
$G [V J]$ es el subgrafo de $G$ inducido por los vértices en $V J$ .

La siguiente condición está implícita en ^{[9] y se demuestra explícitamente en}^[10] .

Si, para todos los subconjuntos $J$ de $[m]$ :
$\eta _{H}({\text{Ind}}(G[V_{J}]))\geq |J|$
entonces la partición $V 1, \dots, V m$ admite un ISR.

Como ejemplo, ^[4] supongamos que $G$ es un grafo bipartito y sus partes son exactamente $V 1$ y $V 2$ . En este caso $[m] = {1,2}$ por lo que hay cuatro opciones para $J$ :

$J = {}:$ entonces $G [J] = {}$ e $Ind(G [J]) = {}$ y la conectividad es infinita, por lo que la condición se cumple trivialmente.
$J = {1}:$ entonces $G [J]$ es un grafo con vértices $V 1$ y sin aristas. Aquí todos los conjuntos de vértices son independientes, por lo que $Ind(G [J])$ es el conjunto potencia de $V 1$ , es decir, tiene un único $n$ -símplex (y todos sus subconjuntos). Se sabe que un único símplex es $k$ -conexo para todos los enteros $k$ , ya que todos sus grupos de homología reducidos son triviales (véase homología simplicial ). Por lo tanto, la condición se cumple.
$J = {2}:$ este caso es análogo al anterior.
$J = {1,2}:$ entonces $G [J] = G$ , e $Ind(G)$ contiene dos símplices $V 1$ y $V 2$ (y todos sus subconjuntos). La condición $η H (Ind(G)) \geq 2$ es equivalente a la condición de que la conectividad homológica de $Ind(G)$ sea al menos 0, lo que es equivalente a la condición de quesea el grupo trivial. Esto se cumple si y solo si el complejo $Ind($ $G$ $)$ contiene una conexión entre sus dos símplices $V$ $1$ y $V$ $2$ . Tal conexión es equivalente a un conjunto independiente en el que un vértice es de $V$ $1$ y uno es de $V$ $2$ . Por lo tanto, en este caso, la condición del teorema no solo es suficiente sino también necesaria. ${\tilde {H_{0}}}({\text{Ind}}(G))$

Otras condiciones

Todo grafo libre de triángulos correctamente coloreado de un número cromático $x$ contiene un conjunto independiente del arco iris de tamaño al menos $x$ $⁄$ $2$ . ^[11]

Varios autores han estudiado las condiciones de existencia de grandes conjuntos independientes del arco iris en varias clases de grafos. ^[1]^[12]

Cálculo

El problema de decisión ISR es el problema de decidir si un grafo dado $G = (V, E)$ y una partición dada de $V$ en $m$ colores admite un conjunto independiente del arco iris. Este problema es NP-completo . La prueba es por reducción del problema de emparejamiento tridimensional (3DM). ^[4] La entrada a 3DM es un hipergrafo tripartito $(X + Y + Z, F)$ , donde $X$ , $Y$ , $Z$ son conjuntos de vértices de tamaño $m$ , y $F$ es un conjunto de tripletes, cada uno de los cuales contiene un único vértice de cada uno de $X$ , $Y$ , $Z$ . Una entrada a 3DM se puede convertir en una entrada a ISR de la siguiente manera:

Para cada arista $(x, y, z)$ en $F$ , hay un vértice $v x,y,z$ en $V$ ;
Para cada vértice $z$ en $Z$ , sea $V z = {v x,y,z | x \in X, y \in Y}.$
Para cada $x$ , $y 1$ , $y 2$ , $z 1$ , $z 2$ , hay una arista $(v x, y 1, z 1, v x, y 2, z 2)$ en $E$ ;
Para cada $x 1$ , $x 2$ , $y$ , $z 1$ , $z 2$ , hay una arista $(v x 1, y, z 1, v x 2, y, z 2)$ en $E$ ;

En el gráfico resultante $G = (V, E)$ , un ISR corresponde a un conjunto de tripletes $(x, y, z)$ tales que:

Cada triplete tiene un valor $z$ diferente (ya que cada triplete pertenece a un conjunto de colores diferente $V z$ );
Cada triplete tiene un valor $x$ diferente y un valor $y$ diferente (ya que los vértices son independientes).

Por lo tanto, el grafo resultante admite un ISR si y sólo si el hipergrafo original admite un 3DM.

Una prueba alternativa es por reducción de SAT . ^[3]

Conceptos relacionados

Si $G$ es el grafo lineal de algún otro grafo $H$ , entonces los conjuntos independientes en $G$ son las correspondencias en $H$ . Por lo tanto, un conjunto independiente del arco iris en $G$ es una correspondencia arco iris en $H$ . Véase también correspondencia en hipergrafos .

Otro concepto relacionado es el ciclo del arco iris , que es un ciclo en el que cada vértice tiene un color diferente. ^[13]

Cuando existe un ISR, una pregunta natural es si existen otros ISR, de modo que todo el conjunto de vértices se divida en ISR disjuntos (suponiendo que la cantidad de vértices en cada color sea la misma). Tal partición se denomina coloración fuerte .

Usando la metáfora de la facultad: ^[3]

Un sistema de representantes distintos es un comité de miembros distintos, con o sin conflictos.
Un conjunto independiente es un comité sin conflicto.
Una transversal independiente es un comité sin conflicto, con exactamente un miembro de cada departamento.
La coloración de un gráfico es una partición de los miembros de la facultad en comités sin conflictos.
Una coloración fuerte es una división de los miembros del profesorado en comités sin conflictos y con exactamente un miembro de cada departamento. Por eso, este problema a veces se denomina el problema del decano feliz .

Una camarilla arcoíris o una camarilla colorida es una camarilla en la que cada vértice tiene un color diferente. ^[10] Cada camarilla en un grafo corresponde a un conjunto independiente en su grafo complementario . Por lo tanto, cada camarilla arcoíris en un grafo corresponde a un conjunto independiente del arcoíris en su grafo complementario.

Véase también

Referencias

^ ab Aharoni, Ron; Briggs, Joseph; Kim, Jinha; Kim, Minki (28 de septiembre de 2019). "Conjuntos independientes del arco iris en ciertas clases de grafos". arXiv : 1909.13143 [math.CO].
^ Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (1 de octubre de 2017). "Sobre una conjetura de Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. doi :10.1007/s12188-016-0160-3. ISSN 1865-8784. S2CID 119139740.
^ abcdef Haxell, P. (1 de noviembre de 2011). "Sobre la formación de comités". The American Mathematical Monthly . 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
^ abcd Aharoni, Ron; Berger, Eli; Ziv, Ran (1 de mayo de 2007). "Sistemas independientes de representantes en gráficos ponderados". Combinatoria . 27 (3): 253–267. doi :10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.
^ E, HaxellP (1 de julio de 2001). "Una nota sobre la coloración de listas de vértices". Combinatoria, probabilidad y computación . 10 (4): 345–347. doi :10.1017/s0963548301004758. S2CID 123033316.
^ Szabó*, Tibor; Tardos†, Gábor (1 de junio de 2006). "Problemas extremos para transversales en grafos con grado acotado". Combinatorica . 26 (3): 333–351. doi :10.1007/s00493-006-0019-9. hdl : 20.500.11850/24692 . ISSN 1439-6912. S2CID 15413015.
^ Haxell, Penny; Szabó, Tibor (1 de enero de 2006). "Las transversales independientes impares son impares". Combinatoria, probabilidad y computación . 15 (1–2): 193–211. doi :10.1017/S0963548305007157 (inactivo el 1 de noviembre de 2024). ISSN 1469-2163. S2CID 6067931.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)
^ Berke, Robert; Haxell, Penny; Szabó, Tibor (2012). "Transversales acotadas en grafos multipartitos". Revista de teoría de grafos . 70 (3): 318–331. doi :10.1002/jgt.20618. ISSN 1097-0118. S2CID 17608344.
^ ab Aharoni, Ron; Haxell, Penny (2000). "Teorema de Hall para hipergrafos". Revista de teoría de grafos . 35 (2): 83–88. doi :10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.
^ ab Meshulam, Roy (1 de enero de 2001). "El complejo de camarillas y la correspondencia de hipergrafos". Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.
^ Aravind, NR; Cambie, Stijn; van Batenburg, Wouter Cames; de Verclos, Rémi de Joannis; Kang, Ross J.; Patel, Viresh (15 de marzo de 2020). "Estructura y color en gráficos sin triángulos". arXiv : 1912.13328 [matemáticas.CO].
^ Kim, Jinha; Kim, Minki; Kwon, O.-joung (5 de febrero de 2020). "Conjuntos independientes del arco iris en clases de grafos densos". arXiv : 2001.10566 [math.CO].
^ Aharoni, Ron; Briggs, José; Holzman, Ron; Jiang, Zilin (2021). "Ciclos impares del arco iris". Revista SIAM de Matemática Discreta . 35 (4): 2293–2303. arXiv : 2007.09719 . doi :10.1137/20M1380557. S2CID 220647170.