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.[1][2]
Definition
A graph function f is TG-invariant if:[2]
[math]\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} }[/math]
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:[1]
- [math]\displaystyle{ \begin{align} &f(M_1\oplus M_2) = f(M_1)f(M_2) \\ &f(M) = af(M/e) + b f(M \backslash e) \ \ \ \text{if } e \text{ is not coloop or bridge} \end{align} }[/math]
It can be shown that f is given by:
- [math]\displaystyle{ f(M) = a^{|E| - r(E)}b^{r(E)} T(M; x/a, y/b) }[/math]
where E is the edge set of M; r is the rank function; and
- [math]\displaystyle{ T(M; x, y) = \sum_{A \subset E(M)} (x-1)^{r(E)-r(A)} (y-1)^{|A|-r(A)} }[/math]
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. (2008). "A ring in graph theory". Mathematical Proceedings of the Cambridge Philosophical Society 43 (1): 26–40. doi:10.1017/S0305004100023173. ISSN 0305-0041.
- Brylawski, T. H. (1972). "The Tutte-Grothendieck ring". Algebra Universalis 2 (1): 375–388. doi:10.1007/BF02945050. ISSN 0002-5240.
References
 |  |
