by S. Huggett and I. Moffatt. Math. Proc. Camb. Phil. Soc., 2018. doi.
The Tutte polynomial \(T(G;x,y)\) of a graph \(G\) is a fundamental invariant in graph theory. It generalizes many other graph polynomials and encodes a lot of information (number of spanning forests, number of proper colourings, number of acyclic orientations etc). It has the important universal property that essentially any multiplicative graph invariant with a deletion/contraction reduction must be an evaluation of it:
Let \(\mathcal{G}\) be a minor closed class of graphs. Then there is a unique map \(U:\mathcal{G}\to\mathbb{Z}[x,y,a,b,\gamma]\) such that \[U(G)=\begin{cases}xU(G/e)&\text{if $e$ is a bridge,}\\yU(G\backslash e)&\text{if $e$ is a loop,}\\aU(G\backslash e)+bU(G/e)&\text{if $e$ is an ordinary edge,}\\\gamma^{n}&\text{if $E(G)=\varnothing$ and $v(G)=n$.}\end{cases}\]Moreover \[U(G)=\gamma^{k(G)}a^{n(G)}b^{r(G)}T(G;\frac xb,\frac ya).\]
There exist several generalizations of the Tutte polynomial to graphs embedded in surfaces: the Las Vergnas polynomial, the Bollobas-Riordan polynomial, the Krushkal polynomial and many others. In this article, Huggett and Moffatt propose a framework in which all these invariants are special evaluations of a master polynomial.
They first recall that the different existing polynomials of embedded graphs apply actually to different classes of objects depending on whether one imposes cellular embedding or not, in surfaces or pseudo-surfaces. Thus the most general framework consists in graphs not necessarily cellularly embedded in pseudo-surfaces. They prove that (stabilization classes of) such graphs are in bijection with vertex- and boundary-coloured ribbon graphs.
Then, having in mind the universality of the Tutte polynomial, they look for the most general polynomial which obeys full1 contraction/deletion relations on coloured ribbon graphs. For this they develop a canonical approach to edge types in order to generalize the notions of bridge, trivial loop, ordinary edge etc. This gives rise to the Tutte polynomial of coloured ribbon graphs.
Their approach is very interesting for several reasons:
- They recover well-known polynomials as specializations of their master polynomial \(T_{ps}\).
- The latter enjoys full reduction relations.
- Their work incites to consider the Bollobas-Riordan polynomial really as an invariant of graphs cellularly embedded in pseudo-surfaces.
To my opinion, this article is a very nice piece of work and is an example of the fact that it might be interesting sometimes to step back and change our way of considering problems.
Recent Comments