Demostrar que el polinomio cromático de un gráfico de ciclo $C_{n}$ es igual a $(k-1)^{n} + (k-1)(-1)^{n}$

Question

Esta es una pregunta de deberes. Pero estoy completamente atascado.

Mi única intuición era hacerlo de forma inductiva a partir de un "algoritmo codicioso" tal vez conocido como el algoritmo de borrado-contracción. Y utilizar de alguna manera la información sobre el jº ciclo para resolver el j+1º. Pero no estoy seguro de cómo lo haría. Muchas gracias por revisar esto.

Answer 1

Denotemos $P(G,k)$ sea el polinomio cromático de un grafo simple $G$ . Por fórmula de supresión-contracción dada cualquier arista $e$ en $G$ Tenemos lo siguiente: $$P(G,k)=P(G-e,k)-P(G\cdot e, k)$$ donde $G-e$ es el gráfico que se obtiene al eliminar $e$ en $G$ y $G\cdot e$ es el gráfico que se obtiene al contraer $e$ en $G$ .

Para demostrar que $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$ utilizamos la inducción sobre $n$ . Para $n=3$ es fácil ver que necesitamos usar diferentes colores para diferentes vértices. Por lo tanto, $$P(C_3,k)=k(k-1)(k-2)=(k-1)(k^2-2k)=(k-1)^3+(-1)^3(k-1).$$ Esto demuestra el caso cuando $n=3$ .

Supongamos ahora que $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$ . Aplicar la fórmula de supresión-contracción a $G=C_{n+1}$ tenemos $$P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k).$$ Obsérvese que el gráfico $C_{n+1}\cdot e$ se obtiene contrayendo una arista $e$ en $C_{n+1}$ que es isomorfo a $C_n$ lo que implica que $$P(C_{n+1}\cdot e, k)=P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1).$$ Tenga en cuenta también que $C_{n+1}-e$ es el camino $P_{n+1}$ con $n+1$ vértices, lo que implica que $$P(C_{n+1}-e, k)=P(P_{n+1},k)=k(k-1)^n.$$ (Para ver la última igualdad, podemos usar la inducción sobre el número de vértices, o por simple argumento de conteo: para colorear el vértice final, hay $k$ colores que podemos elegir, entonces para el siguiente incidente al vértice final, hay $k-1$ colores que podemos elegir, etc.) Combinando todo esto, tenemos $$P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k)$$ $$=k(k-1)^n-(k-1)^{n}-(-1)^{n}(k-1)=(k-1)^{n+1} + (-1)^{n+1}(k-1),$$ según sea necesario.

Answer 2

Vas por buen camino. Hasta donde yo sé, el algoritmo codicioso para encontrar un colorido y el algoritmo de supresión-contracción para contarlos son dos algoritmos bastante distintos. El algoritmo de supresión-contracción es exactamente lo que necesitas. Si eliminas una arista de un ciclo, las coloraciones del gráfico restante son fáciles de contar, mientras que si contraes una arista, obtienes un ciclo con un vértice menos. Así se obtiene una relación de recurrencia que expresa el número de coloraciones de $C_n$ como el número de coloraciones de $C_{n-1}$ más una expresión conocida. Entonces, como ya conoces la solución, sólo tienes que verificar que resuelve esta recurrencia, y que es correcta para $n=2$ .

Answer 3

También puedes hacerlo directamente utilizando el principio de inclusión-exclusión. Etiqueta los vértices de $C_n$ secuencialmente utilizando los enteros $0$ , $1$ , ..., $n-1$ . Para $S\subseteq\{0,1,\ldots,n-1\}$ , dejemos que $T_S$ sea el conjunto de coloraciones (propias o impropias) de $C_n$ en la que, para cada $j\in S$ el color del vértice $j$ es la misma que la del vértice $j-1$ (con la aritmética realizada mod $n$ ). El número de coloraciones adecuadas es entonces $$ \lvert T_{\{\}}\rvert-\sum_{i=0}^{n-1}\lvert T_{\{i\}}\rvert+\sum_{0\le i<j<n}\lvert T_{\{i,j\}}\rvert-\ldots+(-1)^n\lvert T_{\{0,1,\ldots,n-1\}}\rvert. $$ Ahora hay $\binom{n}{m}$ diferentes $S$ de tamaño $m$ . Además, $$ \lvert T_S\rvert=\begin{cases}k^{n-\lvert S\rvert} & \text{if $\lvert S \rvert <n $,}\\ k & \text{if $ S=\{0,1, \ldots ,n-1\} $.}\end{cases} $$ Por lo tanto, el número de coloraciones adecuadas es $$ (-1)^nk+\sum_{m=0}^{n-1}\binom{n}{m}k^{n-m}(-1)^m $$ El resultado se deduce inmediatamente del teorema del binomio.