La hipótesis de Hedetniemi

La conjetura de Hedetniemi es una hipótesis matemática , generalmente refutada, una suposición sobre la relación entre la coloración del gráfico y el producto del tensor del gráfico :

{\displaystyle \chi (G\times H)=\min\{\chi (G),\chi (H)\))

donde es el número cromático de un grafo finito no dirigido . $\ chi (G)$ $GRAMO$

Formulado por Stephen Hedetniemi en 1966 .

En 2019, el matemático ruso Yaroslav Shitov refutó la conjetura proponiendo un contraejemplo [1] [2] .

La desigualdad es fácil de confirmar: si el gráfico está coloreado en colores, puede colorearse en colores usando el mismo color para cada copia en el producto, el razonamiento simétrico implica una restricción en . Por lo tanto, la conjetura de Hedetniemi establece que los productos tensoriales no se pueden colorear con un número de colores inesperadamente pequeño. ${\displaystyle \chi (G\times H)\leqslant \min\{\chi (G),\chi (H)\))$ $GRAMO$ $k$ $G\veces H$ $k$ $GRAMO$ $H$

Casos especiales en los que la hipótesis es verdadera

Cualquier gráfico con un conjunto de bordes no vacío requiere al menos dos colores. Si y no es 1-coloreable, es decir, ambos contienen un borde, entonces su producto también contiene un borde y, por lo tanto, tampoco es 1-colorable. En particular, la conjetura es verdadera cuando o son grafos bipartitos, ya que entonces su número cromático es 1 o 2. $GRAMO$ $H$ $GRAMO$ $H$

De manera similar, si dos gráficos y no son de 2 colores, es decir, no son bipartitos , entonces ambos contienen un ciclo de longitud impar. Dado que el producto de dos ciclos impares contiene un ciclo impar, el producto tampoco puede ser de 2 colores. En otras palabras, si es de 2 colores, entonces al menos uno de los gráficos o debe ser de 2 colores. $GRAMO$ $H$ $G\veces H$ $G\veces H$ $GRAMO$ $H$

El siguiente caso fue probado mucho más tarde por la formulación de la conjetura de El-Zahar y Sauer [3] : si un producto se puede colorear con 3 colores, entonces uno de los gráficos o también debe permitir colorear con 3 colores. En particular, la conjetura es verdadera cuando o permite una coloración de 4 colores (porque entonces la desigualdad solo puede ser estricta cuando permite una coloración de 3 colores). De lo contrario, ambos gráficos en un producto tensorial deben tener al menos 5 colores, y solo se avanza en situaciones muy limitadas. $G\veces H$ $GRAMO$ $H$ $GRAMO$ $H$ ${\displaystyle \chi (G\times H)\leqslant \min\{\chi (G),\chi (H)\))$ $G\veces H$

Conjetura débil de Hedetniemi

La siguiente función (conocida como la función de Polak-Rödl ) mide qué tan pequeño puede ser el número cromático de un producto de gráficos cromáticos. $norte$

{\displaystyle f(n)=\min\{\chi (G\times H):\chi (G)=\chi (H)=n\))

La conjetura de Hedetniemi es entonces equivalente a decir que . En cambio, la conjetura débil de Hedetniemi simplemente establece que la función no tiene límites. En otras palabras, si el producto tensorial de dos gráficos se puede colorear con múltiples colores, esto debería implicar una restricción en el número cromático de uno de los factores. ${\ estilo de visualización f (n) = n}$ $f(n)$

El resultado principal de Polak y Rödl [4] , mejorado independientemente por Polak, Schmerl y Zu, establece que si una función está acotada, entonces está acotada como máximo por 9. Entonces, la prueba de la conjetura de Hedetniemi para gráficos de 10 cromáticas implicaría entonces Conjetura débil de Hedetniemi para todas las gráficas. $f(n)$

Gráficas multiplicativas

La conjetura se estudia en el contexto más general de los homomorfismos de grafos , especialmente en vista de su conexión con la categoría de grafos (con grafos como objetos y homomorfismos como flechas). Para cualquier gráfico fijo , consideramos gráficos que admiten un homomorfismo , que se escribe como . Estos gráficos también se denominan -coloreables . Esto generaliza la noción habitual de coloración de grafos, ya que se deduce de la definición que una -coloración es lo mismo que una -coloración (un homomorfismo a un gráfico completo con vértices). $k$ $GRAMO$ $k$ ${\ estilo de visualización G \ a K}$ $k$ $k$ $k_k$ $k$

Un gráfico se llama multiplicativo si para cualquier gráfico y la ejecución sigue o . Al igual que con la coloración clásica, lo contrario siempre es cierto: si (o simétricamente ) se puede colorear, entonces se puede colorear fácilmente usando los mismos valores de color para todas las copias de . La conjetura de Hedetniemi es entonces equivalente a decir que cualquier gráfico completo es multiplicativo. $k$ $GRAMO$ $H$ $G\times H\to K$ ${\ estilo de visualización G \ a K}$ ${\ estilo de visualización H \ a K}$ $GRAMO$ $H$ $k$ $G\veces H$ $k$ $H$

Los casos bien conocidos mencionados anteriormente son equivalentes a las declaraciones que las gráficas y son multiplicativas. El caso está abierto de par en par. Por otro lado, la demostración de El-Zahara y Sauer [3] fue generalizada por Heggquist, Hell, Miller y Neumann-Lara [5] , demostrando que todos los gráficos de ciclo son multiplicativos. Más tarde, Tardif [6] probó un resultado más general, que todas las camarillas cíclicas con son multiplicativas. En términos del número cromático cíclico, esto significa que si , entonces . $K_1$ $K_{2}$ $K_{3}$ $K_{4}$ $K_{\tfrac {n}{k))$ ${\tfrac{n}{k}}<4$ $\chi _{c}$ ${\ estilo de visualización \ chi _ {c} (G \ veces H) <4}$ ${\displaystyle \chi _{c}(G\times H)=\min\{\chi _{c}(G),\chi _{c}(G)\))$

Se pueden construir ejemplos de gráficos no multiplicativos a partir de dos gráficos y , que son incomparables en el orden de los homomorfismos (es decir , ninguno se cumple). En este caso, formando , obtenemos trivialmente , pero ni , ni tienen homomorfismo en , ya que, formando la proyección o , obtenemos una contradicción. $GRAMO$ $H$ ${\ estilo de visualización G \ a H}$ ${\ estilo de visualización H \ a G}$ $K=G\veces H$ $G\times H\to K$ $GRAMO$ $H$ $k$ ${\ estilo de visualización K \ a H}$ ${\ Displaystyle K\ a G}$

Gráfica exponencial

Dado que el producto tensorial de gráficos es un producto teórico de categoría en la categoría de gráficos (con gráficos como objetos y homomorfismos como flechas), la conjetura se puede reformular en términos de la siguiente construcción en gráficos y . Un gráfico exponencial es un gráfico con todas las funciones como vértices (no solo homomorfismos) y dos funciones y son adyacentes si un vértice es adyacente a un vértice para todos los vértices adyacentes del gráfico . En particular, una función tiene un ciclo (es adyacente a sí misma) si y solo si hay un homomorfismo de a . Visto desde un ángulo diferente, podemos decir que hay un borde entre y cuando dos funciones definen un homomorfismo desde ( Gráfico bipartito doble cubierta de un gráfico ) hasta . $k$ $GRAMO$ ${\ estilo de visualización K^{G}}$ ${\ estilo de visualización V (G) \ a V (K)}$ $F$ $gramo$ $f(v)$ ${\ estilo de visualización g (v')}$ $k$ ${\ estilo de visualización v, v'}$ $GRAMO$ $F$ $GRAMO$ $k$ $F$ $gramo$ ${\displaystyle G\veces K_{2))$ $GRAMO$ $k$

Un gráfico exponencial es un exponencial en la categoría de gráficos. Esto significa que los homomorfismos de a un gráfico corresponden a los homomorfismos de a . Además, existe un homomorfismo dado por . Estas propiedades nos permiten concluir que la multiplicatividad de un gráfico es equivalente al enunciado [3] : para cualquier gráfico y , o es -coloreable. $G\veces H$ $k$ $H$ ${\ estilo de visualización K^{G}}$ $\mathrm {eval} :G\veces K^{G}\to K$ $\mathrm {eval} (v,f)=f(v)$ $k$ $GRAMO$ $k$ $GRAMO$ ${\ estilo de visualización K^{G}}$ $k$

En otras palabras, la conjetura de Hedetniemi puede verse como una declaración sobre gráficos exponenciales: para cualquier número entero , el gráfico es -coloreable o contiene un bucle (lo que significa que es -colorable). También se pueden ver los homomorfismos como los casos más difíciles de la conjetura de Hedetniemi: si el producto fuera un contraejemplo, entonces sería un contraejemplo. $k$ ${\displaystyle K_{k}^{G))$ $k$ $GRAMO$ $k$ ${\displaystyle \mathrm {eval} :G\times K_{k}^{G}\to K_{k))$ $G\veces H$ $G\veces K_{k}^{G}$

Generalizaciones

La generalización a grafos dirigidos tiene un simple contraejemplo, como lo muestran Polyak y Rödl [4] . El número cromático de un grafo dirigido es simplemente el número cromático del grafo no dirigido correspondiente, pero el producto tensorial tiene exactamente la mitad del número de aristas (para los arcos en y hacia el producto tensorial tiene solo una arista desde hasta , mientras que el producto de grafo no dirigido gráficos también tiene un borde entre y ). Sin embargo, resulta que la conjetura débil de Hedetniemi es equivalente para grafos dirigidos y no dirigidos [7] . ${\ estilo de visualización g \ a g'}$ $GRAMO$ $h\a h'$ $H$ $G\veces H$ $(g, h)$ ${\ estilo de visualización (g', h')}$ ${\ estilo de visualización (g, h')}$ ${\ estilo de visualización (g', h)}$

El problema no se puede generalizar a gráficos infinitos: Heinl [8] dio un ejemplo de dos gráficos infinitos, cada uno de los cuales requiere un número infinito de colores para colorear, pero su producto se puede colorear con un conjunto finito de colores. Rhinoth [9] demostró que en el universo constructivo para cualquier cardinal infinito existe un par de grafos con número cromático mayor que , tal que el producto sólo puede ser coloreado por un número finito de colores. $\kappa$ $\kappa$

Cuestiones relacionadas

Sabidoussi [10] demostró una igualdad similar para el producto directo de grafos y ha sido redescubierta varias veces desde entonces. Se conoce la fórmula exacta del producto lexicográfico de grafos . Duffus, Sands y Woodrow [11] propusieron dos conjeturas más fuertes con un colorido único.

Notas

↑ Vladímir Potapov. En busca del número cromático . N+1 (30 de mayo de 2019). Consultado el 30 de mayo de 2019. Archivado desde el original el 30 de mayo de 2019. (indefinido)
↑ Yaroslav Shitov. Contraejemplos a la conjetura de Hedetniemi // Annals of Mathematics . - 2019. - Septiembre ( vol. 190 , ns. 2 ). - Pág. 663-667. doi : 10.4007 / annals.2019.190.2.6 . - arXiv : 1905.02167 .
↑ 1 2 3 El-Zahar, Sauer, 1985 .
↑ 1 2 Poljak, Rödl, 1981 .
↑ Häggkvist, Hell, Miller, Neumann-Lara, 1988 .
↑ Tardif, 2005 .
↑ Tardif, Wehlau, 2006 .
↑ Hajnal, 1985 .
↑ Rinot, 2013 .
↑ Sabidussi, 1957 .
↑ Duffus, Arenas, Woodrow, 1985 .

Literatura

fuentes principales

Duffus D., Sands B., Woodrow RE Sobre el número cromático del producto de gráficos // Journal of Graph Theory. - 1985. - T. 9 , núm. 4 . — S. 487–495 . -doi : 10.1002 / jgt.3190090409 .
El-Zahar M., Sauer N. El número cromático del producto de dos gráficos de 4 cromáticos es 4 // Combinatorica. - 1985. - V. 5 , núm. 2 . — S. 121–126 . -doi : 10.1007/ BF02579374 .
Häggkvist R., Hell P., Miller DJ, Neumann-Lara V. Sobre gráficos multiplicativos y la conjetura del producto // Combinatorica . - 1988. - T. 8 , núm. 1 . — S. 63–74 . -doi : 10.1007/ BF02122553 .
Hajnal A. El número cromático del producto de dos gráficos cromáticos ℵ 1 puede ser contable // Combinatorica . - 1985. - V. 5 , núm. 2 . — S. 137–140 . -doi : 10.1007/ BF02579376 .
Hedetniemi S. Homomorfismos de grafos y autómatas. - Universidad de Michigan, 1966. - (Informe Técnico 03105-44-T).
Poljak S., Rödl V. Sobre el número cromático de arco de un dígrafo // Journal of Combinatorial Theory, Serie B . - 1981. - T. 31 , N º 2 . - S. 190-198 . -doi : 10.1016 / S0095-8956(81)80024-X .
Conjetura de Rinot A. Hedetniemi para grafos incontables. - 2013. - . -arXiv : 1307.6841 . _
Sabidussi G. Gráficos con un grupo dado y propiedades teóricas de gráficos dadas // Canadian Journal of Mathematics . - 1957. - T. 9 . — S. 515–525 . -doi : 10.4153 / CJM-1957-060-7 .
Tardif C. Gráficos multiplicativos y endomorfismos semi-retículos en la categoría de gráficos // Journal of Combinatorial Theory, Series B . - 2005. - T. 95 , N º 2 . - S. 338-345 . -doi : 10.1016/ j.jctb.2005.06.002 .
Tardif C., Wehlau D. Números cromáticos de productos de gráficos: las versiones dirigidas y no dirigidas de la función Poljak-Rödl // Journal of Graph Theory . - 2006. - T. 51 , N º 1 . - S. 33-36 . -doi : 10.1002/ jgt.20117 .

Reseñas y otras fuentes

Wilfried Imrich, Sandi Klavzar. Gráficos de Producto: Estructura y Reconocimiento. - Wiley, 2000. - ISBN 0-471-37039-8 .
Sandy Klavzar. Colorear productos gráficos: una encuesta // Matemáticas discretas . - 1996. - T. 155 , núm. 1–3 . — S. 135–145 . - doi : 10.1016/0012-365X(94)00377-U .
La conjetura de Sauer N. Hedetniemi: una encuesta // Matemáticas discretas . - 2001. - T. 229 , núm. 1–3 . — S. 261–292 . - doi : 10.1016/S0012-365X(00)00213-2 .
Claude Tardif. La conjetura de Hedetniemi, 40 años después // Graph Theory Notes of New York. - 2008. - T. 54 . - S. 46-57 .
Xuding Zhu. Una encuesta sobre la conjetura de Hedetniemi // Taiwanese J. Math.. - 1998. - Vol. 2 , no. 1 . — P. 1–24 .
Un gran avance en la teoría de grafos - Numberphile en YouTube