mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, 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 discr ...

that satisfies a generalized

deletion–contraction formula In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form: :f(G) = f(G \setminus e) + f(G / e). Here ''G'' is a graph, ''f'' is a function on graphs, ''e'' is any edge of ''G'', ''G'' \ ' ...

. Any evaluation of the

Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...

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 ide ...

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

Generalization to matroids

The

matroid In combinatorics, a branch of mathematics, 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 axiomatically, the most significant being ...

function ''f'' is TG if: :

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

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

f(M) = a^b^ 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_ (x-1)^ (y-1)^

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 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 homomorphic i ...

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 rel ...

. For more details see: * *

References

{{DEFAULTSORT:Tutte-Grothendieck invariant Graph invariants