¿Cuál es el polinomio de Tutte de codificación?

Question

Casi exactamente lo que dice en la lata. Vamos a G un grafo conexo; entonces el polinomio de Tutte T_G(x,y) lleva un montón de información acerca de G. sin Embargo, es evidente que no se codifican todo sobre el gráfico, ya que hay ejemplos de no-isomorfo gráficos con el mismo polinomio de Tutte.

Mi pregunta es, ¿qué información hace exactamente el polinomio de Tutte encapsular? Soy consciente de un par de respuestas a esta pregunta, pero no me parece que ninguno de ellos especialmente satisfactorio. Por ejemplo, T_G(x,y) puede ser caracterizado como "el universal Tutte-Grothendieck invariante," pero la definición de Tutte-Grothendieck invariantes es tan intuitivo como la definición del polinomio de Tutte (porque es esencialmente la misma definición!) También se puede definir los coeficientes como el conteo de ciertos árboles de expansión de G, pero esto no lo hace evidente el hecho de que el polinomio de Tutte se especializa para el polinomio cromático, o la noción de que se lleva la mayoría de la información se puede obtener a través de los métodos del álgebra lineal.

Entonces, ¿hay una buena manera de pensar acerca de lo que los datos acerca de G el polinomio de Tutte codifica?

ETA: Bien, este es un muy áspera conjetura. Supongamos que hay algunos "computacionalmente simple" (es decir, las pruebas de la pertenencia está en NP) clase de gráficas que hay dos grafos G, H con el mismo polinomio de Tutte, y G de la clase y H es no. A continuación, hay árboles de expansión S, T, G, H, respectivamente, tales que S está en la clase y T no lo es.

Esto significaría que, en un sentido que yo no puedo hacer totalmente rigurosa, que la información acerca de un grafo G no se codifica en el polinomio de Tutte es sólo información acerca de la estructura de los árboles de expansión de G. (Actualización: Como Kevin Costello señala en un comentario, esta idea parece estar severamente limitada por la existencia de ciertos pares de co-Tutte gráficos. En particular, sería necesario contar árboles de expansión con la multiplicidad de tener ni siquiera la oportunidad de ser cierto.)

Como se ha dicho, la anterior conjetura es falsa por razones triviales. Pero hay una manera de hacerlo es la verdad, tal vez por que requieren de la propiedad a ser, en cierto sentido, al natural? Hay un concepto amplio de "propiedades de gráfico", para lo que es cierto? Podemos, al menos, el estado de una conjetura a lo largo de estas líneas, lo cual parece ser cierto?

Answer 1

Nadie hasta ahora se ha mencionado matroids. El polinomio de Tutte codifica parte de la información del ciclo de matroid de la gráfica. Dos gráficos con el mismo ciclo de matroid (y el número de vértices) tienen el mismo Tutte polinomios. Así que si un gráfico de la propiedad no está determinado por el ciclo de matroid (y el número de vértices) entonces no puede ser obtenido a partir del polinomio de Tutte.

Answer 2

Este es probablemente el más avanzado respuesta que usted está buscando, pero una respuesta es la cohomology de una variedad llamada "hypertoric variedad", construido a partir de la gráfica en un poco de manera sutil. Usted puede leer más acerca de esto en los papeles por Hausel y Sturmfels y Proudfoot y a mí mismo. Usted debe ser advertido de que todos los papeles hablar de hyperplane arreglos; se debe girar a un gráfico en un hyperplane transcripción mediante la toma de una variable para cada vértice, y un hyperplane para cada arista dada por la equiparación de las variables en los extremos opuestos.

Un problema con este enfoque es que se puede ver sólo una variable a la vez; T(x,1) es el polinomio de Poincaré de una sola variedad (creo que la gráfica de hypertoric variedad) y T(1,y) es el polinomio de Poincaré para otro (el cographical hypertoric variedad).

Answer 3

La topológico Tutte polinomios de Bollobas y Riordan: propiedades y relaciones con otros gráfica de polinomios

Answer 4

El polinomio de Tutte de un gráfico de $G$ es la convolución de la modular el flujo de polinomio y el sistema modular de la tensión polinomio de $G$, c.f. [1,2,3]. Esto conduce a una combinatoria de interpretación de los valores del polinomio de Tutte en cada punto entero en el plano [4, Teorema de 3.11.7].

1. W. Kook, V. Reiner, y D. Stanton, Una convolución de la fórmula para el polinomio de Tutte, J. Combinat. La Teoría De La Ser. B 76 (1999), no. 2, 297-300.
2. V. Reiner, Una interpretación para el polinomio de Tutte, Europeo, J. Combinat. 20 (1999), no. 2, 149-161.
3. F. Breuer y R. Sanyal, Ehrhart teoría Modular de ujo de la reciprocidad, y el polinomio de Tutte, Mathematische Zeitschrift, a aparecer. arXiv:0907.0845
4. F. Breuer, Bocadillos de Jamón, las Escaleras y el Recuento de Polinomios, tesis de Doctorado, Freie Universität de Berlín de 2009. Disponibles aquí y aquí.

Descargo de responsabilidad: las últimas dos de las referencias citadas son mías.

Answer 5

Yo voy a aprovechar la oportunidad para anunciar uno de mis resultados: Un número de personas me han dicho: "siempre he pensado que había algo $K$-teórico sobre el polinomio de Tutte". Alex Fink y yo hemos trabajado en los detalles.

Deje $x$ ser un punto en el Grassmannian $G(d,n)$. Deje $T$ ser el toro de la diagonal de las matrices en $GL_n$, y deje $Z$ es el cierre de $Tx$. Deje $\mathcal{O}_Z$ ser la estructura de la gavilla de $Z$ y deje $\mathcal{O}(1)$ ser el Fruncido de la línea de paquete en la $G(d,n)$.

Deje $\mathbb{P}$ ser el espacio proyectivo líneas en $\mathbb{C}^n$, vamos a $\mathbb{P}^{\vee}$ ser el espacio proyectivo de hyperplanes en $\mathbb{C}^n$, y deje $F \subset \mathbb{P} \times G(d,n) \times \mathbb{P}^{\vee}$ ser el espacio de parcial de los indicadores de la dimensión $(1,d,n-1)$. Empujando y tirando de $F$ da un mapa de $\phi: K_0(G(d,n)) \to K_0(\mathbb{P} \times \mathbb{P}^{\vee}) \cong \mathbb{Z}[t,u]/\langle t^n, u^n \rangle$.

A continuación, $\phi([\mathcal{O}_Z \otimes \mathcal{O}(1)])$ es el polinomio de Tutte de la matroid $M$$x$.

Ver a un bebé en caso de esto, vamos a $\int$ denotar el pushforward a $K_0(\mathrm{pt}) \cong \mathbb{Z}$. La proyección de la fórmula nos da el $\int \circ \phi = \int$. Ahora, $\int \mathcal{O}_Z(1)$ es la dimensión global de las secciones de la Desplumadora de la línea de paquete restringido a $Z$. La Desplumadora coordiante $p_I$ es cero en $Z$ si y sólo si $I \not \in M$, y no existen otras relaciones, por lo $\int \mathcal{O}_Z(1)$ es el número de bases de $M$. Por otro lado, $\int : K_0(\mathbb{P} \times \mathbb{P}^{\vee}) \to \mathbb{Z}$ envía $t$$u$$1$. Por lo que este resultado incluye el hecho básico de que el polinomio de Tutte, evaluado en $(1,1)$, es el número de bases de la matroid.

Alex y yo sugiero que $\phi([\mathcal{O}_Z \otimes \mathcal{O}(k)])$ podría ser una interesante matroid invariante para otros valores de $k$.