Tutte–Grothendieck invariant explained

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.^[1]

Definition

A graph function f is TG-invariant if:^[2]

f(G) = \begin{cases} c ^{|V(G)|} & ifGhasnoedges \\ xf(G/e) & if e isabridge \\ yf(G \backslash e) & if e isaloop \\ af(G/e) + bf(G \backslash e) & else \end{cases}

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{align} &f(M _{1 ⊕} M _{2)} = f(M _{1)f(M} _{2)} \\ &f(M) = af(M/e) + b f(M \backslash e) if e isnotcolooporbridge \end{align}

It can be shown that f is given by:

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

where E is the edge set of M; r is the rank function; and

T(M; x, y) = \sum _{A} (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:

• Tutte. W. T.. W. T. Tutte. A ring in graph theory. Mathematical Proceedings of the Cambridge Philosophical Society. 43. 1. 2008. 26–40. 0305-0041. 10.1017/S0305004100023173. 0018406.
• Brylawski. T. H.. Thomas H. Brylawski. The Tutte-Grothendieck ring. Algebra Universalis. 2. 1. 1972. 375–388. 0002-5240. 10.1007/BF02945050. 0330004.

Notes and References

1. Book: Welsh. Complexity, Knots, Colourings and Counting.
2. Graph polynomials and Tutte-Grothendieck invariants: an application of elementary finite Fourier analysis. Goodall. Andrew. 2008. math.CO. 0806.4848.