En matemáticas , un invariante de Tutte-Grothendieck (TG) es un tipo de invariante de gráfico que satisface una fórmula generalizada de deleción-contracción . Cualquier evaluación del polinomio de Tutte sería un ejemplo de un invariante TG. [1] [2]
Definición
Una función gráfica f es invariante TG si: [2]
Por encima de G / e denota contracción del borde, mientras que G \ e denota deleció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]
Se puede demostrar que f viene dada por:
donde E es el conjunto de bordes de M ; r es la función de rango; y
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 utilizada en el teorema de Riemann-Roch . Para obtener más detalles, consulte:
- Tutte, WT (2008). "Un anillo en la teoría de grafos". Procedimientos matemáticos 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 de Tutte-Grothendieck". Álgebra Universalis . 2 (1): 375–388. doi : 10.1007 / BF02945050 . ISSN 0002-5240 . Señor 0330004 .