Polinomio cromatico de un cuadrado

11

Considere un cuadrado, ABCD. Intuitivamente me pareció que su polinomio cromático es donde hay colores disponibles.λ(λ1)(λ1)(λ2)λ

Es decir, hay formas en que se puede elegir un color para A, hay formas para elegir los colores para B y D (B y D son adyacentes a A) y formas para colores para que C sea recogido.λλ1λ2

Sin embargo, usar el teorema de descomposición (diapositiva 47, ejemplo 11.33) y descomponer el cuadrado en una ruta de longitud 3 y un triángulo, muestra que mi razonamiento inicial es incorrecto.

¿Podría decirme dónde me estoy equivocando con mi pensamiento?

Abhijith Madhav
fuente

Respuestas:

8

¡Debes recordar que los vértices diagonales uno del otro pueden ser del mismo color! Su fórmula no tiene eso en cuenta. Podemos encontrar el número cromático de un gráfico a través del principio de inclusión-exclusión. Es una técnica de conteo muy general que nos permite contar estructuras complejas, si podemos probar ciertos límites en ciertos subconjuntos.

La idea principal es que contamos todas las formas posibles en que ocurre una propiedad. Luego eliminamos algunos elementos "malos". Sin embargo, es posible que hayamos eliminado demasiado y necesitemos agregar algunos artículos "buenos". Esto va y viene hasta que hayamos pasado por todos los subconjuntos.

El principio de inclusión-exclusión nos dice que dado un conjunto básico , el número de elementos de que no se encuentran en ninguno de los subconjuntos es X A i I [ n ] ( - 1 ) | Yo | El | A I | , dónde |X|=nXAi

I[n](1)|I||AI|, where I is the set of indices in X and AI=iIAi

Sea el número de colores, y sea el conjunto de todos los colores posibles (es decir, ), y seaλX|X|=λ4

Ae={coloring:e=(i,j)E,color(i)=color(j)}

Antes de obtener nuestro polinomio final, necesitamos contar el tamaño de nuestros conjuntos , y el tamaño de todos los subconjuntos que se cruzan.Ae

Observe que . Esto se debe al hecho de que solo coloreamos pero siempre elegimos los mismos colores para los vértices vecinos. En adelante tenemos,|A12|=|A23|=|A34|=|A41|=λ3G

|A12A23|=|A23A34|=|A34A41|=|A41A12|=|A12A34|=|A41A23|=λ2

No voy a enumerar cada conjunto de 3, pero todos tienen el mismo recuento. . Y finalmente, . Ahora recopilemos nuestros términos y sumemos.|AeAeAe|=λ|A12A23A34A41|=λ

λ44λ3+6λ24λ+λ=λ44λ3+6λ23λ

Ahora contar con inclusión-exclusión para este problema no fue tan malo porque teníamos un ciclo simple de 4 ciclos. Si el gráfico tuviera más estructura, rápidamente sería molesto descubrir cada tamaño de intersección para todas las intersecciones posibles.

Nicholas Mancuso
fuente
2

La respuesta de Nicholas arriba y esta me ayudó a ver la falla en mi pensamiento. Pensé en elaborar más específicamente sobre Nicholas '

Debes recordar que los vértices diagonales uno del otro pueden ser del mismo color.

y también obtener el polinomio cromático ajustándome a mi razonamiento incorrecto.

Inicialmente pensé que hay formas de elegir colores para C. El "-2" explicaba que los colores eran diferentes de los de B y D. Lo que no pensé es que B y D pueden tener mismos colores en cuyo caso solo habría forma de elegir colores para C. Asíλ2λ1

P(ABCD,λ) = Número de formas de colorear correctamente ABCD cuando B y D son del mismo color + Número de formas de colorear correctamente ABCD cuando B y D tienen un color diferente
=λ(λ1)(1)(λ1)+λ(λ1)(λ2)(λ2)

Abhijith Madhav
fuente