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]

$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}}$

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]

{\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)

where E is the edge set of M; r is the rank function; and

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:

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. MR 0018406.
Brylawski, T. H. (1972). "The Tutte-Grothendieck ring". Algebra Universalis. 2 (1): 375–388. doi:10.1007/BF02945050. ISSN 0002-5240. MR 0330004.

gollark: (reference implementation here: https://github.com/osmarks/random-stuff/blob/master/length_terminated_strings.c)

gollark: Why would you do that instead of length-terminated values?

gollark: No spec, can only do arrays of arrays and no other data structures, annoying and textual still.

gollark: You WILL be caused to emit tau neutrinos with an energy of 45GeV or greater.

gollark: Do NOT CSV under any circumstances.

References

Welsh. Complexity, Knots, Colourings and Counting.
Goodall, Andrew (2008). "Graph polynomials and Tutte-Grothendieck invariants: an application of elementary finite Fourier analysis". arXiv:0806.4848 [math.CO].

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-1] Welsh. Complexity, Knots, Colourings and Counting.

[:1-2] Goodall, Andrew (2008). "Graph polynomials and Tutte-Grothendieck invariants: an application of elementary finite Fourier analysis". arXiv:0806.4848 [math.CO].