¿Cuántos polinomios cromáticos de mapas planos existen?

Question

Sea P(n) el conjunto de polinomios que pueden darse como polinomio cromático de un mapa plano con n países. ¿Qué se sabe o se conjetura sobre el crecimiento de |P(n)|?

P.D.: Gracias Gerry y Noam, puedo acotar la pregunta de esta manera: ¿existe un exponencial baja ¿con qué límite se encuentra |P(n)|?

Answer 1

El siguiente post ha sido redactado como sección 6 de este documento . De hecho, se puede demostrar que el número de valores de los polinomios cromáticos a 4 crece exponencialmente.

El número de polinomios cromáticos crece exponencialmente. Esta respuesta es conjunta con Slava Krushkal .

El Álgebra cromática $\mathcal{C}_n$ es un álgebra sobre $\mathbb{C}[Q]$ (para un parámetro $Q$ ) formado a partir de combinaciones lineales de (clases de isotopía de) grafos planos en un rectángulo $R$ con $n$ puntos univalentes en la parte superior e inferior:

Dichos diagramas pueden componerse colocando uno sobre otro, fusionando los $n$ vértices univalentes juntos para obtener aristas. A continuación, cotice esta álgebra por algunas relaciones: la relación de supresión-contracción

y una relación para eliminar los bucles y matar los diagramas con puentes

Dichos diagramas representan gráficas planas que concuerdan fuera de las imágenes mostradas. Estas relaciones son satisfechas por el polinomio en $Q$ que cuenta el número de en ninguna parte los flujos cero (sobre un grupo abeliano con $Q$ elemnts) en un gráfico. También hay un trazado, en el que se cierra el gráfico de arriba a abajo y se evalúa el polinomio de flujo:

Para los genéricos $Q\in \mathbb{C}$ , se trata de un álgebra semisimple. De forma más general, se puede describir un álgebra plana que contiene todos los $\mathcal{C}_n$ s.

Para entender por qué el número de polinomios cromáticos crece exponencialmente, se trata de tomar algunos gráficos en $\mathcal{C}_n$ que generan un semigrupo en el álgebra. Como el álgebra es lineal, la alternativa de Tits para semigrupos implica que o bien este semigrupo debe contener un subsemigrupo libre o bien es virtualmente nilpotente. Esto último es poco probable, si se toman los generadores de $\mathcal{C}_n$ ya que es semisimple. Por lo tanto, el crecimiento de los elementos en el álgebra cuando uno multiplica estos generadores es exponencial. Entonces se pueden extraer las entradas de la matriz multiplicando con una base de $\mathcal{C}_n$ y tomando las trazas (para obtener productos internos con la base, y por lo tanto esencialmente las entradas de la matriz). El número de estas trazas crece exponencialmente, de ahí el número de polinomios de flujo de los grafos (de ahí los polinomios cromáticos de los grafos planos duales) en función del número de vértices.

Para concretar, tenemos un ejemplo explícito para demostrar este enfoque. Queremos la subálgebra de menor dimensión posible, por lo que es conveniente establecer $Q=\phi+1 = \frac{3+\sqrt{5}}{2}$ desde $\mathcal{C}_n$ tiene entonces un radical de traza no trivial generado por la relación de Tutte:

Para los gráficos trivalentes (cúbicos), es conveniente utilizar esta forma de la relación:

Añadiendo esta relación (que no afecta al valor del polinomio de flujo para grafos planos en $Q=\phi+1$ ) disminuye la dimensión del álgebra y, por tanto, facilita el cálculo.

Haremos una variación de la estrategia anterior. Consideremos los elementos $A, B$ de $\mathcal{C}_3$ en esta foto:

Podemos multiplicar (apilando) $A$ y $B$ con los gráficos $e_1, e_2$ que no son elementos de $\mathcal{C}_3^{\phi+1}$ , sino de un espacio vectorial relacionado $\mathcal{C}_{3,1}$ que es un módulo sobre $\mathcal{C}_3$ (realmente en el álgebra plana), para $Q=\phi+1$ (obtenido de la de la misma manera, tomando los grafos modulando las relaciones de supresión-contracción). Entonces podemos calcular $Ae_1= -\phi e_1, Ae_2=-\phi^2 e_2-\phi e_1,$ $Be_1=-\phi^2 e_2-\phi e_1, Be_2=-\phi e_2$ por lo que la acción de $A,B$ preserva el subespacio abarcado por $e_1,e_2$ . Éstas están representadas por las matrices:

$A=\left(\begin{array}{cc}-\phi & -\phi \\0 & -\phi^2\end{array}\right),$ $B=\left(\begin{array}{cc}-\phi^2 & 0 \\-\phi & -\phi\end{array}\right),$

Ahora, multiplica $A, B$ juntos $n$ veces, consiguiendo $2^n$ elementos de $\mathcal{C}_3$ . A continuación, añada $e_1, e_2$ en la parte inferior, y sus reflejos en la parte superior, para obtener un elemento de $\mathcal{C}_1$ . Entonces toma la traza, así que conecta por un arco que va de arriba a abajo y evaluar el polinomio de flujo. Los gráficos $A,B$ entonces tienen un subsemigrupo en $GL(2,\mathbb{R})$ que es libre (ya que tienen vectores propios distintos), por lo que los varios productos dan elementos distintos de $\mathcal{C}_3$ , y por lo tanto obtenemos al menos $2^{n/4}$ coeficientes distintos cuando emparejamos con el $e_i$ s y tomar el rastro.

Aquí está $ABAAB$ tapado de una manera:

Answer 2

Sospecho que la respuesta a esta pregunta debería ser sí, debería haber un límite inferior exponencial en $|P(n)|$ . De hecho, creo que debería haber un límite inferior exponencial en el número de 3 coloraciones de gráficos planos con $n$ vértices. No sé cómo probar esto, pero algunas pruebas son que La 3-colorabilidad de los grafos planares es NP-completa. Esto se demuestra reduciendo la tricolorabilidad de los grafos generales a la de los grafos planos. A su vez, se demuestra que la 3-SAT se reduce a la 3-colorabilidad, por construyendo para cada fórmula un grafo que es 3-colable si la fórmula es satisfacible. Ahora, el número de 3-satisfacciones de fórmulas debería crecer exponencialmente, creo. Y cuantas más satisfacciones tenga una fórmula, más coloraciones tendrán los gráficos correspondientes. Así que el número de 3-coloraciones de los grafos planos debería crecer exponencialmente, y por tanto el número de polinomios cromáticos. De todos modos, esto predice, al menos heurísticamente, que debería haber un crecimiento exponencial del número de polinomios.