Tutte–Grothendieck invariant

In mathematics, a Tutte–Grothendieck (TG) invariant is a type of graph invariant that satisfies a generalized deletion–contraction formula. Any evaluation of the Tutte polynomial would be an example of a TG invariant.

Definition

A graph function f is TG-invariant if:

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

Above G / e denotes edge contraction whereas G \ e denotes deletion. The numbers c, x, y, a, b are parameters.

Generalization to matroids

The matroid function f is TG if:

$\begin{array}{cc}& f(M_1\oplus M_2)=f(M_1)f(M_2)\\ & f(M)=af(M\mathrm{\setminus }e)+bf(M/e)\text{if }e\text{ is not coloop or bridge}\end{array}$

It can be shown that f is given by:

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

where Template:Tmath is the value Template:Mvar takes on coloops, Template:Tmath is the value Template:Mvar takes on loops, Template:Mvar is the edge set of Template:Mvar; Template:Mvar is the rank function; and

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

is the generalization of the Tutte polynomial to matroids.

Grothendieck group

The invariant is named after Alexander Grothendieck because of a similar construction of the Grothendieck group used in the Riemann–Roch theorem. For more details see:

• Template:Cite journal
• Template:Cite journal