Modifications of Tutte–Grothendieck invariants and Tutte polynomials

Abstract

Generalized Tutte–Grothendieck invariants are mappings from the class of matroids to a commutative ring that are characterized recursively by contraction–deletion rules. Well known examples are Tutte, chromatic, tension and flow polynomials. In general, the rule consists of three formulas valid separately for loops, isthmuses, and the ordinary elements. We show that each generalized Tutte–Grothendieck invariant thus also Tutte polynomials on matroids can be transformed so that the contraction–deletion rule for loops (isthmuses) coincides with the general case.

Keywords:

• Generalized Tutte–Grothendieck invariant
• Isthmus- and loop-smooth modifications
• Tutte polynomial
• Matroid duality
• Deletion–contraction formula

1 Introduction

A generalized Tutte–Grothendieck invariant (shortly a T–G invariant) $\Phi$ is a mapping from the class of finite matroids to a commutative ring $(R,+,\cdot ,0,1)$ such that $\Phi \left(M\right)=\Phi \left(M^{\prime }\right)$ if $M$ is isomorphic to $M^{\prime }$ and there are constants ${\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2\in R$ such that (1) $$\begin{array}{ccc}\hfill & \Phi \left(M\right)=1\hfill & \text{if the ground set of}M\text{is empty,}\hfill \\ \hfill & \Phi \left(M\right)={\alpha }_1\cdot \Phi (M-e)\hfill & \text{if}e\text{is an isthmus of}M\text{,}\hfill \\ \hfill & \Phi \left(M\right)={\beta }_1\cdot \Phi (M-e)\hfill & \text{if}e\text{is a loop of}M\text{,}\hfill \\ \hfill & \Phi \left(M\right)={\alpha }_2\cdot \Phi (M∕e)+{\beta }_2\cdot \Phi (M-e)\hfill & \text{otherwise,}\hfill \end{array}$$(1) for every matroid $M$ and every element $e$ of $M$ (see [1–5]). We also say that $\Phi$ is determined by the quadruple $({\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2)$. In certain sense, all T–G invariants can be derived from the Tutte polynomial of $M$ (2) $$T(M;x,y)=\sum _{A\subseteq E}{(x-1)}^{r\left(E\right)-r\left(A\right)}{(y-1)}^{r^{\ast }\left(E\right)-r^{\ast }(E\setminus A)},$$(2) where $E$ and $r$ denote the ground set and rank function of $M$, respectively (see [1]). This invariant encodes many properties of graphs and has applications in combinatorics, knot theory, statistical physics and coding theory (see cf. [1,6–8]).

If $e$ is a loop or an isthmus of $M$, then $M-e=M∕e$. Thus the second (third) row of (1) is contained in the fourth row if ${\alpha }_1={\alpha }_2+{\beta }_2$ (${\beta }_1={\alpha }_2+{\beta }_2$). In this case we call $\Phi$ an isthmus-smooth (loop-smooth) T–G invariant.

We show that any T–G invariant can be transformed to an isthmus-smooth T–G invariant and to a loop-smooth T–G invariant. The transformations are studied in framework of matroid duality. Furthermore, we discuss modifications of duality and convolution formulas known for the Tutte polynomial. Notice that transformations into isthmus-smooth invariants are used by decomposition formulas of T–G invariants in [3].

2 General modifications

By (2), $T(M;x,y)$ is a sum of polynomials $x^{r_1}{y}^{r_2}$ where $r_1\le r\left(M\right)$, $r_2\le r^{\ast }\left(M\right)$. Hence all denominators in a polynomial $\tilde{T}(M;x_1,y_1,x_2,y_2)=x_2^{r\left(M\right)}{y}_2^{r^{\ast }\left(M\right)}T(M;x_1∕x_2,y_1∕y_2)$ vanish. Thus all fractions in formula ${\alpha }_2^{r\left(M\right)}{\beta }_2^{r^{\ast }\left(M\right)}T(M;{\alpha }_1∕{\alpha }_2,{\beta }_1∕{\beta }_2)$ are only formal and we do not need to assume any restriction for ${\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2\in R$.

Lemma 1

Let ${\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2$ be arbitrary elements of a commutative ring $(R,+,\cdot ,0,1)$. Then ${\alpha }_2^{r\left(M\right)}{\beta }_2^{r^{\ast }\left(M\right)}T(M;{\alpha }_1∕{\alpha }_2,{\beta }_1∕{\beta }_2)$ is the unique T–G invariant determined by quadruple $({\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2)$.

The proof of Lemma 1 is left to the reader. It suffices to use induction on $\left|E\right|$, (1), and that $T(M;x,y)$ is determined by $(x,y,1,1)$ (see cf. [1]). Notice that a simpler form of Lemma 1 was proved in [9] (see also [1, Corollary 6.2.6]).

Theorem 1

If $\Phi$ is a T–G invariant determined by $({\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2)$ and $\xi \in R$, then $${\Phi }_{\xi }^{\mathrm{is}}\left(M\right)={\left(\xi {\beta }_2\right)}^{r\left(M\right)}{\left(\xi ({\alpha }_1-{\alpha }_2)\right)}^{r^{\ast }\left(M\right)}\Phi \left(M\right)$$is an isthmus-smooth T–G invariant such that for every matroid $M$, $$\begin{array}{cc}{\Phi }_{\xi }^{\mathrm{is}}\left(M\right)=1\hfill & \text{if}E=\varnothing ,\hfill \\ {\Phi }_{\xi }^{\mathrm{is}}\left(M\right)=\left(\xi {\beta }_1({\alpha }_1-{\alpha }_2)\right){\Phi }_{\xi }^{\mathrm{is}}(M-e)\hfill & \text{if}e\text{is a loop of}M\text{,}\hfill \\ {\Phi }_{\xi }^{\mathrm{is}}\left(M\right)=\xi {\beta }_2{\alpha }_2{\Phi }_{\xi }^{\mathrm{is}}(M∕e)+\xi {\beta }_2({\alpha }_1-{\alpha }_2){\Phi }_{\xi }^{\mathrm{is}}(M-e)\hfill & \text{otherwise}.\hfill \end{array}$$

Proof

Define by ${\zeta }_1=\xi {\beta }_2$, ${\zeta }_2=\xi ({\alpha }_1-{\alpha }_2)$. Then ${\Phi }_{\xi }^{\mathrm{is}}\left(M\right)={\zeta }_1^{r\left(M\right)}{\zeta }_2^{r^{\ast }\left(M\right)}\Phi \left(M\right)$ for each matroid $M$. By Lemma 1, $\Phi \left(M\right)={\alpha }_2^{r\left(M\right)}{\beta }_2^{r^{\ast }\left(M\right)}T(M;{\alpha }_1∕{\alpha }_2,{\beta }_1∕{\beta }_2)$, whence $$\begin{array}{c}\hfill {\Phi }_{\xi }^{\mathrm{is}}\left(M\right)={\left({\zeta }_1{\alpha }_2\right)}^{r\left(M\right)}{\left({\zeta }_2{\beta }_2\right)}^{r^{\ast }\left(M\right)}T(M;\frac{{\zeta }_1{\alpha }_1}{{\zeta }_1{\alpha }_2},\frac{{\zeta }_2{\beta }_1}{{\zeta }_2{\beta }_2}).\hfill \end{array}$$Thus by Lemma 1, ${\Phi }_{\xi }^{\mathrm{is}}$ is a T–G invariant determined by $({\zeta }_1{\alpha }_1,{\zeta }_2{\beta }_1,{\zeta }_1{\alpha }_2,{\zeta }_2{\beta }_2)$. Furthermore, ${\Phi }_{\xi }^{\mathrm{is}}$ is isthmus-smooth because ${\zeta }_1{\alpha }_1={\zeta }_1{\alpha }_2+{\zeta }_2{\beta }_2$.

We call ${\Phi }_{\xi }^{\mathrm{is}}$ the $\xi$-isthmus-smooth modification of $\Phi$. If $\Phi$ is an isthmus-smooth invariant (i.e., if ${\alpha }_1={\alpha }_2+{\beta }_2$), then ${\Phi }_{\xi }^{\mathrm{is}}\left(M\right)={\left(\xi {\beta }_2\right)}^{\left|E\right|}\Phi \left(M\right)$ for every matroid $M$.

Theorem 2

If $\Phi$ is a T–G invariant determined by $({\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2)$ and $\xi \in R$, then $${\Phi }_{\xi }^{\mathrm{ls}}\left(M\right)={\left(\xi {\alpha }_2\right)}^{r^{\ast }\left(M\right)}{\left(\xi ({\beta }_1-{\beta }_2)\right)}^{r\left(M\right)}\Phi \left(M\right)$$is a loop-smooth T–G invariant such that for every matroid $M$, $$\begin{array}{cc}{\Phi }_{\xi }^{\mathrm{ls}}\left(M\right)=1\hfill & \text{if}E=\varnothing ,\hfill \\ {\Phi }_{\xi }^{\mathrm{ls}}\left(M\right)=\left(\xi {\alpha }_1({\beta }_1-{\beta }_2)\right){\Phi }_{\xi }^{\mathrm{ls}}(M-e)\hfill & \text{if}e\text{is an isthmus of}M\text{,}\hfill \\ {\Phi }_{\xi }^{\mathrm{ls}}\left(M\right)=\xi {\alpha }_2({\beta }_1-{\beta }_2){\Phi }_{\xi }^{\mathrm{ls}}(M∕e)+\xi {\alpha }_2{\beta }_2{\Phi }_{\xi }^{\mathrm{ls}}(M-e)\hfill & \text{otherwise}.\hfill \end{array}$$

Proof

Dual form of the proof of Theorem 1.

We call ${\Phi }_{\xi }^{\mathrm{ls}}$ the $\xi$-loop-smooth modification of $\Phi$. If $\Phi$ is an isthmus invariant, then ${\Phi }_{\xi }^{\mathrm{ls}}\left(M\right)={\left(\xi {\alpha }_2\right)}^{\left|E\right|}\Phi \left(M\right)$ for every matroid $M$.

If $\Phi$ is a T–G invariant determined by $({\alpha }_1,{\beta }_1,{\alpha }_2,{\beta }_2)$, then denote by ${\Phi }^{\ast }$ the T–G invariant determined by $({\beta }_1,{\alpha }_1,{\beta }_2,{\alpha }_2)$. Clearly, $\Phi ={\left({\Phi }^{\ast }\right)}^{\ast }$. By Lemma 1 and the duality formula $T(M;x,y)=T(M^{\ast };y,x)$ (see cf. [1]), (3) $$\Phi \left(M\right)={\Phi }^{\ast }\left(M^{\ast }\right).$$(3) Notice that ${\Phi }_{\xi }^{\mathrm{ls}}={\left({\left({\Phi }^{\ast }\right)}_{\xi }^{\mathrm{is}}\right)}^{\ast }$, whence ${\Phi }_{\xi }^{\mathrm{is}}={\left({\left({\left({\left({\Phi }^{\ast }\right)}^{\ast }\right)}_{\xi }^{\mathrm{is}}\right)}^{\ast }\right)}^{\ast }={\left({\left({\Phi }^{\ast }\right)}_{\xi }^{\mathrm{ls}}\right)}^{\ast }$. Thus (4) $${\Phi }_{\xi }^{\mathrm{ls}}={\left({\left({\Phi }^{\ast }\right)}_{\xi }^{\mathrm{is}}\right)}^{\ast }\text{and}{\Phi }_{\xi }^{\mathrm{is}}={\left({\left({\Phi }^{\ast }\right)}_{\xi }^{\mathrm{ls}}\right)}^{\ast }.$$(4)

If $R$ contains no zero divisors, we can extend $R$ into its quotient field and allow $\xi$ to be any element of $R$ (or the quotient field of $R$) in Theorems 1 and 2.

Theorem 1 (2) has no sense if ${\beta }_2=0$ (${\alpha }_2=0$) or ${\alpha }_1={\alpha }_2$ (${\beta }_1={\beta }_2$). If ${\beta }_2=0$ (${\alpha }_2=0$), then $\Phi \left(M\right)$ is easy to evaluate because by (1), $\Phi \left(M\right)={\beta }_1^{r^{\ast }\left(M\right)}{\alpha }_1^{i_M}{\alpha }_2^{r\left(M\right)-i_M}$ ($\Phi \left(M\right)={\alpha }_1^{r\left(M\right)}{\beta }_1^{l_M}{\beta }_2^{r^{\ast }\left(M\right)-l_M}$), where $i_M$ ($l_M$) denotes the number of isthmuses (loops) in $M$. If $\alpha ={\alpha }_1={\alpha }_2\ne 0$, then we can replace in Lemma 1 formal fraction ${\alpha }_1∕{\alpha }_2$ by $1$ whence $\Phi \left(M\right)={\alpha }^{r\left(M\right)}{\beta }_2^{r^{\ast }\left(M\right)}T(M;1,{\beta }_1∕{\beta }_2)$. Thus by (3), $\Phi \left(M\right)={\alpha }_2^{r\left(M\right)}{\beta }^{r^{\ast }\left(M\right)}T(M;{\alpha }_1∕{\alpha }_2,1)$ if $\beta ={\beta }_1={\beta }_2\ne 0$. Notice that to evaluate $T(M;1,y)$ and $T(M;x,1)$ is in general as difficult as to evaluate $T(M;x,y)$ (see [10–12] for more details).

3 Modifications of the Tutte polynomial

Suppose that $\mathbb{Z}[x,y]$ is the ring of polynomials of variables $x$ and $y$ with integral coefficients and let $\Phi \left(M\right)=T(M;x,y)$. Then $\Phi \left(M\right)$ is a T–G invariant determined by $(x,y,1,1)$ (see cf. [1]). Let $R$ be a commutative ring containing $\mathbb{Z}[x,y]$ and let $\xi \in R$. By Theorem 1, the $\xi$-isthmus-smooth modification of the Tutte polynomial of $M$ is (5) $$T_{\xi }^{\mathrm{is}}(M;x,y)={\xi }^{\left|E\right|}{(x-1)}^{r^{\ast }\left(M\right)}T(M;x,y)$$(5) and satisfies $$\begin{array}{cc}{T}_{\xi }^{\mathrm{is}}(M;x,y)=1\hfill & \text{if}E=\varnothing ,\hfill \\ T_{\xi }^{\mathrm{is}}(M;x,y)=\xi y(x-1)T_{\xi }^{\mathrm{is}}(M-e;x,y)\hfill & \text{if}e\text{is a loop of}M\text{,}\hfill \\ T_{\xi }^{\mathrm{is}}(M;x,y)=\xi T_{\xi }^{\mathrm{is}}(M∕e;x,y)+\xi (x-1)T_{\xi }^{\mathrm{is}}(M-e;x,y)\hfill & \text{otherwise.}\hfill \end{array}$$By Theorem 2, the $\xi$-loop-smooth modification of the Tutte polynomial of $M$ is (6) $$T_{\xi }^{\mathrm{ls}}(M;x,y)={\xi }^{\left|E\right|}{(y-1)}^{r\left(M\right)}T(M;x,y)$$(6) and satisfies $$\begin{array}{cc}{T}_{\xi }^{\mathrm{ls}}(M;x,y)=1\hfill & \text{if}E=\varnothing ,\hfill \\ T_{\xi }^{\mathrm{ls}}(M;x,y)=\xi x(y-1)T_{\xi }^{\mathrm{ls}}(M-e;x,y)\hfill & \text{if}e\text{is an isthmus,}\hfill \\ T_{\xi }^{\mathrm{ls}}(M;x,y)=\xi (y-1)T_{\xi }^{\mathrm{ls}}(M-e;x,y)+\xi T_{\xi }^{\mathrm{ls}}(M∕e;x,y)\hfill & \text{otherwise.}\hfill \end{array}$$By (3), $T_{\xi }^{\mathrm{ls}}(M;x,y)={\left(T_{\xi }^{\mathrm{ls}}\right)}^{\ast }(M^{\ast };x,y)$, and by (4), ${\left(T_{\xi }^{\mathrm{ls}}\right)}^{\ast }(M^{\ast };x,y)={\left(T^{\ast }\right)}_{\xi }^{\mathrm{is}}(M^{\ast };x,y)$. By (1) and (2), $T^{\ast }(M^{\ast };x,y)=T(M^{\ast };y,x)$, whence ${\left(T^{\ast }\right)}_{\xi }^{\mathrm{is}}(M^{\ast };x,y)=T_{\xi }^{\mathrm{is}}(M^{\ast };y,x)$, i.e., we have a variant of the duality formula (7) $$T_{\xi }^{\mathrm{ls}}(M;x,y)=T_{\xi }^{\mathrm{is}}(M^{\ast };y,x).$$(7)

Kook, Reiner, and Stanton [13] introduced the convolution formula $$T(M;x,y)=\sum _{A\subseteq E}T(M∕A;x,0)\cdot T\left(M\right|A;0,y),$$(where $M|A$ and $M∕A$ denote the restriction of $M$ to $A$ and the contraction of $A$ from $M$, respectively). Suppose that $\xi \ne 0$. Then by (5) and (6), $$\begin{array}{c}\hfill T(M;x,y)=\sum _{A\subseteq E}{\xi }^{-\left|E\right|}{(-1)}^{-r(M∕A)}{T}_{\xi }^{\mathrm{ls}}(M∕A;x,0)\cdot {(-1)}^{-r^{\ast }\left(M\right|A)}{T}_{\xi }^{\mathrm{is}}\left(M\right|A;0,y).\hfill \end{array}$$Since $r^{\ast }\left(M\right|A)=\left|A\right|-r\left(A\right)$, $r(M∕A)=r\left(M\right)-r\left(A\right)$, and $2r\left(A\right)-r\left(M\right)-\left|A\right|$ has the same parity as $r\left(M\right)+\left|A\right|$, we get a variant of the convolution formula (8) $$\begin{array}{c}\hfill T(M;x,y)={\xi }^{-\left|E\right|}{(-1)}^{r\left(M\right)}\sum _{A\subseteq E}{(-1)}^{\left|A\right|}{T}_{\xi }^{\mathrm{ls}}(M∕A;x,0)\cdot T_{\xi }^{\mathrm{is}}\left(M\right|A;0,y).\hfill \end{array}$$(8)