mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a Tutte–Grothendieck (TG) invariant is a type of

graph invariant Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discre ...

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
c^ & \text \\
xf(G/e) & \text e \text \\
yf(G \backslash e) & \text e \text \\
af(G/e) + bf(G \backslash e) & \text
\end

Above ''G'' / ''e'' denotes

edge contraction In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...

whereas ''G'' \ ''e'' denotes deletion. The numbers ''c'', ''x'', ''y'', ''a'', ''b'' are parameters.

Generalization to matroids

The

matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...

function ''f'' is TG if: :

\begin
&f(M_1\oplus M_2) = f(M_1)f(M_2) \\
&f(M) = a f(M \backslash e) + b f(M / e) \ \ \ \text e \text
\end

It can be shown that ''f'' is given by: :

f(M) = a^b^ T(M; x_0/b, y_0/a)

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

T(M; x, y) = \sum_ (x-1)^ (y-1)^

is the generalization of the Tutte polynomial to matroids.

Grothendieck group

The invariant is named after

Alexander Grothendieck Alexander Grothendieck, later Alexandre Grothendieck in French (; ; ; 28 March 1928 – 13 November 2014), was a German-born French mathematician who became the leading figure in the creation of modern algebraic geometry. His research ext ...

because of a similar construction of the

Grothendieck group In mathematics, the Grothendieck group, or group of differences, of a commutative monoid is a certain abelian group. This abelian group is constructed from in the most universal way, in the sense that any abelian group containing a group homomorp ...

used in the

Riemann–Roch theorem The Riemann–Roch theorem is an important theorem in mathematics, specifically in complex analysis and algebraic geometry, for the computation of the dimension of the space of meromorphic functions with prescribed zeros and allowed poles. It re ...

. For more details see: * *

References

{{DEFAULTSORT:Tutte-Grothendieck invariant Graph invariants