Tutte–Grotendieck invariant

Inom matematik är en Tutte–Grothendieck (TG) invariant en typ av grafinvariant som uppfyller en generaliserad deletions–sammandragningsformel . Varje utvärdering av Tutte-polynomet skulle vara ett exempel på en TG-invariant.

Definition

En graffunktion f är TG-invariant om:

$f(G )={\begin{cases}c^{|V(G)|}&{\text{om null}}\\xf(G/e)&{\text{if }}e{\text{ är en loop}}\\yf(G\backslash e)&{\text{if }}e{\text{ är en coloop eller bridge}}\\af(G/e)+bf(G\backslash e)&{ \text{else}}\end{cases}}$

Ovanför G / e betecknar kantkontraktion medan G \ e betecknar deletion. Siffrorna c , x , y , a , b är parametrar.

Generalisering till matroider

Matroidfunktionen f är TG om :

${ \begin{aligned}&f(M_{1}\oplus M_{2})=f(M_{1})f(M_{2})\\&f(M)=af(M/e)+bf(M \backslash e)\ \ \ {\text{om }}e{\text{ är inte coloop eller bridge}}\end{aligned}}$

Det kan visas att f ges av:

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

där E är kantmängden av M ; r är rangfunktionen; och

$T(M;x,y)=\summa _{A\delmängd E(M)}(x-1)^{r(E)-r(A)}(y-1 )^{|A|-r(A)}$

är generaliseringen av Tutte-polynomet till matroider.

Grothendieck-gruppen

Invarianten är uppkallad efter Alexander Grothendieck på grund av en liknande konstruktion av Grothendieck-gruppen som användes i Riemann-Roch-satsen . För mer information se:

•    Tutte, WT (2008). "En ring i grafteori". Mathematical Proceedings of the Cambridge Philosophical Society . 43 (1): 26–40. doi : 10.1017/S0305004100023173 . ISSN 0305-0041 . MR 0018406 .
•    Brylawski, TH (1972). "Tutte-Grotendieck-ringen". Algebra Universalis . 2 (1): 375–388. doi : 10.1007/BF02945050 . ISSN 0002-5240 . MR 0330004 .