Invariante de Tutte-Grothendieck

En matemáticas , un invariante de Tutte-Grothendieck (TG) es un tipo de invariante gráfico que satisface una fórmula generalizada de eliminación-contracción . Cualquier evaluación del polinomio de Tutte sería un ejemplo de invariante TG. ^{[1] [2]}

Definición

Una función gráfica f es invariante TG si: ^[2]

${\displaystyle f(G)={\begin{cases}c^{|V(G)|}&{\text{if G has no edges}}\\xf(G/e)&{\text{if }}e{\text{ is a bridge}}\\yf(G\backslash e)&{\text{if }}e{\text{ is a loop}}\\af(G/e)+bf(G\backslash e)&{\text{else}}\end{cases}}}$

Por encima de G / e denota contracción de borde mientras que G \ e denota eliminación. Los números c , x , y , a , b son parámetros.

Generalización a matroides

La función matroide f es TG si: ^[1]

${\displaystyle {\begin{aligned}&f(M_{1}\oplus M_{2})=f(M_{1})f(M_{2})\\&f(M)=af(M/e)+bf(M\backslash e)\ \ \ {\text{if }}e{\text{ is not coloop or bridge}}\end{aligned}}}$

Se puede demostrar que f está dada por:

${\displaystyle f(M)=a^{|E|-r(E)}b^{r(E)}T(M;x/a,y/b)}$

donde E es el conjunto de aristas de M ; r es la función de rango; y

${\displaystyle T(M;x,y)=\sum _{A\subset E(M)}(x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)}}$

es la generalización del polinomio de Tutte a matroides.

Grupo Grothendieck

El invariante lleva el nombre de Alexander Grothendieck debido a una construcción similar del grupo de Grothendieck utilizado en el teorema de Riemann-Roch . Para más detalles ver:

• Tutte, WT (2008). "Un anillo en teoría de grafos". Actas matemáticas de la Sociedad Filosófica de Cambridge . 43 (1): 26–40. doi :10.1017/S0305004100023173. ISSN  0305-0041. SEÑOR  0018406.
• Brylawski, TH (1972). "El anillo Tutte-Grothendieck". Álgebra universal . 2 (1): 375–388. doi :10.1007/BF02945050. ISSN  0002-5240. SEÑOR  0330004.

Referencias

1. galés. Complejidad, Nudos, Coloraciones y Conteo .
2. Goodall, Andrew (2008). "Gráfico de polinomios e invariantes de Tutte-Grothendieck: una aplicación del análisis de Fourier finito elemental". arXiv : 0806.4848 [matemáticas.CO].