Polinomio cromático

Un polinomio cromático es un polinomio estudiado en la teoría algebraica de grafos que representa el número de colores de un gráfico en función del número de colores. Originalmente definido por George Birkhoff como un intento de resolver el problema de los cuatro colores . Generalizado y estudiado sistemáticamente por Hassler Whitney , Tutt generalizó el polinomio cromático al polinomio de Tutt relacionándolo con el modelo Potts física estadística .

Historia

George Birkhoff introdujo el polinomio cromático en 1912, definiéndolo solo para gráficos planos en un intento de probar el teorema de los cuatro colores . Si denota el número de colores correctos del gráfico G con k colores, entonces se podría probar el teorema de los cuatro colores mostrando que para todos los gráficos planos G . De esta manera esperaba utilizar el poder del cálculo y el álgebra para estudiar las raíces de polinomios para estudiar el problema de coloración combinatoria. ${\ Displaystyle PAG (G, k)}$ $P(G,4)>0$

Hassler Whitney generalizó el polinomio de Birkhoff del caso plano a gráficos generales en 1932. En 1968, Reed planteó la cuestión de qué polinomios son polinomios cromáticos para algunos gráficos (el problema permanece abierto) e introdujo la noción de gráficos cromáticamente equivalentes. Actualmente, los polinomios cromáticos son los objetos centrales de la teoría algebraica de grafos [1] .

Definición

El polinomio cromático de un grafo G cuenta el número de colores de vértice correctos . Un polinomio generalmente se denota como , o . Esta última notación se utilizará en el resto del artículo. $P_{G}(k)$ ${\ estilo de visualización \ chi _ {G} (k)}$ ${\ estilo de visualización \ pi _ {G} (k)}$ ${\ Displaystyle PAG (G, k)}$

Por ejemplo, un camino con 3 vértices no se puede colorear con 0 colores o 1 color. Usando 2 colores, el gráfico se puede colorear de dos maneras. Usando 3 colores, el gráfico se puede colorear de 12 maneras. $P_{3}$

Colores disponibles $k$	0	una	2	3
Número de páginas para colorear $P(P_{3},k)$	0	0	2	12

Dado un grafo G con n vértices, un polinomio cromático se define como un único polinomio interpolador de grado máximo n que pasa por los puntos

\left\{(0,P(G,0)),(1,P(G,1)),\cdots,(n,P(G,n))\right\}.

Si el gráfico G no contiene vértices con bucles, entonces el polinomio cromático es un polinomio reducido de grado exactamente n . De hecho, para el ejemplo anterior, tenemos

P(P_{3},t)=t(t-1)^{2},\qquad P(P_{3},3)=12.

Un polinomio cromático contiene al menos tanta información sobre la colorabilidad del gráfico G como la que contiene el número cromático. Además, el número cromático es el entero positivo más pequeño para el cual el polinomio cromático no se anula,

{\displaystyle\chi(G)=\min\{k:P(G,k)>0\}.}

Ejemplos

Polinomios cromáticos para algunas gráficas

Triángulo $K_{3}$	$t(t-1)(t-2)$
Gráfico completo $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
Sendero $P_{n}$	$t(t-1)^{{n-1}}$
Cualquier árbol con n vértices	$t(t-1)^{{n-1}}$
Ciclo $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Conde de Petersen	$t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{ 2}+775t-352\derecha)$

Propiedades

Para un grafo fijo G con n vértices, el polinomio cromático es, de hecho, un polinomio de grado n . Por definición, el cálculo del valor del polinomio da el número de k -coloraciones del gráfico G para . Lo mismo es cierto para k > n . ${\ Displaystyle PAG (G, t)}$ ${\ Displaystyle PAG (G, k)}$ $k=0,1,\cdots,n$

Expresión

(-1)^{|V(G)|}P(G,-1)

da el número de orientaciones acíclicas del gráfico G [2] .

El valor de la derivada del polinomio en el punto 1 es igual, hasta un signo, al invariante cromático . ${\ estilo de visualización P' (G, 1)}$ ${\ estilo de visualización \ theta (G)}$

Si un grafo G tiene n vértices, m aristas y c componentes , entonces $G_{1},\cdots,G_{c}$

Los coeficientes para son iguales a cero. ${\displaystyle t^{0},\cdots,t^{c-1))$
Los coeficientes para son todos distintos de cero. ${\displaystyle t^{c},\cdots,t^{n))$
El coeficiente at es igual a 1. $t^{n}$ ${\ Displaystyle PAG (G, t)}$
El coeficiente at es igual a . ${\ estilo de visualización t^{n-1}}$ ${\ Displaystyle PAG (G, t)}$ ${\ estilo de visualización -m}$
Los coeficientes de cualquier polinomio cromático son de signos alternos.
Los valores absolutos de los coeficientes de cualquier polinomio cromático forman una secuencia logarítmicamente cóncava [3] .
$P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$

Un grafo G con n vértices es un árbol si y solo si

P(G,t)=t(t-1)^{n-1}.

Equivalencia cromática

Se dice que dos gráficos son cromáticamente equivalentes si tienen los mismos polinomios cromáticos. Los gráficos isomorfos tienen los mismos polinomios cromáticos, pero los gráficos no isomorfos pueden ser cromáticamente equivalentes. Por ejemplo, todos los árboles con n vértices tienen los mismos polinomios cromáticos:

{\ estilo de visualización (x-1) ^ {n-1} x,}

En particular,

{\ estilo de visualización (x-1) ^ {3} x}

es un polinomio cromático tanto para la garra como para el camino de 4 vértices .

Singularidad cromática

Un grafo es cromáticamente único si está definido por un polinomio cromático hasta el isomorfismo. En otras palabras, si el gráfico G es cromáticamente único, entonces G y H son isomorfos. ${\ Displaystyle P (G, t) = P (H, t)}$

Todos los ciclos son cromáticamente únicos [4] .

Raíces cromáticas

La raíz (o cero ) de un polinomio cromático (llamado "raíz cromática") es un valor de x para el cual . Las raíces cromáticas están bien estudiadas. De hecho, la motivación original de Birkhoff para introducir el polinomio cromático fue mostrar que para gráficos planos para x ≥ 4. Esto probaría el teorema de los cuatro colores . $P(G,x)=0$ $P(G,x)>0$

Ningún gráfico se puede colorear con 0 colores, por lo que 0 siempre es una raíz cromática. Solo los gráficos sin bordes pueden ser de un solo color, por lo que 1 es la raíz cromática de cualquier gráfico con al menos un borde. Por otro lado, a excepción de estos dos casos, ningún grafo puede tener como raíz cromática un número real menor o igual a 32/27 [5] . El resultado de Tatta relaciona la proporción áurea con el estudio de las raíces cromáticas, mostrando que las raíces cromáticas existen muy cerca de : si es una triangulación plana de una esfera, entonces $\fi$ ${\ estilo de visualización \ phi ^ {2}}$ $G_{n}$

P(G_{n},\phi ^{2})\leq \phi ^{5-n}.

Si bien la línea real tiene grandes porciones que no contienen raíces cromáticas para ningún gráfico, cualquier punto en el plano complejo está arbitrariamente cerca de una raíz cromática en el sentido de que hay una familia infinita de gráficos cuyas raíces cromáticas son densas en el plano complejo. .plano [6] .

Categorización

El polinomio cromático se categoriza utilizando la teoría de la homología, estrechamente relacionada con la homología de Khovanov [7] .

Algoritmos

polinomio cromático
Entrada	Grafica G con n vértices.
Salida	Posibilidades ${\ Displaystyle PAG (G, t)}$
Horas Laborales	${\ estilo de visualización O (2 ^ {n} n ^ {r})}$ por alguna constante $r$
Complejidad	#P es dificil
Reducido de	#3SAT

#k-colorear
Entrada	Grafica G con n vértices.
Salida	${\ Displaystyle PAG (G, k)}$
Horas Laborales	Pertenece a P para . para _ De lo contrario ${\ estilo de visualización k = 0,1,2}$ ${\ estilo de visualización O (1 {,} 6262 ^ {n})}$ $k=3$ ${\ estilo de visualización O (2 ^ {n} n ^ {r})}$ por alguna constante $r$
Complejidad	#P es difícil hasta ahora ${\ estilo de visualización k = 0,1,2}$
Aproximabilidad	Sin FPRAS para ${\ Displaystyle k> 2}$

Problemas computacionales relacionados con polinomios cromáticos

encontrar un polinomio cromático para un gráfico G dado ; ${\ Displaystyle PAG (G, t)}$
cálculo en un punto fijo k para un gráfico dado G . ${\ Displaystyle PAG (G, k)}$

El primer problema es más general, ya que conociendo los coeficientes podemos calcular el valor del polinomio en cualquier punto del tiempo del polinomio. La complejidad computacional del segundo problema depende fuertemente del valor de k . Cuando k es un número natural, se puede pensar en el problema como calcular el número de k -coloraciones de un gráfico dado. Por ejemplo, el problema incluye contar 3 colores como un problema canónico para estudiar la complejidad del conteo. Esta tarea está completa en la clase #P . ${\ Displaystyle PAG (G, t)}$

Algoritmos eficientes

Para algunas clases básicas de gráficos, se conocen fórmulas explícitas para polinomios cromáticos. Por ejemplo, esto es cierto para los árboles y las camarillas, como se muestra en la tabla anterior.

Hay algoritmos de tiempo polinomial conocidos para calcular el polinomio cromático para una amplia clase de gráficos, que incluye gráficos cordales [8] y gráficos con ancho de camarilla limitado [9] [10] . La segunda de estas clases, a su vez, incluye cografos y gráficos con un ancho de árbol acotado , como los gráficos planos exteriores .

Hay personas en Internet que están tratando de resolver el problema de forma colectiva, y son ayudados por ayudantes autónomos activos, especialmente para polinomios cromáticos de alto grado [11] .

Eliminación - contracción

La forma recursiva de calcular un polinomio cromático se basa en la contracción de la arista , para un par de vértices , y el gráfico se obtiene fusionando dos vértices y eliminando la arista entre ellos. El polinomio cromático satisface la relación recursiva $tu$ $v$ $jefe$

P(G,k)=P(G-uv,k)-P(G/uv,k)

donde y son vértices adyacentes y es un gráfico con la arista eliminada . Equivalentemente, $tu$ $v$ $G-uv$ $ultravioleta$

P(G,k)=P(G+uv,k)+P(G/uv,k)

si y no son adyacentes y es un gráfico con una arista añadida . En la primera forma, la recursividad se detiene en el conjunto de grafos vacíos. Estas relaciones recurrentes también se denominan teorema de reducción fundamental [12] . La pregunta de Tutt sobre qué otras propiedades gráficas satisfacen las mismas relaciones de recurrencia condujo al descubrimiento de una generalización de dos variables del polinomio cromático, el polinomio de Tutt . $tu$ $v$ $G+uv$ $ultravioleta$

Las expresiones dan un procedimiento recursivo llamado algoritmo de eliminación-contracción , que es la base de muchos algoritmos de coloreado de gráficos. La función ChromaticPolynomial en el sistema de álgebra computacional de Mathematica usa la segunda fórmula recursiva si el gráfico es denso, y la primera si el gráfico es disperso [13] . El peor tiempo de ejecución para ambas fórmulas satisface la relación de recurrencia de los números de Fibonacci , de modo que, en el peor de los casos, el algoritmo se ejecuta en el tiempo (hasta algún factor polinomial)

\phi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1{ ,}62^{n+m}\derecho)

en un gráfico con n vértices y m aristas [14] . El análisis del tiempo de ejecución se puede mejorar a un factor polinomial del número de árboles de expansión del gráfico de entrada [15] . En la práctica, se usa una estrategia de ramificación y límite , junto con la caída de gráficos isomorfos , para eliminar las llamadas recursivas, y el tiempo depende de la heurística utilizada para elegir un par de vértices (para soltar y tirar). ${\ estilo de visualización t (G)}$

Método del cubo

Existe un enfoque geométrico natural para colorear gráficos, si observa que cuando asigna números naturales a cada vértice, el color de los gráficos es un vector de una red de enteros. Dado que asignar dos vértices y el mismo color equivale a la igualdad de coordenadas y en el vector de coloración, cada arista se puede asociar a un hiperplano de la forma . El conjunto de tales hiperplanos para un gráfico dado se llama su configuración gráfica de hiperplanos . Una coloración adecuada de un gráfico es una coloración cuyo vector no aparece en el plano prohibido. Restringido por muchos colores , los puntos de la red caen en un cubo . En este contexto, el polinomio cromático cuenta los puntos de la cuadrícula en el cubo que no entran en la configuración gráfica. $i$ $j$ $i$ $j$ $\{x\in R^{d}:x_{i}=x_{j}\}$ $k$ ${\ estilo de visualización [0, k] ^ {n})$ ${\ estilo de visualización [0, k]}$

Complejidad computacional

El problema de calcular el número de 3-coloraciones de un gráfico dado es un ejemplo canónico de un problema #P-completo, por lo que el problema de calcular los coeficientes de un polinomio cromático es #P-difícil. De manera similar, el cálculo para un gráfico G dado es #P-completo. Por otro lado, es fácil de calcular para , por lo que los problemas correspondientes tienen una complejidad de tiempo polinomial. Para números enteros, el problema es #P-hard, que se establece de manera similar al caso . De hecho, se sabe que es #P-hard para todo x (incluidos los números enteros negativos e incluso todos los números complejos), a excepción de tres "puntos primos" [16] . Por lo tanto, la complejidad de calcular un polinomio cromático es completamente comprensible. ${\ estilo de visualización PAG (G, 3)}$ ${\ estilo de visualización k = 0,1,2}$ ${\ Displaystyle PAG (G, k)}$ ${\ Displaystyle k> 3}$ $k=3$ ${\ estilo de visualización P (G, x)}$

en un polinomio

P(G,t)=a_{1}t+a_{2}t^{2}+\puntos +a_{n}t^{n},

el coeficiente es siempre 1 y también se conocen algunas otras propiedades de los coeficientes. Esto plantea la cuestión de si algunos coeficientes se pueden calcular de forma más sencilla. Sin embargo, el problema de calcular a r para una r fija y un gráfico G dado es #P-difícil [17] . $un$

No se conoce ningún algoritmo de cálculo aproximado para cualquier x , excepto para tres puntos simples. En puntos enteros , el problema de resolución correspondiente de determinar si un gráfico dado se puede colorear con k colores es NP-difícil . Dichos problemas no pueden ser aproximados por ningún factor con un algoritmo probabilístico polinomial de error limitado, excepto NP = RP, ya que cualquier aproximación multiplicativa distinguiría entre 0 y 1, lo que sería una solución eficiente del problema con un algoritmo probabilístico polinomial de error acotado en el forma del problema de solución . En particular, bajo algunas suposiciones, esto excluye la posibilidad de un esquema de aproximación aleatoria completamente polinomial (FPRAS) . Para otros puntos, se necesita un razonamiento más complejo y el tema está en el centro de una investigación activa. A partir de 2008, se sabe que no existe un esquema FPRAS para calcular cualquier x > 2, excepto para NP = RP [18] . ${\ estilo de visualización P (G, x)}$ ${\ estilo de visualización k = 3,4, \ puntos}$ ${\ estilo de visualización P (G, x)}$

Notas

↑ Biggs, 1993 , pág. Algunos capítulos.
↑ Stanley, 1973 .
↑ Eh, 2012 .
↑ Chao, Whitehead, 1978 .
↑ Jackson, 1993 .
↑ Sokal, 2004 .
↑ Helme-Guizón, Rong, 2005 .
↑ Naor, Naor, Schaffer, 1987 .
↑ Giménez, Hliněny, Noy, 2005 .
↑ Makowsky, Rotics, Averbouch, Godlin, 2006 .
↑ Shirado, Christakis, 2017 , pág. 370–374.
↑ Dong, Koh, Teo, 2005 .
↑ Pemmaraju, Skiena, 2003 .
↑ Wilf, 1986 .
↑ Sekine, Imai, Tani, 1995 .
↑ Jaeger, Vertigan and Welsh ( Jaeger, Vertigan, Welsh 1990 ), basado en la mezcla de Linial ( Linial 1986 ).
↑ Oxley, galés, 2002 .
↑ Goldberg, Jerrum, 2008 .

Literatura

A. Yu. Evnin. Polinomio cromático de un grafo en problemas // Educación matemática . - 2014. - Nº 4 (72) . - S. 9-15 . (Ruso)
Biggs N. Teoría de grafos algebraicos. - Prensa de la Universidad de Cambridge, 1993. - ISBN 0-521-45897-8 .
Hirokazu Shirado, Nicholas A. Christakis. Agentes autónomos localmente ruidosos mejoran la coordinación humana global en experimentos de red // Naturaleza. - 2017. - T. 545 , núm. 7654 . — S. 370–374 . -doi : 10.1038/ naturaleza22332 .
Chao C.-Y., Whitehead EG Sobre la equivalencia cromática de gráficos // Teoría y aplicaciones de gráficos. - Springer, 1978. - T. 642. - S. 121-131. — (Apuntes de clase en Matemáticas). - ISBN 978-3-540-08666-6 .
Dong FM, Koh KM, Teo KL Polinomios cromáticos y cromaticidad de gráficos. - Compañía editorial científica mundial, 2005. - ISBN 981-256-317-2 .
Giménez O., Hliněný P., Noy M. Cálculo del polinomio de Tutte en gráficos de ancho de camarilla acotado // Proc. 31 Int. trabajo Conceptos teóricos de grafos en informática (WG 2005). - Springer-Verlag, 2005. - T. 3787. - S. 59–68. -doi : 10.1007/ 11604686_6 .
Goldberg LA, Jerrum M. Inaproximabilidad del polinomio de Tutte // Información y computación. - 2008. - T. 206 , núm. 7 . - S. 908 . -doi : 10.1016/ j.ic.2008.04.003 .
Laure Helme-Guizon, Yongwu Rong. Una categorización del polinomio cromático // Topología algebraica y geométrica. - 2005. - V. 5 , núm. 4 . - S. 1365-1388 . -doi : 10.2140 / agt.2005.5.1365 .
Huh J. Milnor números de hipersuperficies proyectivas y el polinomio cromático de grafos. — arXiv:1008.4749v3, 2012.
Jackson B. Un intervalo libre de cero para polinomios cromáticos de gráficos // Combinatoria, probabilidad y computación. - 1993. - T. 2 . — S. 325–336 . - doi : 10.1017/S0963548300000705 .
Jaeger F., Vertigan DL, Welsh DJA Sobre la complejidad computacional de los polinomios de Jones y Tutte // Procedimientos matemáticos de la Sociedad Filosófica de Cambridge. - 1990. - T. 108 . — págs. 35–53 . -doi : 10.1017/ S0305004100068936 .
Linial N. Problemas de enumeración dura en geometría y combinatoria // SIAM J. Métodos discretos algebraicos. - 1986. - T. 7 , núm. 2 . — S. 331–335 . -doi : 10.1137/ 0607036 .
Makowsky JA, Rotics U., Averbouch I., Godlin B. Computación de polinomios gráficos en gráficos de ancho de camarilla acotado // Proc. 32 Int. trabajo Conceptos teóricos de grafos en informática (WG 2006). - Springer-Verlag, 2006. - T. 4271. - S. 191-204. — (Apuntes de clase en informática). -doi : 10.1007/ 11917496_18 .
Naor J., Naor M., Schaffer A. Algoritmos paralelos rápidos para grafos cordales // Proc. 19º ACM Symp. Teoría de la Computación (STOC '87). - 1987. - S. 355-364. doi : 10.1145 / 28395.28433 .
Oxley JG, Welsh DJA Polinomios cromáticos, de flujo y de confiabilidad: La complejidad de sus coeficientes. // Combinatoria, Probabilidad y Computación . - 2002. - T. 11 , núm. 4 . — Pág. 403–426 .
Pemmaraju S., Skiena S. sección 7.4.2 // Matemática discreta computacional: combinatoria y teoría de grafos con Mathematica. - Prensa de la Universidad de Cambridge, 2003. - ISBN 0-521-80686-0 .
Sekine K., Imai H., Tani S. Computing the Tutte polynomial of a graph of moderado size // Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004. — Cairns, Australia, 4 al 6 de diciembre de 1995: Springer, 1995, págs. 224–233.
Las raíces cromáticas Sokal AD son densas en todo el plano complejo // Combinatoria, probabilidad y computación . - 2004. - T. 13 , núm. 2 . — S. 221–261 . - doi : 10.1017/S0963548303006023 .
Stanley R.P. Orientaciones acíclicas de gráficos // Disc. Matemáticas. . - 1973. - V. 5 , núm. 2 . — S. 171–178 . - doi : 10.1016/0012-365X(73)90108-8 .
Vitali I Voloshin. Hipergrafías mixtas para colorear: teoría, algoritmos y aplicaciones .. - American Mathematical Society, 2002. - ISBN 0-8218-2812-6 .
Algoritmos y complejidad de Wilf HS . - Prentice-Hall, 1986. - ISBN 0-13-021973-8 .

Enlaces

Weisstein, Eric W. Polinomio cromático (inglés) en el sitio web Wolfram MathWorld .
Polinomio cromático de PlanetMath
Código para calcular polinomios Tutte, Chromatic y Flow de Gary Haggard, David J. Pearce y Gordon Royle: [1] (enlace no disponible)