Misplaced Pages

Tutte–Grothendieck invariant

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Tutte–Grothendieck invariant" – news · newspapers · books · scholar · JSTOR (August 2019) (Learn how and when to remove this message)

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 ) = { c | V ( G ) | if G has no edges x f ( G / e ) if  e  is a bridge y f ( G ∖ e ) if  e  is a loop a f ( G / e ) + b f ( G ∖ e ) else {\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}}}

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:

f ( M 1 ⊕ M 2 ) = f ( M 1 ) f ( M 2 ) f ( M ) = a f ( M / e ) + b f ( M ∖ e )       if  e  is not coloop or bridge {\displaystyle {\begin{aligned}&f(M_{1}\oplus M_{2})=f(M_{1})f(M_{2})\\&f(M)=af(M/e)+bf(M\backslash e)\ \ \ {\text{if }}e{\text{ is not coloop or bridge}}\end{aligned}}}

It can be shown that f is given by:

f ( M ) = a | E | − r ( E ) b r ( E ) T ( M ; x / a , y / b ) {\displaystyle f(M)=a^{|E|-r(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 ) = ∑ A ⊂ E ( M ) ( x − 1 ) r ( E ) − r ( A ) ( y − 1 ) | A | − r ( A ) {\displaystyle 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:

References

  1. ^ Welsh. Complexity, Knots, Colourings and Counting.
  2. ^ Goodall, Andrew (2008). "Graph polynomials and Tutte-Grothendieck invariants: an application of elementary finite Fourier analysis". arXiv:0806.4848 .
Category: