Polinomio de Tutte

Codificación algebraica de la conectividad de grafos

El polinomio es el polinomio de Tutte del gráfico del toro . La línea roja muestra la intersección con el plano , que es esencialmente equivalente al polinomio cromático. ${\displaystyle x^{4}+x^{3}+x^{2}y}$ ${\displaystyle y=0}$

El polinomio de Tutte , también llamado polinomio dicromato o polinomio de Tutte–Whitney , es un polinomio de grafos . Es un polinomio de dos variables que desempeña un papel importante en la teoría de grafos . Se define para cada grafo no dirigido y contiene información sobre cómo está conectado el grafo. Se denota por . ${\displaystyle G}$ ${\displaystyle T_{G}}$

La importancia de este polinomio se debe a la información que contiene sobre . Aunque originalmente se estudió en la teoría de grafos algebraicos como una generalización de los problemas de conteo relacionados con la coloración de grafos y el flujo sin ceros , contiene varias otras especializaciones famosas de otras ciencias, como el polinomio de Jones de la teoría de nudos y las funciones de partición del modelo de Potts de la física estadística . También es la fuente de varios problemas computacionales centrales en la informática teórica . ${\displaystyle G}$

El polinomio de Tutte tiene varias definiciones equivalentes. Es esencialmente equivalente al polinomio de rango de Whitney, al polinomio dicromático del propio Tutte y al modelo de agrupamiento aleatorio de Fortuin-Kasteleyn bajo transformaciones simples. Es esencialmente una función generadora para el número de conjuntos de aristas de un tamaño dado y componentes conexos, con generalizaciones inmediatas a matroides . También es el invariante de grafo más general que se puede definir mediante una recurrencia de deleción-contracción . Varios libros de texto sobre teoría de grafos y teoría de matroides le dedican capítulos enteros. ^{[1] [2] [3]}

Definiciones

Definición. Para un grafo no dirigido se puede definir el polinomio de Tutte como ${\displaystyle G=(V,E)}$

${\displaystyle T_{G}(x,y)=\sum \nolimits _{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},}$

donde denota el número de componentes conectados del gráfico . En esta definición queda claro que está bien definido y es un polinomio en y . ${\displaystyle k(A)}$ ${\displaystyle (V,A)}$ ${\displaystyle T_{G}}$ ${\displaystyle x}$ ${\displaystyle y}$

La misma definición se puede dar utilizando una notación ligeramente diferente, haciendo que denote el rango del gráfico . Entonces, la función generadora de rangos de Whitney se define como ${\displaystyle r(A)=|V|-k(A)}$ ${\displaystyle (V,A)}$

${\displaystyle R_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{r(E)-r(A)}v^{|A|-r(A)}.}$

Las dos funciones son equivalentes bajo un simple cambio de variables:

${\displaystyle T_{G}(x,y)=R_{G}(x-1,y-1).}$

El polinomio dicromático de Tutte es el resultado de otra transformación simple: ${\displaystyle Q_{G}}$

${\displaystyle T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1).}$

La definición original de Tutte es equivalente, pero menos fácil de expresar. Para conectado, establecemos ${\displaystyle T_{G}}$ ${\displaystyle G}$

${\displaystyle T_{G}(x,y)=\sum \nolimits _{i,j}t_{ij}x^{i}y^{j},}$

donde denota el número de árboles de expansión de actividad interna y actividad externa . ${\displaystyle t_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

Una tercera definición utiliza una recurrencia de contracción-eliminación . La contracción de arista de un grafo es el grafo obtenido al fusionar los vértices y y eliminar la arista . Escribimos para el grafo donde la arista simplemente se elimina. Entonces el polinomio de Tutte se define por la relación de recurrencia ${\displaystyle G/uv}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle uv}$ ${\displaystyle G-uv}$ ${\displaystyle uv}$

${\displaystyle T_{G}=T_{G-e}+T_{G/e},}$

si no es ni un bucle ni un puente , con caso base ${\displaystyle e}$

${\displaystyle T_{G}(x,y)=x^{i}y^{j},}$

Si contiene puentes y bucles y no contiene otros bordes. Especialmente, si no contiene bordes. ${\displaystyle G}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle T_{G}=1}$ ${\displaystyle G}$

El modelo de conglomerado aleatorio de la mecánica estadística de Fortuin y Kasteleyn (1972) proporciona otra definición equivalente. ^[4] La suma de partición

${\displaystyle Z_{G}(q,w)=\sum \nolimits _{F\subseteq E}q^{k(F)}w^{|F|}}$

es equivalente a bajo la transformación ^[5] ${\displaystyle T_{G}}$

${\displaystyle T_{G}(x,y)=(x-1)^{-k(E)}(y-1)^{-|V|}\cdot Z_{G}{\Big (}(x-1)(y-1),\;y-1{\Big )}.}$

Propiedades

El polinomio de Tutte se factoriza en componentes conexos. Si es la unión de grafos disjuntos y entonces ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H'}$

${\displaystyle T_{G}=T_{H}\cdot T_{H'}}$

Si es planar y denota su gráfico dual entonces ${\displaystyle G}$ ${\displaystyle G^{*}}$

${\displaystyle T_{G}(x,y)=T_{G^{*}}(y,x)}$

En particular, el polinomio cromático de un grafo plano es el polinomio de flujo de su dual. Tutte se refiere a estas funciones como funciones V. ^[6 ]

Ejemplos

Los grafos isomorfos tienen el mismo polinomio de Tutte, pero la inversa no es cierta. Por ejemplo, el polinomio de Tutte de cada árbol en las aristas es . ${\displaystyle m}$ ${\displaystyle x^{m}}$

Los polinomios de Tutte se dan a menudo en forma de tabla, enumerando los coeficientes de en la fila y la columna . Por ejemplo, el polinomio de Tutte del gráfico de Petersen , ${\displaystyle t_{ij}}$ ${\displaystyle x^{i}y^{j}}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle {\begin{aligned}36x&+120x^{2}+180x^{3}+170x^{4}+114x^{5}+56x^{6}+21x^{7}+6x^{8}+x^{9}\\&+36y+84y^{2}+75y^{3}+35y^{4}+9y^{5}+y^{6}\\&+168xy+240x^{2}y+170x^{3}y+70x^{4}y+12x^{5}y\\&+171xy^{2}+105x^{2}y^{2}+30x^{3}y^{2}\\&+65xy^{3}+15x^{2}y^{3}\\&+10xy^{4},\end{aligned}}}$

viene dado por la siguiente tabla.

Otro ejemplo, el polinomio de Tutte del gráfico del octaedro viene dado por

${\displaystyle {\begin{aligned}&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2}\\&+25\,{x}^{2}+29\,{y}^{4}+15\,{y}^{5}+5\,{y}^{6}+6\,{y}^{4}x\\&+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^{3}+7\,{x}^{4}+{x}^{5}\end{aligned}}}$

Historia

El interés de WT Tutte en la fórmula de contracción-eliminación comenzó en sus días de estudiante en Trinity College, Cambridge , originalmente motivado por rectángulos perfectos y árboles de expansión . A menudo aplicaba la fórmula en su investigación y "se preguntaba si había otras funciones interesantes de grafos, invariantes bajo isomorfismo , con fórmulas de recursión similares". ^[6] RM Foster ya había observado que el polinomio cromático es una de esas funciones, y Tutte comenzó a descubrir más. Su terminología original para los invariantes de grafos que satisfacen la recursión de contracción-eliminación era función W y función V si era multiplicativa sobre componentes. Tutte escribe: "Jugando con mis funciones W obtuve un polinomio de dos variables del cual se podía obtener el polinomio cromático o el polinomio de flujo estableciendo una de las variables igual a cero y ajustando los signos". ^[6] Tutte llamó a esta función dicromato , ya que la vio como una generalización del polinomio cromático a dos variables, pero generalmente se la conoce como el polinomio de Tutte. En palabras de Tutte, "Esto puede ser injusto para Hassler Whitney , quien conocía y usaba coeficientes análogos sin molestarse en fijarlos a dos variables". (Existe una "notable confusión" ^[7] sobre los términos dicromato y polinomio dicromático , introducidos por Tutte en un artículo diferente, y que difieren solo ligeramente). La generalización del polinomio de Tutte a matroides fue publicada por primera vez por Crapo , aunque ya aparece en la tesis de Tutte. ^[8]

Independientemente del trabajo en teoría de grafos algebraicos , Potts comenzó a estudiar la función de partición de ciertos modelos en mecánica estadística en 1952. El trabajo de Fortuin y Kasteleyn ^[9] sobre el modelo de conglomerado aleatorio , una generalización del modelo de Potts , proporcionó una expresión unificadora que mostraba la relación con el polinomio de Tutte. ^[8]

Especializaciones

En varios puntos y líneas del plano , el polinomio de Tutte evalúa cantidades que han sido estudiadas por derecho propio en diversos campos de las matemáticas y la física. Parte del atractivo del polinomio de Tutte proviene del marco unificador que proporciona para analizar estas cantidades. ${\displaystyle (x,y)}$

Polinomio cromático

El polinomio cromático dibujado en el plano de Tutte

En , el polinomio de Tutte se especializa en el polinomio cromático, ${\displaystyle y=0}$

${\displaystyle \chi _{G}(\lambda )=(-1)^{|V|-k(G)}\lambda ^{k(G)}T_{G}(1-\lambda ,0),}$

donde denota el número de componentes conectados de G . ${\displaystyle k(G)}$

Para un entero λ el valor del polinomio cromático es igual al número de coloraciones de vértices de G utilizando un conjunto de colores λ. Es claro que no depende del conjunto de colores. Lo que es menos claro es que se trata de la evaluación en λ de un polinomio con coeficientes enteros. Para ver esto, observamos: ${\displaystyle \chi _{G}(\lambda )}$ ${\displaystyle \chi _{G}(\lambda )}$

1. Si G tiene n vértices y ninguna arista, entonces . ${\displaystyle \chi _{G}(\lambda )=\lambda ^{n}}$
2. Si G contiene un bucle (un solo borde que conecta un vértice consigo mismo), entonces . ${\displaystyle \chi _{G}(\lambda )=0}$
3. Si e es una arista que no es un bucle, entonces

${\displaystyle \chi _{G}(\lambda )=\chi _{G-e}(\lambda )-\chi _{G/e}(\lambda ).}$

Las tres condiciones anteriores nos permiten calcular , aplicando una secuencia de eliminaciones y contracciones de aristas; pero no dan garantía de que una secuencia diferente de eliminaciones y contracciones conduzca al mismo valor. La garantía proviene del hecho de que cuenta algo, independientemente de la recurrencia. En particular, ${\displaystyle \chi _{G}(\lambda )}$ ${\displaystyle \chi _{G}(\lambda )}$

${\displaystyle T_{G}(2,0)=(-1)^{|V|}\chi _{G}(-1)}$

da el número de orientaciones acíclicas.

Polinomio de Jones

El polinomio de Jones dibujado en el plano de Tutte

A lo largo de la hipérbola , el polinomio de Tutte de un grafo plano se especializa en el polinomio de Jones de un nudo alternado asociado . ${\displaystyle xy=1}$

Puntos individuales

(2,1)

${\displaystyle T_{G}(2,1)}$cuenta el número de bosques , es decir, el número de subconjuntos de aristas acíclicas.

(1,1)

${\displaystyle T_{G}(1,1)}$cuenta la cantidad de bosques de expansión (subconjuntos de aristas sin ciclos y la misma cantidad de componentes conectados que G ). Si el gráfico está conectado, cuenta la cantidad de árboles de expansión. ${\displaystyle T_{G}(1,1)}$

(1,2)

${\displaystyle T_{G}(1,2)}$cuenta el número de subgrafos que abarcan (subconjuntos de aristas con el mismo número de componentes conectados que G ).

(2,0)

${\displaystyle T_{G}(2,0)}$cuenta el número de orientaciones acíclicas de G. ^[10 ]

(0,2)

${\displaystyle T_{G}(0,2)}$cuenta el número de orientaciones fuertemente conectadas de G. ^[11 ]

(2,2)

${\displaystyle T_{G}(2,2)}$es el número donde es el número de aristas del gráfico G. ${\displaystyle 2^{|E|}}$ ${\displaystyle |E|}$

(0,−2)

Si G es un gráfico 4-regular, entonces

${\displaystyle (-1)^{|V|+k(G)}T_{G}(0,-2)}$

cuenta el número de orientaciones eulerianas de G . Aquí está el número de componentes conectados de G . ^[10] ${\displaystyle k(G)}$

(3,3)

Si G es el gráfico de cuadrícula m  ×  n , entonces cuenta la cantidad de formas de cubrir un rectángulo de ancho 4 m y altura 4 n con T-tetrominós . ^{[12] [13]} ${\displaystyle 2T_{G}(3,3)}$

Si G es un grafo planar , entonces es igual a la suma de las orientaciones eulerianas ponderadas en un grafo medial de G , donde el peso de una orientación es 2 al número de vértices de silla de montar de la orientación (es decir, el número de vértices con aristas incidentes ordenadas cíclicamente "dentro, afuera, adentro afuera"). ^[14] ${\displaystyle 2T_{G}(3,3)}$

Modelos de Potts e Ising

Las funciones de partición para el modelo de Ising y los modelos de Potts de 3 y 4 estados dibujados en el plano de Tutte.

Defina la hipérbola en el plano xy −:

${\displaystyle H_{2}:\quad (x-1)(y-1)=2,}$

El polinomio de Tutte se especializa en la función de partición del modelo de Ising estudiado en física estadística . En concreto, a lo largo de la hipérbola ambos están relacionados por la ecuación: ^[15] ${\displaystyle Z(\cdot ),}$ ${\displaystyle H_{2}}$

${\displaystyle Z(G)=2\left(e^{-\alpha }\right)^{|E|-r(E)}\left(4\sinh \alpha \right)^{r(E)}T_{G}\left(\coth \alpha ,e^{2\alpha }\right).}$

En particular,

${\displaystyle (\coth \alpha -1)\left(e^{2\alpha }-1\right)=2}$

para todos los complejos α.

De manera más general, si para cualquier entero positivo q , definimos la hipérbola:

${\displaystyle H_{q}:\quad (x-1)(y-1)=q,}$

Entonces, el polinomio de Tutte se especializa en la función de partición del modelo de Potts de estado q . Varias cantidades físicas analizadas en el marco del modelo de Potts se traducen en partes específicas del . ${\displaystyle H_{q}}$

Polinomio de flujo

El polinomio de flujo dibujado en el plano de Tutte

En , el polinomio de Tutte se especializa en el polinomio de flujo estudiado en combinatoria. Para un grafo conexo y no dirigido G y un entero k , un k -flujo sin ningún punto de origen es una asignación de valores de "flujo" a los bordes de una orientación arbitraria de G de modo que el flujo total que entra y sale de cada vértice es congruente módulo k . El polinomio de flujo denota el número de k -flujos sin ningún punto de origen . Este valor está íntimamente relacionado con el polinomio cromático; de hecho, si G es un grafo plano , el polinomio cromático de G es equivalente al polinomio de flujo de su grafo dual en el sentido de que ${\displaystyle x=0}$ ${\displaystyle 1,2,\dots ,k-1}$ ${\displaystyle C_{G}(k)}$ ${\displaystyle G^{*}}$

Teorema (Tutte).

${\displaystyle C_{G}(k)=k^{-1}\chi _{G^{*}}(k).}$

La conexión con el polinomio de Tutte viene dada por:

${\displaystyle C_{G}(k)=(-1)^{|E|-|V|+k(G)}T_{G}(0,1-k).}$

Polinomio de confiabilidad

El polinomio de confiabilidad dibujado en el plano de Tutte

En , el polinomio de Tutte se especializa en el polinomio de confiabilidad de todos los terminales estudiado en la teoría de redes. Para un grafo conectado G, elimine cada arista con probabilidad p ; esto modela una red sujeta a fallas aleatorias de las aristas. Entonces, el polinomio de confiabilidad es una función , un polinomio en p , que da la probabilidad de que cada par de vértices en G permanezca conectado después de que las aristas fallen. La conexión con el polinomio de Tutte está dada por ${\displaystyle x=1}$ ${\displaystyle R_{G}(p)}$

${\displaystyle R_{G}(p)=(1-p)^{|V|-k(G)}p^{|E|-|V|+k(G)}T_{G}\left(1,{\tfrac {1}{p}}\right).}$

Polinomio dicromático

Tutte también definió una generalización más cercana de dos variables del polinomio cromático, el polinomio dicromático de un gráfico. Este es

${\displaystyle Q_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{k(A)}v^{|A|-|V|+k(A)},}$

donde es el número de componentes conectados del subgrafo generador ( V , A ). Esto está relacionado con el polinomio de nulidad de corank por ${\displaystyle k(A)}$

${\displaystyle Q_{G}(u,v)=u^{k(G)}\,R_{G}(u,v).}$

El polinomio dicromático no se puede generalizar a matroides porque k ( A ) no es una propiedad de los matroides: diferentes gráficos con el mismo matroide pueden tener diferentes números de componentes conectados.

Polinomios relacionados

Polinomio de Martin

El polinomio de Martin de un grafo 4-regular orientado fue definido por Pierre Martin en 1977. ^[17] Demostró que si G es un grafo plano y es su grafo medial dirigido , entonces ${\displaystyle m_{\vec {G}}(x)}$ ${\displaystyle {\vec {G}}}$ ${\displaystyle {\vec {G}}_{m}}$

${\displaystyle T_{G}(x,x)=m_{{\vec {G}}_{m}}(x).}$

Algoritmos

Deleción-contracción

Algoritmo de deleción-contracción aplicado al gráfico de diamante . Los bordes rojos se eliminan en el hijo izquierdo y se contraen en el hijo derecho. El polinomio resultante es la suma de los monomios en las hojas, . Basado en Welsh y Merino (2000). ${\displaystyle x^{3}+2x^{2}+y^{2}+2xy+x+y}$

La recurrencia de deleción-contracción para el polinomio de Tutte,

${\displaystyle T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y),\qquad e{\text{ not a loop nor a bridge.}}}$

produce inmediatamente un algoritmo recursivo para calcularlo para un gráfico dado: siempre que pueda encontrar una arista e que no sea un bucle o un puente , calcule recursivamente el polinomio de Tutte para cuando se elimina esa arista y cuando se contrae esa arista . Luego, sume los dos subresultados para obtener el polinomio de Tutte general para el gráfico.

El caso base es un monomio donde m es el número de puentes y n es el número de bucles. ${\displaystyle x^{m}y^{n}}$

Dentro de un factor polinomial, el tiempo de ejecución t de este algoritmo se puede expresar en términos del número de vértices n y el número de aristas m del gráfico,

${\displaystyle t(n+m)=t(n+m-1)+t(n+m-2),}$

una relación de recurrencia que escala como los números de Fibonacci con solución ^[18]

${\displaystyle t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O\left(1.6180^{n+m}\right).}$

El análisis se puede mejorar hasta un factor polinomial del número de árboles de expansión del gráfico de entrada. ^[19] Para gráficos dispersos con este tiempo de ejecución es . Para gráficos regulares de grado k , el número de árboles de expansión se puede limitar mediante ${\displaystyle \tau (G)}$ ${\displaystyle m=O(n)}$ ${\displaystyle \exp(O(n))}$

${\displaystyle \tau (G)=O\left(\nu _{k}^{n}n^{-1}\log n\right),}$

dónde

${\displaystyle \nu _{k}={\frac {(k-1)^{k-1}}{(k^{2}-2k)^{{\frac {k}{2}}-1}}}.}$

Por lo tanto, el algoritmo de eliminación-contracción se ejecuta dentro de un factor polinómico de este límite. Por ejemplo: ^[20]

${\displaystyle \nu _{5}\approx 4.4066.}$

En la práctica, se utilizan pruebas de isomorfismo de grafos para evitar algunas llamadas recursivas. Este enfoque funciona bien para grafos que son bastante dispersos y presentan muchas simetrías; el rendimiento del algoritmo depende de la heurística utilizada para elegir la arista e . ^{[19] [21] [22]}

Eliminación gaussiana

En algunos casos restringidos, el polinomio de Tutte se puede calcular en tiempo polinomial, en última instancia porque la eliminación gaussiana calcula de manera eficiente las operaciones matriciales determinante y pfaffiana . Estos algoritmos son en sí mismos resultados importantes de la teoría de grafos algebraicos y la mecánica estadística .

${\displaystyle T_{G}(1,1)}$es igual al número de árboles de expansión de un grafo conectado. Esto se puede calcular en tiempo polinomial como el determinante de una submatriz principal máxima de la matriz laplaciana de G , un resultado temprano en la teoría de grafos algebraicos conocido como el teorema de matriz-árbol de Kirchhoff . Del mismo modo, la dimensión del espacio de bicicleta en se puede calcular en tiempo polinomial mediante eliminación gaussiana. ${\displaystyle \tau (G)}$ ${\displaystyle T_{G}(-1,-1)}$

Para los grafos planares, la función de partición del modelo de Ising, es decir, el polinomio de Tutte en la hipérbola , se puede expresar como un pfaffiano y calcular de manera eficiente a través del algoritmo FKT . Esta idea fue desarrollada por Fisher , Kasteleyn y Temperley para calcular el número de cubiertas de dímeros de un modelo de red plana . ${\displaystyle H_{2}}$

Cadena de Markov Monte Carlo

Utilizando un método de Monte Carlo de cadena de Markov , el polinomio de Tutte puede aproximarse arbitrariamente bien a lo largo de la rama positiva de , equivalentemente, la función de partición del modelo ferromagnético de Ising. Esto explota la estrecha conexión entre el modelo de Ising y el problema de contar emparejamientos en un grafo. La idea detrás de este célebre resultado de Jerrum y Sinclair ^[23] es configurar una cadena de Markov cuyos estados sean los emparejamientos del grafo de entrada. Las transiciones se definen eligiendo aristas al azar y modificando el emparejamiento en consecuencia. La cadena de Markov resultante se mezcla rápidamente y conduce a emparejamientos "suficientemente aleatorios", que pueden usarse para recuperar la función de partición utilizando un muestreo aleatorio. El algoritmo resultante es un esquema de aproximación aleatorio de tiempo completamente polinomial (fpras). ${\displaystyle H_{2}}$

Complejidad computacional

El polinomio de Tutte plantea varios problemas computacionales. El más sencillo es

Entrada: Un gráfico ${\displaystyle G}$

Salida: Los coeficientes de ${\displaystyle T_{G}}$

En particular, la salida permite evaluar lo que es equivalente a contar el número de 3-coloraciones de G. Esta última cuestión es #P-completa , incluso cuando se restringe a la familia de grafos planares , por lo que el problema de calcular los coeficientes del polinomio de Tutte para un grafo dado es #P-difícil incluso para grafos planares. ${\displaystyle T_{G}(-2,0)}$

Se ha prestado mucha más atención a la familia de problemas denominada Tutte, definida para cada par complejo : ${\displaystyle (x,y)}$ ${\displaystyle (x,y)}$

Entrada: Un gráfico ${\displaystyle G}$

Salida: El valor de ${\displaystyle T_{G}(x,y)}$

La dureza de estos problemas varía con las coordenadas . ${\displaystyle (x,y)}$

Cálculo exacto

El plano de Tutte. Cada punto en el plano real corresponde a un problema computacional . En cualquier punto rojo, el problema es computable en tiempo polinomial; en cualquier punto azul, el problema es #P-hard en general, pero computable en tiempo polinomial para grafos planares; y en cualquier punto en las regiones blancas, el problema es #P-hard incluso para grafos planares bipartitos. ${\displaystyle (x,y)}$ ${\displaystyle T_{G}(x,y)}$

Si tanto x como y son números enteros no negativos, el problema pertenece a #P . Para pares de números enteros generales, el polinomio de Tutte contiene términos negativos, lo que coloca el problema en la clase de complejidad GapP , la clausura de #P bajo sustracción. Para dar cabida a coordenadas racionales , se puede definir un análogo racional de #P . ^[24] ${\displaystyle T_{G}(x,y)}$ ${\displaystyle (x,y)}$

La complejidad computacional de calcular con exactitud se divide en dos clases para cualquier . El problema es #P-difícil a menos que se encuentre en la hipérbola o sea uno de los puntos ${\displaystyle T_{G}(x,y)}$ ${\displaystyle x,y\in \mathbb {C} }$ ${\displaystyle (x,y)}$ ${\displaystyle H_{1}}$

${\displaystyle \left\{(1,1),(-1,-1),(0,-1),(-1,0),(i,-i),(-i,i),\left(j,j^{2}\right),\left(j^{2},j\right)\right\},\qquad j=e^{\frac {2\pi i}{3}}.}$

en cuyos casos es computable en tiempo polinomial. ^[25] Si el problema se restringe a la clase de grafos planares, los puntos de la hipérbola también se vuelven computables en tiempo polinomial. Todos los demás puntos siguen siendo #P-difíciles, incluso para grafos planares bipartitos. ^[26] En su artículo sobre la dicotomía para grafos planares, Vertigan afirma (en su conclusión) que el mismo resultado se cumple cuando se restringe aún más a grafos con grado de vértice como máximo tres, salvo el punto , que no cuenta en ninguna parte-cero Z ₃ -flujos y es computable en tiempo polinomial. ^[27] ${\displaystyle H_{2}}$ ${\displaystyle T_{G}(0,-2)}$

Estos resultados contienen varios casos especiales notables. Por ejemplo, el problema de calcular la función de partición del modelo de Ising es #P-difícil en general, aunque los algoritmos célebres de Onsager y Fisher lo resuelven para redes planas. Además, el polinomio de Jones es #P-difícil de calcular. Finalmente, calcular el número de cuatro coloraciones de un grafo plana es #P-completo, aunque el problema de decisión es trivial por el teorema de los cuatro colores . En contraste, es fácil ver que contar el número de tres coloraciones para grafos planares es #P-completo porque se sabe que el problema de decisión es NP-completo mediante una reducción parsimoniosa .

Aproximación

La cuestión de qué puntos admiten un buen algoritmo de aproximación ha sido muy estudiada. Aparte de los puntos que se pueden calcular exactamente en tiempo polinomial, el único algoritmo de aproximación conocido es el FPRAS de Jerrum y Sinclair, que funciona para puntos en la hipérbola de “Ising” para y > 0. Si los grafos de entrada se restringen a instancias densas, con grado , hay un FPRAS si x ≥ 1, y ≥ 1. ^[28] ${\displaystyle T_{G}(x,y)}$ ${\displaystyle H_{2}}$ ${\displaystyle \Omega (n)}$

Aunque la situación no se entiende tan bien como para realizar un cálculo exacto, se sabe que es difícil aproximar grandes áreas del plano. ^[24]

Véase también

• Polinomio de Bollobás-Riordan
• Un invariante de Tutte-Grothendieck es cualquier evaluación del polinomio de Tutte

Notas

1. Bollobás 1998, capítulo 10.
2. Biggs 1993, capítulo 13.
3. Godsil y Royle 2004, cap. 15.
4. Sókal 2005.
5. Sokal 2005, ecuación (2.26).
6. Todo 2004.
7. Galés.
8. Farr 2007.
9. Fortuin y Kasteleyn 1972.
10. Gales 1999.
11. Las Vergnas 1980.
12. Korn y Pak 2004.
13. Véase Korn y Pak 2003 para interpretaciones combinatorias de muchos otros puntos.
14. Las Vergnas 1988.
15. Welsh 1993, pág. 62.
16. Welsh y Merino 2000.
17. Martín 1977.
18. Wilf 1986, pág. 46.
19. Sekine, Imai y Tani 1995.
20. Chung y Yau 1999, siguiendo a Björklund et al. 2008.
21. Haggard, Pearce y Royle 2010.
22. Pearce, Haggard y Royle 2010.
23. Jerrum y Sinclair 1993.
24. Goldberg y Jerrum 2008.
25. Jaeger, Vertigan y Welsh 1990.
26. Vertigan y Welsh 1992.
27. Vértigan 2005.
28. Para el caso x ≥ 1 e y = 1, véase Annan 1994. Para el caso x ≥ 1 e y > 1, véase Alon, Frieze y Welsh 1995.

Referencias

• Alon, N.; Frieze, A.; Welsh, DJA (1995), "Esquemas de aproximación aleatorizados en tiempo polinomial para invariantes de Tutte-Gröthendieck: el caso denso", Random Structures and Algorithms , 6 (4): 459–478, doi :10.1002/rsa.3240060409.
• Annan, JD (1994), "Un algoritmo de aproximación aleatorio para contar el número de bosques en gráficos densos", Combinatorics, Probability and Computing , 3 (3): 273–283, doi :10.1017/S0963548300001188.
• Biggs, Norman (1993), Teoría de grafos algebraicos (2.ª ed.), Cambridge University Press , ISBN 0-521-45897-8.
• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), "Cálculo del polinomio de Tutte en tiempo exponencial de vértice", Actas del 47.º Simposio anual IEEE sobre fundamentos de la informática (FOCS 2008) , págs. 677–686, arXiv : 0711.2585 , doi : 10.1109/FOCS.2008.40, ISBN 978-0-7695-3436-7.
• Bollobás, Béla (1998), Teoría de grafos moderna , Springer , ISBN 978-0-387-98491-9.
• Chung, Fan ; Yau, S.-T. (1999), "Recubrimientos, núcleos de calor y árboles de expansión", Electronic Journal of Combinatorics , 6 : R12, doi :10.37236/1444, MR  1667452.
• Crapo, Henry H. (1969), "El polinomio de Tutte", Aequationes Mathematicae , 3 (3): 211–229, doi :10.1007/bf01817442.
• Farr, Graham E. (2007), "Polinomios de Tutte-Whitney: algo de historia y generalizaciones", en Grimmett, Geoffrey ; McDiarmid, Colin (eds.), Combinatoria, complejidad y azar. Un tributo a Dominic Welsh , Oxford Lecture Series in Mathematics and its Applications, vol. 34, Oxford University Press , pp. 28–52, ISBN 978-0-19-857127-8, Zbl1124.05020 ​.
• Fortuin, Cees M.; Kasteleyn, Pieter W. (1972), "Sobre el modelo de grupos aleatorios: I. Introducción y relación con otros modelos", Physica , 57 (4), Elsevier : 536–564, Bibcode :1972Phy....57..536F, doi :10.1016/0031-8914(72)90045-6, ISSN  0031-8914.
• Godsil, Chris ; Royle, Gordon (2004), Teoría de grafos algebraicos , Springer , ISBN 978-0-387-95220-8.
• Goldberg, Leslie Ann ; Jerrum, Mark (2008), "Inaproximabilidad del polinomio de Tutte", Información y computación , 206 (7): 908–929, arXiv : cs/0605140 , doi :10.1016/j.ic.2008.04.003.
• Haggard, Gary; Pearce, David J.; Royle, Gordon (2010), "Cálculo de polinomios de Tutte", ACM Transactions on Mathematical Software , 37 (3): Art. 24, 17, doi :10.1145/1824801.1824802, MR  2738228.
• Jaeger, F.; Vertigan, DL; Welsh, DJA (1990), "Sobre la complejidad computacional de los polinomios de Jones y Tutte", Mathematical Proceedings of the Cambridge Philosophical Society , 108 (1): 35–53, Bibcode :1990MPCPS.108...35J, doi :10.1017/S0305004100068936.
• Jerrum, Mark ; Sinclair, Alistair (1993), "Algoritmos de aproximación en tiempo polinomial para el modelo de Ising" (PDF) , SIAM Journal on Computing , 22 (5): 1087–1116, doi :10.1137/0222066.
• Korn, Michael; Pak, Igor (2003), Evaluaciones combinatorias del polinomio de Tutte (PDF) (preimpresión).
• Korn, Michael; Pak, Igor (2004), "Teselación de rectángulos con tetrominós T", Theoretical Computer Science , 319 (1–3): 3–27, doi : 10.1016/j.tcs.2004.02.023.
• Las Vergnas, Michel (1980), "Convexidad en matroides orientadas", Journal of Combinatorial Theory , Serie B, 29 (2): 231–243, doi : 10.1016/0095-8956(80)90082-9 , ISSN  0095-8956, MR  0586435.
• Las Vergnas, Michel (1988), "Sobre la evaluación en (3, 3) del polinomio de Tutte de un grafo", Journal of Combinatorial Theory , Serie B, 45 (3): 367–372, doi : 10.1016/0095-8956(88)90079-2 , ISSN  0095-8956.
• Martin, Pierre (1977), Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck [ Enumeraciones eulerianas en multigrafías e invariantes de Tutte-Grothendieck ] (tesis doctoral) (en francés), Universidad Joseph Fourier.
• Pearce, David J.; Haggard, Gary; Royle, Gordon (2010), "Heurísticas de selección de aristas para calcular polinomios de Tutte" (PDF) , Chicago Journal of Theoretical Computer Science : Artículo 6, 14, MR  2659710.
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), "Cálculo del polinomio de Tutte de un gráfico de tamaño moderado", Algorithms and computations (Cairns, 1995) , Lecture Notes in Computer Science , vol. 1004, Springer , págs. 224–233, doi :10.1007/BFb0015427, ISBN 978-3-540-60573-7, Sr.  1400247.
• Sokal, Alan D. (2005), "El polinomio de Tutte multivariado (alias modelo de Potts) para gráficos y matroides", en Webb, Bridget S. (ed.), Surveys in Combinatorics , London Mathematical Society Lecture Note Series, vol. 327, Cambridge University Press , pp. 173–226, arXiv : math/0503607 , doi :10.1017/CBO9780511734885.009, ISBN 978-0-521-61523-5.
• Tutte, WT (2001), Teoría de grafos , Cambridge University Press , ISBN 978-0521794893.
• Tutte, WT (2004), "Grafos polinomiales", Advances in Applied Mathematics , 32 (1–2): 5–9, doi : 10.1016/S0196-8858(03)00041-1.
• Vertigan, DL; Welsh, DJA (1992), "La complejidad computacional del plano de Tutte: el caso bipartito", Combinatorics, Probability and Computing , 1 (2): 181–187, doi :10.1017/S0963548300000195.
• Vertigan, Dirk (2005), "La complejidad computacional de los invariantes de Tutte para gráficos planares", SIAM Journal on Computing , 35 (3): 690–712, doi :10.1137/S0097539704446797.
• Welsh, DJA (1976), Teoría de matroides , Academic Press , ISBN 012744050X.
• Welsh, Dominic (1993), Complejidad: nudos, coloraciones y conteo , London Mathematical Society Lecture Note Series, Cambridge University Press , ISBN 978-0521457408.
• Welsh, Dominic (1999), "El polinomio de Tutte", Random Structures & Algorithms , 15 (3–4), Wiley : 210–228, doi :10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R, ISSN  1042-9832.
• Welsh, DJA ; Merino, C. (2000), "El modelo de Potts y el polinomio de Tutte", Journal of Mathematical Physics , 41 (3): 1127–1152, Bibcode :2000JMP....41.1127W, doi :10.1063/1.533181.
• Wilf, Herbert S. (1986), Algoritmos y complejidad (PDF) , Prentice Hall , ISBN 0-13-021973-8, Sr.  0897317.

Enlaces externos

• "Polinomio de Tutte", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Polinomio de Tutte". MundoMatemático .
• Polinomio cromático de PlanetMath
• Steven R. Pagano: Matroides y grafos con signo
• Sandra Kingan: Teoría de Matroides. Muchos enlaces.
• Código para calcular polinomios de Tutte, cromáticos y de flujo de Gary Haggard, David J. Pearce y Gordon Royle: [1]