Deleted:Tutte–Grothendieck invariant

From WikiAlpha
Revision as of 17:17, 11 July 2019 by SaveArticleBot (Talk | contribs) (Via SaveArticle)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
The below content is licensed according to Creative Commons Attribution-ShareAlike License contrary to the public domain logo at the foot of the page. It originally appeared on The original article might still be accessible here. You may be able to find a list of the article's previous contributors on the talk page.

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]


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

<math>f(G) = \begin{cases} c^{|V(G)|} & \text{if null} \\ xf(G/e) & \text{if } e \text{ is a loop} \\ yf(G \backslash e) & \text{if } e \text{ is a coloop or bridge} \\ 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]


&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>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>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: