![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
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.
1 Introduction
A generalized Tutte–Grothendieck invariant (shortly a T–G invariant) is a mapping from the class of finite matroids to a commutative ring
such that
if
is isomorphic to
and there are constants
such that
(1)
(1) for every matroid
and every element
of
(see [Citation1–5]). We also say that
is determined by the quadruple
. In certain sense, all T–G invariants can be derived from the Tutte polynomial of
(2)
(2) where
and
denote the ground set and rank function of
, respectively (see [Citation1]). This invariant encodes many properties of graphs and has applications in combinatorics, knot theory, statistical physics and coding theory (see cf. [Citation1,6–8]).
If is a loop or an isthmus of
, then
. Thus the second (third) row of (1) is contained in the fourth row if
(
). In this case we call
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 [Citation3].
2 General modifications
By (2), is a sum of polynomials
where
,
. Hence all denominators in a polynomial
vanish. Thus all fractions in formula
are only formal and we do not need to assume any restriction for
.
Lemma 1
Let be arbitrary elements of a commutative ring
. Then
is the unique T–G invariant determined by quadruple
.
The proof of Lemma 1 is left to the reader. It suffices to use induction on , (1), and that
is determined by
(see cf. [Citation1]). Notice that a simpler form of Lemma 1 was proved in [Citation9] (see also [Citation1, Corollary 6.2.6]).
Theorem 1
If is a T–G invariant determined by
and
, then
is an isthmus-smooth T–G invariant such that for every matroid
,
Proof
Define by ,
. Then
for each matroid
. By Lemma 1,
, whence
Thus by Lemma 1,
is a T–G invariant determined by
. Furthermore,
is isthmus-smooth because
.
We call the
-isthmus-smooth modification of
. If
is an isthmus-smooth invariant (i.e., if
), then
for every matroid
.
Theorem 2
If is a T–G invariant determined by
and
, then
is a loop-smooth T–G invariant such that for every matroid
,
Proof
Dual form of the proof of Theorem 1.
We call the
-loop-smooth modification of
. If
is an isthmus invariant, then
for every matroid
.
If is a T–G invariant determined by
, then denote by
the T–G invariant determined by
. Clearly,
. By Lemma 1 and the duality formula
(see cf. [Citation1]),
(3)
(3) Notice that
, whence
. Thus
(4)
(4)
If contains no zero divisors, we can extend
into its quotient field and allow
to be any element of
(or the quotient field of
) in Theorems 1 and 2.
Theorem 1 (2) has no sense if (
) or
(
). If
(
), then
is easy to evaluate because by (1),
(
), where
(
) denotes the number of isthmuses (loops) in
. If
, then we can replace in Lemma 1 formal fraction
by
whence
. Thus by (3),
if
. Notice that to evaluate
and
is in general as difficult as to evaluate
(see [10–12] for more details).
3 Modifications of the Tutte polynomial
Suppose that is the ring of polynomials of variables
and
with integral coefficients and let
. Then
is a T–G invariant determined by
(see cf. [Citation1]). Let
be a commutative ring containing
and let
. By Theorem 1, the
-isthmus-smooth modification of the Tutte polynomial of
is
(5)
(5) and satisfies
By Theorem 2, the
-loop-smooth modification of the Tutte polynomial of
is
(6)
(6) and satisfies
By (3),
, and by (4),
. By (1) and (2),
, whence
, i.e., we have a variant of the duality formula
(7)
(7)
Kook, Reiner, and Stanton [Citation13] introduced the convolution formula
(where
and
denote the restriction of
to
and the contraction of
from
, respectively). Suppose that
. Then by (5) and (6),
Since
,
, and
has the same parity as
, we get a variant of the convolution formula
(8)
(8)
References
- BrylawskiT., OxleyJ., The Tutte polynomial and its applications WhiteN.Matroid Applications1992Cambridge University Press Cambridge 123–225
- ChenB., Dual complementary polynomials of graphs and combinatorial-geometric interpretation on the values of tutte polynomial at positive integers, European J. Combin., 36 2014 206–230
- KocholM., Splitting formulas for Tutte-Grothendieck invariants, J. Combin. Theory Ser. B, 125 2017 114–131
- TraldiL., A dichromatic polynomial for weighted graphs and link polynomials, Proc. Amer. Math. Soc., 106 1989 279–286
- ZaslavskyT., Strong Tutte functions of matroids and graphs, Trans. Amer. Math. Soc., 334 1992 317–347
- BeaudinL., Ellis-MonaghanJ., PangbornG., ShrockR., A little statistical mechanics for the graph theorist, Discrete Math., 310 2010 2037–2053
- JacksonB., SokalA.D., Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids, J. Combin. Theory Ser. B, 99 2009 869–903
- WelshD.J.A. Complexity: Knots, Colourings and Counting London Math. Soc. Lecture Notes Series, vol. 186 1993Cambridge University Press Cambridge
- OxleyJ.G., WelshD.J.A., The Tutte polynomial and percolation BondyJ.A., MurtyU.S.R.Graph Theory and Related Topics1979Academic Press New York 329–339
- GoldbergL.A., JerrumM., Inapproximability of the tutte polynomial, Inform. Comput., 206 2008 908–929
- JaegerF., VertiganD.L., WelshD.J.A., On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc., 108 1990 35–53
- VertiganD., The computational complexity of Tutte invariants for planar graphs, SIAM J. Comput., 135 2005 690–712
- KookW., ReinerV., StantonD., A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B, 76 1999 297–300