Difference between revisions of "Deleted:Tutte–Grothendieck invariant"
(Via SaveArticle) 
(No difference)

Latest revision as of 17:17, 11 July 2019
The below content is licensed according to Creative Commons AttributionShareAlike License contrary to the public domain logo at the foot of the page. It originally appeared on http://en.wikipedia.org. 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]}
Definition
A graph function f is TGinvariant 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]}
 <math>\begin{align}
&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)} (x1)^{r(E)r(A)} (y1)^{Ar(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:
 W. T. Tutte, A ring in graph theory
 https://www.pdfarchive.com/2017/08/22/brylawski1972thetuttegrothendieckring/
References
 ↑ ^{1.0} ^{1.1} Welsh. Complexity, Knots, Colourings and Counting.
 ↑ ^{2.0} ^{2.1} Goodall, Andrew. "Graph polynomials and TutteGrothendieck invariants: an application of elementary finite Fourier analysis". https://arxiv.org/pdf/0806.4848.pdf.