# Chain Tutte polynomials

Max Wakefield  US Naval Academy
572-C Holloway Rd
Annapolis MD, 21402 USA<EMAIL_ADDRESS>
###### Abstract.

The Tutte polynomial and Derksen’s $\mathcal{G}$-invariant are the universal
deletion/contraction and valuative matroid and polymatroid invariants,
respectively. There are only a handful of well known invariants (like the
matroid Kazhdan-Lusztig polynomials) between (in terms of roughness/fineness)
the Tutte polynomial and Derksen’s $\mathcal{G}$-invariant. The aim of this
study is to define a spectrum of generalized Tutte polynomials to fill the gap
between the Tutte polynomial and Derksen’s $\mathcal{G}$-invariant. These
polynomials are built by taking repeated convolution products of universal
Tutte characters studied by Dupont, Fink, and Moci and using the framework of
Ardila and Sanchez for studying valuative invariants. We develop foundational
aspects of these polynomials by showing they are valuative on generalized
permutahedra and present a generalized deletion/contraction formula. We apply
these results on chain Tutte polynomials to obtain new formulas for the Möbius
polynomial, the opposite characteristic polynomial, a generalized Möbius
polynomial, Ford’s expected codimension of a matroid variety, and Derksen’s
$\mathcal{G}$-invariant.

##  1\. Introduction

Tutte polynomials were originally defined on graphs by Tutte in [37] while
their coefficients were first investigated by Whitney in [39] (for some
history see [20]). Crapo popularized and generalized Tutte polynomials to
matroids in [11] . Since then Tutte polynomials have become arguably the most
studied invariants on graphs, matroids, hyperplane arrangements, polymatroids,
and extended generalized permutahedra. Recently an entire CRC handbook [17]
edited by Ellis-Monaghan and Moffatt is entirely dedicated to the study of
Tutte polynomials. Most importantly Tutte polynomials are universal among
deletion-contraction invariants, meaning one can formulate any deletion-
contraction invariant, like the chromatic/characteristic polynomial, with the
Tutte polynomial.

Recently there was significant developments on understanding the foundational
aspects of Tutte polynomials. Speyer in [35] showed that the Tutte polynomial
over matroids is valuative from the polytope perspective. The work of Dupont,
Fink, and Moci in [15] presents the Tutte polynomial as a specialization of
Tutte characters on set species which allows them to examine Tutte polynomials
on objects like Delta matroids and prove various convolution formulas. Ardila
and Sanchez in [2] conducted a study of valuative invariants and built
framework for understanding them with convolutions. This led to another proof
that the Tutte polynomial is valuative but over a much larger class of
objects, in particular extended generalized permutahedra. Then just recently,
Ferroni and Schröter in [21] studied in detail some foundational valuations on
certain small matroid subdivisions.

Derksen’s $\mathcal{G}$-invariant gives another perspective on the Tutte
polynomial. Derksen showed in [12] that his $\mathcal{G}$-invariant is
valuative and that the Tutte polynomial can be derived from $\mathcal{G}$.
Then in [13] Fink and Derksen proved that Derksen’s $\mathcal{G}$-invariant
was universal among valuative invariants. Hence between the Tutte polynomial
and Derksen’s $\mathcal{G}$-invariant are the non-deletion/contraction
invariants which are also valuations. Many of these non-deletion/contraction
yet valuative invariants, like the matroid Kazhdan-Lusztig polynomials of [16]
and the Billera-Jia-Reiner quasi-symmetric function of a matroid from [4] and
the matroid volume polynomial of Eur in [18], have not been calculated for
some simple families of matroids like braid arrangements. One reason is that
the known recursions for these invariants are unwieldy. One of the main
motivations for this work is to build structures that will help compute these
invariants. So, one aim here is to develop a generalized deletion-contraction
recursion to help compute valuative matroid invariants. The other main
motivation is to build new finer invariants that may help distinguish certain
types of matroids.

A key focal point of this study is to understand the spectrum between the
Tutte polynomial and Derksen’s $\mathcal{G}$-invariant through what we call
chain Tutte polynomials. We hope that these finer Tutte polynomials can give
more information about some of the more elusive non-deletion/contraction
invariants. We denote these chain Tutte polynomials by $T^{k}$ where $k\geq 1$
and they are defined over matroids or generalized permutahedra. It turns out,
see Corollary 5.31, that for matroids with $n$ many ground set elements that
the $\mathcal{G}$-invariant can be determined from $T^{n}$. Since, as we will
see below, $T^{1}$ is exactly the classical Tutte polynomial, Corollary 5.31
shows directly that our $T^{k}$ form the spectrum starting from the classical
Tutte polynomial all the way up to Derksen’s $\mathcal{G}$-invariant.

Many generalizations of Tutte polynomials are focussed on defining them for
larger classes of combinatorial objects. First we should note that our chain
Tutte polynomials are far from the chain polynomials studied in [31] by Read
and Whitehead and [36] by Traldi. We do not consider weighted graphs or
matroids like that of Zaslavsky in [41]. Farr in [19] considered a rank
generating function for objects with rank functions defined over the entire
real field (not just the non-negative integers). Cameron, Dinu, Michałek, and
Seynnaeve in [10] defined a Tutte polynomial on a flag matroid which is a
sequence of matroids. There are also generalizations to finer invariants. An
important example in the multivariable Tutte polynomial (see [34]) which is a
complete invariant for matroids (we do not know whether or not there is a nice
specialization of the multivariable Tutte polynomial to chain Tutte
polynomials). There is also the work of Bernardi, Kálmán, and Postnikov in [3]
where they define one polynomial for each positive integer $n$ that
parametrizes the Tutte polynomials of all polymatroids with a fixed ground set
size $n$ (again we do not know whether or not one can determine chain Tutte
polynomials from the Universal Tutte polynomials of Bernardi, Kálmán, and
Postnikov). Another perspective was given by Krajewski, Moffatt, and Tanasa in
[27] where a framework is outlined to build Tutte polynomials using Hopf
algebras. Another perspective was given by Miezaki, Oura, Sakuma, and
Shinohara in an announcement paper [28] where they define genus $g$ Tutte
polynomials which are probably the most similar to the study here. However,
the polynomials of Miezaki, Oura, Sakuma, and Shinohara have many more terms
and are much finer invariants than ours. Actually the main result (Theorem 3.1
in [28]) of Miezaki, Oura, Sakuma, and Shinohara is that their collection of
genus $g$ Tutte polynomials are complete invariants for matroids where ours
will never be. Instead the polynomials studied here are a direct spectrum
between the classical Tutte polynomial and the $\mathcal{G}$-invariant. Hence,
the Tutte polynomial generalization we study here is different than all these
works. In particular, though the polynomials in [27] seem close to ours and
have many variables they are not built from sequences of ground set elements
and satisfy a classical “2-term” deletion/contraction formulas instead of our
$k$-term version. We are not generalizing Tutte polynomials to larger or
different classes of objects. Instead we study finer versions of the Tutte
polynomials for matroids and generalized permutahedra which are still rougher
than the multivariable Tutte polynomial, the genus $g$ Tutte polynomials of
Miezaki, Oura, Sakuma, and Shinohara, and Derksen’s $\mathcal{G}$-invariant.

A starting place for this study was the work of Dupont, Fink, and Moci in [15]
where they define universal Tutte characters and their convolutions. The chain
Tutte polynomials we define here are essentially convolution products of
Dupont, Fink, and Moci Tutte characters (from [15]). For this study we use the
language and perspective in [2] where Ardila and Sanchez make the setting of
Tutte characters very concrete. Also, one of Ardila and Sanchez’s main
results, that convolution products of valuations are also valuations (Theorem
C in [2]), allows us to accomplish two results here. First, Ardila and
Sanchez’s perspective helps us view chain Tutte polynomials in the more
general setting of generalized permutahedra. Second, this perspective and
using Theorem C in [2] allows us to conclude that chain Tutte polynomials are
valuations (Proposition 4.6 and Theorem 4.8) on generalized permutahedra and
hence matroids.

One aim for this study is to develop the foundation for chain Tutte
polynomials. In Section 3 we define chain Tutte polynomials, list a few
examples, and present a generalized deletion/contraction formula (see Theorem
3.11) which is exactly a generalized version of the classic
deletion/contraction for the Tutte polynomial. Similarly we show that the
chain Tutte polynomials satisfy a nice duality relation (Proposition 3.4) and
factor over products of matroids (Proposition 3.5), both of which again are
generalizations of the corresponding results for the classic Tutte polynomial.
Also, as discussed above, we generalize the chain Tutte polynomials to
generalized permutahedra by defining a ‘universal’ chain Tutte polynomial and
showing that it is a valuation. This allows us to consider chain Tutte
polynomials on wider classes of objects like polymatroids.

Another aim of this paper is to illustrate the usefulness of chain Tutte
polynomials on a few foundational, yet less studied matroid invariants. More
specifically, we examine a few invariants on matroids which can be computed
directly from chain Tutte polynomials. First we look at some constant
evaluations of the chain Tutte polynomials. While the constant evaluation
formulas we present are not surprising, we include them to illustrate how
chain Tutte polynomials generalize classic formulas for the Tutte polynomial
(for example computing the number of bases of a matroid). Then we consider
some polynomial evaluations of chain Tutte polynomials. It turns out that one
can determine the Möbius polynomial by the second chain Tutte polynomial. The
Möbius polynomial has seen some recent activity in coding theory (see [24] and
[26]) and some applications in non-commutative algebras defined by layered
graphs in [32] by Retakh and Wilson which originated from work of Gelfand,
Retakh, Serconek, and Wilson in [23]. Using the generalized
deletion/contraction formula applied to the evaluation formulas from chain
Tutte polynomials we get a new recursion for the Möbius polynomial (Corollary
5.12). Next we study the characteristic polynomial of the lattice of flats of
a matroid. This opposite characteristic polynomial is also an easy evaluation
of the second chain Tutte polynomial. The reason to study the opposite
characteristic polynomial is that in [25] Johnson and the author presented a
problem to prove that the generalized Möbius function defined using the
$J$-function from [25] is a valuation. We prove this result by proving that
the opposite characteristic polynomial is a valuation since it is an
evaluation of the second chain Tutte polynomial. Next we examine the expected
codimension of a matroid variety defined by Ford in [22]. We show that the
expected codimension is determined by the second chain Tutte polynomial and
then apply our inductive result to obtain a recursion for the expected
codimension. Our last application is to Derksen’s $\mathcal{G}$-invariant. We
show that we can determine Derksen’s $\mathcal{G}$-invariant from the $n^{th}$
chain Tutte polynomial where $n$ is the number of ground set elements. Since
$\mathcal{G}$ is universal, which was proved by Fink and Derksen in [13], we
get that the $n^{th}$ chain Tutte polynomial is equivalent to $\mathcal{G}$.
Hence we have proved that the chain Tutte polynomials have made a spectrum of
finer invariants from the classical Tutte polynomial to the
$\mathcal{G}$-invariant.

We organize this paper as follows. In section 2 we collect some classic facts
about matroids, generalized permutahedra, Möbius functions, Tutte polynomials
and Derksen’s $\mathcal{G}$-invariant. Then in section 3 we define chain Tutte
polynomials and present basic results about them including our main result,
Theorem 3.11, which gives a generalized deletion/contraction formula. Next in
section 4 we generalize chain Tutte polynomials to generalized permutahedra
and prove that chain Tutte polynomials are valuations. We end with section 5
where we examine various applications of chain Tutte polynomials by computing
specific polynomial evaluations. There we study the Möbius polynomial, the
opposite characteristic polynomial, the generalized $J$-Möbius polynomial, the
expected codimension of a matroid variety, and Derksen’s
$\mathcal{G}$-invariant.

Acknowledgments: The author is very thankful to Clément Dupont for teaching
him about universal Tutte characters, Graham Denham for some conversations
about Tutte polynomials, Carolyn Chun for insights on matroid theory, Franklin
Kenter for some comments in graph theory, Will Traves for many helpful
discussions, and Joseph Bonin for helpful comments on matroid theory and
earlier versions of this note. The author is very thankful to Alex Fink for
many helpful comments and mathematical suggestions for an earlier version of
this article. In particular, Fink made the suggestion to find the expected
codimension with the chain Tutte polynomials.

##  2\. Preliminaries

In this section we review some definitions and results as well as some
reformulations of basic properties of well known invariants on matroids and
lattices. For any set $X$ we denote the set of subsets of $X$ (the power set)
by $2^{X}$. For matroid terminology we follow [1] and [30].

###  2.1. Posets and polymatroids

A finite poset $L$ is a ranked lattice if all least upper bounds and greatest
lower bound exist and the length of all maximal chains (properly ordered
sequences of maximal length) are the same. If $L$ is a ranked lattice then the
lub is called a join and denoted by $\vee$ and the glb is called a meet and
denoted by $\wedge$. If a finite lattice $L$ is ranked then it has a rank
function usually denoted by $\mathrm{rk}:L\to\mathbb{Z}_{\geq 0}$ where
$\mathrm{rk}(X)$ is the length of a maximal chain from the least element to
$X$. We say a lower bounded lattice is atomic if every element is a join of
atoms (all the covers of the bottom element $\hat{0}$). Let $L$ be a finite
ranked and atomic lattice with atoms $\mathcal{A}$ and rank function
$\mathrm{rk}$. If $S\subseteq\mathcal{A}$ then we define the rank of $S$ as
$\mathrm{rk}(\bigvee S)$.

######  Definition 2.1.

A (poly)_matroid_ is a pair $M=(\mathcal{A},\mathrm{rk})$ where $\mathcal{A}$
is a finite set, called the ground set and a function
$\mathrm{rk}:2^{\mathcal{A}}\to\mathbb{N}=\\{0,1,2,\dots\\}$ that satisfies

  1. (1)

$\mathrm{rk}(\emptyset)=0$

  2. (2)

for all $a\in\mathcal{A}$, $\mathrm{rk}(a)\in\\{0,1\\}$ (omit this axiom for
polymatroids.)

  3. (3)

for all $X\subseteq Y\subseteq\mathcal{A}$, $\mathrm{rk}(X)\leq\mathrm{rk}(Y)$

  4. (4)

for all $X\subseteq Y\subseteq\mathcal{A}$,
$\mathrm{rk}(X)+\mathrm{rk}(Y)\geq\mathrm{rk}(X\cap Y)+\mathrm{rk}(X\cup Y)$.

A _basis_ of a matroid is a set $B\subseteq\mathcal{A}$ such that
$|B|=\mathrm{rk}(\mathcal{A})=\mathrm{rk}(B)$. The size of a basis of $M$ is
called the _rank_ of $M$ written $\mathrm{rk}(M)$. For any polymatroidal
function $f$ (e.g. $\mathrm{rk}$) we will denote the corresponding function
with a subscript (e.g. $\mathrm{rk}_{M}$) unless the context is clear. A
_flat_ of a matroid $M$ is a set $F\subseteq\mathcal{A}$ such that for all
$x\in\mathcal{A}-F$, $\mathrm{rk}(F\cup\\{x\\})>\mathrm{rk}(F)$. The _lattice
of flats_ of $M$ is $L(M)$ is the set of flats of $M$ ordered by inclusion.
The lattice of flats is a geometric lattice, in particular it is a ranked
atomic lattice. We will often refer to the ground set elements of a matroid
$M$ as atoms since they are the atoms of the lattice of flats and the notation
$\mathcal{A}$ is used in the theory of hyperplane arrangements [29]. An atom
$a\in\mathcal{A}$ is a _loop_ in $M$ if $\mathrm{rk}(a)=0$ and a _coloop_ if
$\mathrm{rk}(\mathcal{A}-a)=\mathrm{rk}(M)-1$. We also say that two atoms
$a,b\in\mathcal{A}$ are _parallel_ if $\mathrm{rk}(\\{a,b\\})=1$. Finally we
say that a matroid is _simple_ if it has no loops or parallel elements.

Note that from an undirected graph $G=(V,E)$ with vertices $V$ and edges $E$
(with multiedges or loops) one can construct a matroid $M=(E,\mathrm{rk})$
where the rank function is defined by $\mathrm{rk}(S)=|S|-c$ where $c$ is the
number of connected components of the induced graph on the vertices $S$. In
Section 3 we will consider some examples defined by graphs.

Many of our constructions can be generalized to a wider setting of ranked
atomic lattices or polymatroids and even generalized permutahedra. However we
chose to keep the aim of most of this work aimed at matroids. Let $Mat$ be the
collection of all matroids.

###  2.2. Möbius function

The Möbius function is $\mu:\mathcal{P}\times\mathcal{P}\to\mathbb{Z}$ where
$\mathcal{P}$ is a locally finite poset defined by setting $\mu(X,X)=1$ and

$\sum\limits_{X\leq Y\leq Z}\mu(X,Y)=0$

for all $X,Z\in\mathcal{P}$. First we recall a classic result on Möbius
functions on matroids by which we mean the Möbius function on the lattice of
flats $L(M)$ of the matroid $M$. For any subset of atoms
$X\subseteq\mathcal{A}$ we write $\bigvee X$ for the join of these atoms
inside the lattice of flats (a.k.a. the flat closure of $X$ in $L(M)$).

######  Lemma 2.2 (Proposition 7.1.4 [40]).

Let $M$ be a simple matroid with minimum flat $\hat{0}=\emptyset$ and maximum
flat $\hat{1}=\mathcal{A}$. Then

$\mu(\hat{0},\hat{1})=\sum\limits_{\begin{subarray}{c}X\subset\mathcal{A}\\\
\bigvee X=\hat{1}\end{subarray}}(-1)^{|X|}.$

For our purposes we need to extend this result slightly. Surely this is in the
literature somewhere, but the author could not find this particular
formulation so we include the proof.

######  Lemma 2.3.

Let $M$ be a matroid with ground set $\mathcal{A}$ and $L(M)$ its lattice of
flats. For all $X,Y\in L(M)$

$\mu(X,Y)=\sum\limits_{\begin{subarray}{c}A\subseteq B\subseteq\mathcal{A}\\\
\bigvee A=X\\\ \bigvee B=Y\end{subarray}}(-1)^{|A|+|B|}$

###### Proof.

Let

$g(X,Y)=\sum\limits_{\begin{subarray}{c}A\subseteq B\subseteq\mathcal{A}\\\
\bigvee A=X\\\ \bigvee B=Y\end{subarray}}(-1)^{|A|+|B|}.$

Then for any fixed $X,Z\in L(M)$

$\displaystyle\sum\limits_{\begin{subarray}{c}Y\in L(M)\\\ X\leq Y\leq
Z\end{subarray}}g(X,Y)=$ $\displaystyle\sum\limits_{\begin{subarray}{c}Y\in
L(M)\\\ X\leq Y\leq
Z\end{subarray}}\left[\sum\limits_{\begin{subarray}{c}A\subseteq
B\subseteq\mathcal{A}\\\ \bigvee A=X\\\ \bigvee
B=Y\end{subarray}}(-1)^{|A|+|B|}\right]$ $\displaystyle=$
$\displaystyle\sum\limits_{\begin{subarray}{c}Y\in L(M)\\\ X\leq Y\leq
Z\end{subarray}}\left[\sum\limits_{\begin{subarray}{c}A\subseteq\mathcal{A}\\\
\bigvee
A=X\end{subarray}}(-1)^{|A|}\left[\sum\limits_{\begin{subarray}{c}B\supseteq
A\\\ \bigvee B=Y\end{subarray}}(-1)^{|B|}\right]\right]$ $\displaystyle=$
$\displaystyle\sum\limits_{\begin{subarray}{c}A\subseteq\mathcal{A}\\\ \bigvee
A=X\end{subarray}}(-1)^{|A|}\left[\sum\limits_{\begin{subarray}{c}Y\in L(M)\\\
X\leq Y\leq Z\end{subarray}}\left[\sum\limits_{\begin{subarray}{c}B\supseteq
A\\\ \bigvee B=Y\end{subarray}}(-1)^{|B|}\right]\right]$ $\displaystyle=$
$\displaystyle\sum\limits_{\begin{subarray}{c}A\subseteq\mathcal{A}\\\ \bigvee
A=X\end{subarray}}(-1)^{|A|}\left[\sum\limits_{\begin{subarray}{c}B\subseteq
E\\\ A\subseteq B\subseteq Z\end{subarray}}(-1)^{|B|}\right].$

The sum in the brackets in the last line above is zero in all cases except
when $A=Z$ where it is 1 and which implies that $X=Z$. Hence we have shown
that the function $g$ satisfies the same recursion as the Möbius function
$\mu$.∎

We want another basic property about Möbius functions.

######  Lemma 2.4.

Let $M$ be a matroid with ground set $\mathcal{A}$, $L(M)$ its lattice of
flats, $\hat{0}$ its minimal flat, and $\hat{1}$ its maximal flat. If $k\geq
2$ then

$\sum\limits_{\begin{subarray}{c}A_{1}\subseteq\cdots\subseteq
A_{k}\subseteq\mathcal{A}\\\ \bigvee A_{1}=\cdots=\bigvee
A_{k}=\hat{1}\end{subarray}}(-1)^{\sum|A_{i}|}=\left\\{\begin{array}[]{cl}1&\text{
if }k\text{ is even}\\\ \mu(\hat{0},\hat{1})&\text{ if }k\text{ is
odd}\end{array}\right..$

###### Proof.

The $k=2$ base case is just Lemma 2.3 in the form of $\mu(\hat{1},\hat{1})$.
When $k$ is even we have a telescoping decomposition

$\sum\limits_{\begin{subarray}{c}A_{1}\subseteq\cdots\subseteq
A_{k}\subseteq\mathcal{A}\\\ \bigvee A_{1}=\cdots=\bigvee
A_{k}=\hat{1}\end{subarray}}(-1)^{\sum|A_{i}|}=\sum\limits_{\begin{subarray}{c}A_{k-1}\subseteq
A_{k}\subseteq\mathcal{A}\\\ \bigvee A_{k-1}=\bigvee
A_{k}=\hat{1}\end{subarray}}(-1)^{|A_{k-1}|+|A_{k}|}\left[\sum\limits_{\begin{subarray}{c}A_{1}\subseteq\cdots\subseteq
A_{k-1}\\\ \bigvee A_{1}=\cdots=\bigvee
A_{k-1}\end{subarray}}(-1)^{\sum|A_{i}|}\right].$

Then by induction the summation in the above bracket is 1. So, using Lemma 2.3
again we get the total is 1. Now suppose that $k>2$ is odd. Similarly we
separate the sum

$\sum\limits_{\begin{subarray}{c}A_{1}\subseteq\cdots\subseteq
A_{k}\subseteq\mathcal{A}\\\ \bigvee A_{1}=\cdots=\bigvee
A_{k}=\hat{1}\end{subarray}}(-1)^{\sum|A_{i}|}=\sum\limits_{\begin{subarray}{c}A_{k}\subseteq\mathcal{A}\\\
\bigvee
A_{k}=\hat{1}\end{subarray}}(-1)^{|A_{k}|}\left[\sum\limits_{\begin{subarray}{c}A_{1}\subseteq\cdots\subseteq
A_{k-1}\subseteq A_{k}\\\ \bigvee A_{1}=\cdots=\bigvee
A_{k}\end{subarray}}(-1)^{\sum|A_{i}|}\right].$

Since the summation in the bracket above has even terms it is 1 and then the
result follows from Lemma 2.2.∎

###  2.3. Tutte and Whitney polynomials

Next we review the classical Whitney rank generating function and the Tutte
polynomial.

######  Definition 2.5.

Let $M=(\mathcal{A},\mathrm{rk})$ be a polymatroid. The Whitney rank
generating function of $M$ is

$W_{M}(a_{1};b_{1})=\sum\limits_{S\subseteq\mathcal{A}}a_{1}^{\mathrm{rk}(M)-\mathrm{rk}(S)}b_{1}^{|S|-\mathrm{rk}(S)}$

and the Tutte polynomial of $M$ is

$T_{M}(x;y)=W_{M}(x-1,y-1)=\sum\limits_{S\subseteq\mathcal{A}}(x-1)^{\mathrm{rk}(M)-\mathrm{rk}(S)}(y-1)^{|S|-\mathrm{rk}(S)}.$

Next we define the characteristic polynomial of a polymatroid. This invariant
will appear in various places in this work.

######  Definition 2.6.

Let $M=(\mathcal{A},\mathrm{rk})$ be a polymatroid and $L(M)$ its lattice of
flats. The characteristic polynomial of $M$ is

$\chi_{M}(t)=\sum\limits_{x\in L(M)}\mu(\hat{0},x)t^{\mathrm{crk}(x)}.$

A key fact is that the characteristic polynomial of a matroids lattice of
flats $L(M)$ is just an evaluation of the Tutte polynomial

$\chi_{M}(t)=T_{M}(1-t;0).$

Now we recall the functions that satisfy a deletion-contraction formula.

######  Definition 2.7.

Let $R$ be a commutative ring and $Mat$ be the collection of matroids. We say
that a function $f:Mat\to R$ is a _generalized Tutte-Grothendieck invariant_
if for any $M\in Mat$ with ground set $\mathcal{A}$ and $e\in\mathcal{A}$

$f(M)=\left\\{\begin{array}[]{lll}af(M\backslash e)+bf(M/e)&&\text{if }e\text{
is neither a loop nor a coloop}\\\ f(M\backslash e)f(L)&&\text{if }e\text{ is
a loop}\\\ f(M/e)f(C)&&\text{if }e\text{ is a coloop}\\\ \end{array}\right.$

for some fixed non-zero constants $a,b\in R$ where $C$ is the matroid of one
coloop and $L$ is a matroid consisting of one loop.

###  2.4. Derksen invariant

In [12] Derksen defined an invariant for polymatroids which have since been
studied by many authors. Then Derksen and Fink in [13] proved that this
invariant is universal for valuative invariants on polymatroids.

A _complete chain_ of a polymatroid $M=(\mathcal{A},\mathrm{rk})$ is a
sequence of subsets $\bar{X}=(X_{i})_{i=0}^{|\mathcal{A}|}$ of $\mathcal{A}$
such that $X_{0}=\emptyset\subset X_{1}\subset\cdots\subset
X_{|\mathcal{A}|}=\mathcal{A}$. Let

$r(\bar{X})=(\mathrm{rk}(X_{1})-\mathrm{rk}(X_{0}),\mathrm{rk}(X_{2})-\mathrm{rk}(X_{1}),\dots,\mathrm{rk}(X_{|\mathcal{A}|})-\mathrm{rk}(X_{|\mathcal{A}|-1}))$

be the rank vector of $\bar{X}$ and $\\{U_{r}\\}$ be a basis for the ring of
quasi-symmetric functions where $r$ runs over all the finite sequences of non-
negative integers.

######  Definition 2.8.

The _Derksen invariant_ of $M$ is the function

$\mathcal{G}(M)=\sum\limits_{\bar{X}}U_{r(\bar{X})}.$

In [12] Derksen proved that the $\mathcal{G}$-invariant (often called the
$\mathcal{G}$-invariant or the Fink-Derksen invariant in the literature, see
[6] and [2]) determined the Tutte polynomial and multiple other important
polymatroid invariants. In subsection 5.6 we will examine the relationship
between our chain Tutte polynomials and Derksen’s $\mathcal{G}$-invariant.

##  3\. Definition and basic properties

Notationally we will denote a sequence of objects (often variables)
$n_{1},\ldots,n_{k}$ by $(n_{i})_{1}^{k}$ or $(n_{i})$ when the indices range
is clear from the context. In this section we define our main object of study
and present some of its fundamental properties.

######  Definition 3.1.

Let $M=(\mathcal{A},\mathrm{rk})$ be a polymatroid with ground set
$\mathcal{A}$. For a positive integer $k$ let

$\mathcal{C}^{k}_{\mathcal{A}}=\left\\{(S_{1},\dots,S_{k})\in\big{(}2^{\mathcal{A}}\big{)}^{k}\
|\ S_{1}\subseteq S_{2}\subseteq\cdots\subseteq S_{k}\right\\}$

and set $\mathcal{C}_{\mathcal{A}}^{0}=\\{()\\}$ where we are considering $()$
as the empty chain. The $k^{th}$ _chain Whitney rank generating polynomial_ of
$M$ is

$W^{k}_{M}((a_{i})_{1}^{k};(b_{i})_{1}^{k})=\sum\limits_{(S_{i})_{1}^{k}\in\mathcal{C}^{k}_{\mathcal{A}}}\prod\limits_{i=1}^{k}(a_{i})^{\mathrm{rk}(M)-\mathrm{rk}(S_{i})}(b_{i})^{|S_{i}|-\mathrm{rk}(S_{i})}.$

Then the $k^{th}$ _chain Tutte polynomial_ of $M$ is

$T^{k}_{M}((x_{i})_{1}^{k};(y_{i})_{1}^{k})=W^{k}_{M}((x_{i}-1)_{1}^{k};(y_{i}-1)_{1}^{k}).$

For convenience we may suppress the variables and just write $T^{k}_{M}$ and
also we will define $W^{0}_{M}=T_{M}^{0}=1$.

######  Remark 3.2.

Some consider this non-homogenous version of the chain Tutte polynomials to be
less useful than the ‘universal’ version we give below in Definition 4.4.
However, for the beginning of this study we focus primarily on the chain
generalization of the classical Tutte polynomial. Also, for matroids these two
polynomials are an invertible change of coordinates of one another as is the
case for the universal Tutte character of the matroids minors systems as shown
by Dupont, Fink, and Moci in [15] Section 5.2.

For most of this study we will focus on the setting of matroids. However, we
may examine the case of a more general ranked, atomic lattice $L$ in which
case we write $T_{L}^{k}((x_{i});(y_{i}))$ where $\mathrm{rk}(S_{i})$ means
the rank of $\mathrm{rk}(\bigvee S_{i})$ in $L$. In this case the atoms are
the ground set elements and for a subset of ground set elements $S_{i}$ the
rank $\mathrm{rk}(S_{i})$ is the usual matroid rank function.

By construction $T^{1}_{M}(x;y)$ is the usual Tutte polynomial (studied on
graphs in [37, 39] and generalized to matroids in [11]). Also, for all $k\geq
1$ the classical Tutte polynomial is contained in every flag Tutte polynomial
since

$T^{k}_{M}(x_{1},2,\ldots,2;y_{1},2\ldots,2)=T^{1}_{M}(x_{1};y_{1}).$

Also, we have the following.

######  Proposition 3.3.

For all $k$ the polynomial $T^{|\mathcal{A}|}_{M}$ determines $T^{k}_{M}$.

###### Proof.

For $k\leq|\mathcal{A}|$ we have that

$T^{|\mathcal{A}|}_{M}(x_{1},\dots,x_{k},2\dots,2;y_{1},\dots,y_{k},2,\dots,2)=T^{k}_{M}(x_{1},\dots,x_{k};y_{1},\dots,y_{k}).$

For $k>|\mathcal{A}|$ any term of $T^{k}_{M}$ will have at least
$k-|\mathcal{A}|$ of the same consecutive exponents on both the $x_{i}$ and
the $y_{i}$ of the form $x_{i}^{a}x_{i+1}^{a}$ and $y_{i}^{c}y_{i+1}^{c}$.
Deleting all these repeats in $T^{k}_{M}$ will give $T^{|\mathcal{A}|}_{M}$. ∎

First we present a few basic facts about these polynomials which generalize
the properties in the classical case of $T^{1}_{M}$. First we show that up to
a change of coordinates the chain Tutte polynomial of the dual matroid is the
same as the matroid.

######  Proposition 3.4.

If $M^{*}$ is the dual matroid of $M$ then

$T^{k}_{M^{*}}(x_{1},\dots,x_{k};y_{1},\dots,y_{k})=T^{k}_{M}(y_{k},\dots,y_{1};x_{k},\dots,x_{1}).$

###### Proof.

First we note that the map sending a flag $(A_{1},\dots,A_{k})$ to its
complement $(\mathcal{A}-A_{k},\dots,\mathcal{A}-A_{1})$ is a permutation of
$\mathcal{C}^{k}(\mathcal{A})$. Then just use Definition 3.1 and the fact that
$\mathrm{rk}_{M^{*}}(X)=|X|-\mathrm{rk}_{M}(\mathcal{A})+\mathrm{rk}_{M}(\mathcal{A}-X)$.∎

The next fact is that $T^{k}$ is multiplicative over matroid direct sum.
Recall that if $M_{1}=(\mathcal{A}_{1},\mathcal{I}_{1})$ and
$M_{2}=(\mathcal{A}_{2},\mathcal{I}_{2})$ are matroids then $M_{1}\oplus
M_{2}=(\mathcal{A}_{1}\sqcup\mathcal{A}_{2},\\{I_{1}\sqcup I_{2}\ |\
I_{1}\in\mathcal{I}_{1},I_{2}\in\mathcal{I}_{2}\\})$.

######  Proposition 3.5.

If $M_{1}=(\mathcal{A}_{1},\mathcal{I}_{1})$ and
$M_{2}=(\mathcal{A}_{2},\mathcal{I}_{2})$ are matroids then

$T^{k}_{M_{1}\oplus
M_{2}}((x_{i});(y_{i}))=T^{k}_{M_{1}}((x_{i});(y_{i}))T^{k}_{M_{2}}((x_{i});(y_{i})).$

###### Proof.

The proof is done by decomposing the definition of $T^{k}_{M_{1}\oplus
M_{2}}((x_{i});(y_{i}))$ in terms of the disjoint sets $\mathcal{A}_{1}$ and
$\mathcal{A}_{2}$. We find that

$T^{k}_{M_{1}\oplus M_{2}}((x_{i});(y_{i}))=$ $\displaystyle=$
$\displaystyle\sum\limits_{(S_{i})\in\mathcal{C}^{k}_{\mathcal{A}}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(\mathcal{A}_{1}\sqcup\mathcal{A}_{2})-\mathrm{rk}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}(S_{i})}$
$\displaystyle=$
$\displaystyle\sum\limits_{(S_{i}^{1})\in\mathcal{C}^{k}_{\mathcal{A}_{1}}}\sum\limits_{(S_{i}^{2})\in\mathcal{C}^{k}_{\mathcal{A}_{2}}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(\mathcal{A}_{1}\sqcup\mathcal{A}_{2})-\mathrm{rk}(S_{i}^{1}\sqcup
S_{i}^{2})}(y_{i}-1)^{|S_{i}^{1}\sqcup S_{i}^{2}|-\mathrm{rk}(S_{i}^{1}\sqcup
S_{i}^{2})}$ $\displaystyle=$
$\displaystyle\sum\limits_{(S_{i}^{1})\in\mathcal{C}^{k}_{\mathcal{A}_{1}}}\sum\limits_{(S_{i}^{2})\in\mathcal{C}^{k}_{\mathcal{A}_{2}}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(\mathcal{A}_{1})+\mathrm{rk}(\mathcal{A}_{2})-\mathrm{rk}(S_{i}^{1})-\mathrm{rk}(S_{i}^{2})}(y_{i}-1)^{|S_{i}^{1}|+|S_{i}^{2}|-\mathrm{rk}(S_{i}^{1})-\mathrm{rk}(S_{i}^{2})}$
$\displaystyle=$
$\displaystyle\sum\limits_{(S_{i}^{1})\in\mathcal{C}^{k}_{\mathcal{A}_{1}}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(\mathcal{A}_{1})-\mathrm{rk}(4S_{i}^{1})}(y_{i}-1)^{|S_{i}^{1}|-\mathrm{rk}(S_{i}^{1})}$
$\displaystyle\cdot$
$\displaystyle\sum\limits_{(S_{i}^{2})\in\mathcal{C}^{k}_{\mathcal{A}_{2}}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(\mathcal{A}_{2})-\mathrm{rk}(S_{i}^{2})}(y_{i}-1)^{|S_{i}^{2}|-\mathrm{rk}(S_{i}^{2})}$

which is exactly the product
$T^{k}_{M_{1}}((x_{i});(y_{i}))T^{k}_{M_{2}}((x_{i});(y_{i})).$ ∎

######  Example 3.6.

Let $\mathcal{B}_{1}$ be the rank 1 Boolean lattice (subset lattice of a set
with 1 element) also known as the free matroid on one element or $U_{1,1}$ or
the matroid of one coloop $C$. Then by direct computation

$T^{k}_{\mathcal{B}_{1}}((x_{i});(y_{i}))=1+\sum\limits_{i=1}^{k}\prod\limits_{j=1}^{i}(x_{j}-1).$

Notice that even $T^{2}_{\mathcal{B}_{1}}(x_{1},x_{2};y_{1},y_{2})$ has
negative coefficients. Then since Theorem 3.5 we have that

$T^{k}_{\mathcal{B}_{n}}((x_{i});(y_{i}))=\left(1+\sum\limits_{i=1}^{k}\prod\limits_{j=1}^{i}(x_{j}-1)\right)^{n}$

where $\mathcal{B}_{n}$ is the free matroid on $n$ elements (aka Boolean
subset lattice or the uniform matroid $U_{n,n}$).

$G_{1}$$G_{2}$ Figure 1. The Gray graphs

Now we show that the second chain Tutte polynomial $T^{2}$ has more
information than the Tutte polynomial $T^{1}$ for a few classic examples.

######  Example 3.7.

The two Gray graphs $G_{1}$ and $G_{2}$, pictured in Figure 1 (see Example 3.4
in [12] and [9]), have the same Tutte polynomial even though they are not
isomorphic graphs. However, the second chain Tutte polynomials differ for
$G_{1}$ and $G_{2}$. The differences range from terms of the form
$x_{1}^{4}x_{2}^{2}y_{1}y_{2}^{2}$ to $y_{1}y_{2}^{3}$ (these computations
were made using Sage [14]).

######  Example 3.8.

$M_{1}$$M_{2}$ Figure 2. Two non-isomorphic matroids with same Tutte
polynomial $T^{1}$ but different chain Tutte polynomial $T^{2}$

Let $M_{1}$ and $M_{2}$ be the rank 3 matroids on 7 elements in Figure 2 ([8]
Example 6.2.18). The coefficient of $a_{1}^{2}a_{2}b_{1}b_{2}^{2}$ in
$W^{2}_{M_{1}}$ is 2, but the coefficient of the same monomial in
$W^{2}_{M_{2}}$ is 1. However, the classic Tutte polynomial of these two
matroids is the same. The Derksen invariant $\mathcal{G}$ also distinguishes
these two matroids ([12] Example 3.6).

We will see below in Section 4.2 that Derksen’s $G$-invariant determines
$T^{k}$ for any $k>0$. Hence, also the chain Tutte polynomials $T^{k}$ for all
$k$ will not distinguish the examples built by Bonin in [5] and Bonin and Long
in [7]. As is the case with the classical Tutte polynomial even the dart graph
and kite graph (shown in Figure 3) are not distinguished by all the chain
Tutte polynomials.

dart graphkite graph Figure 3. The dart graph and the kite graph are not
distinguished by any chain Tutte polynomials

Now we look at a few examples to show that $T^{k}$ for $k>1$ is not a
generalized Tutte-Grothendieck invariant.

######  Example 3.9.

Let $L=U_{0,1}$ be the matroid of a loop, $C=\mathcal{B}_{1}=U_{1,1}$ be the
matroid of a coloop, $D=U_{1,2}$ be the rank 1 matroid with two parallel
elements,$U_{2,3}$ be the uniform matroid on three elements of rank 2, and
$U_{2,4}$ be the uniform matroid on four elements of rank 2. Since the
deletion and contraction by any element in a uniform matroid results in
isomorphic matroids we can arbitrarily choose any element to evaluate the
deletion-contraction property. The deletions and contractions of these
matroids are as follows: $U_{2,4}\backslash e=U_{2,3}$, $U_{2,4}/e=U_{1,3}$,
$U_{2,3}\backslash e=U_{2,2}$, $U_{2,3}/e=D$, $D\backslash e=C$ and $D/e=L$.
We can compute
$T^{2}_{L}=(x_{1}-1)(x_{2}-1)+(x_{1}-1)(x_{2}-1)(y_{2}-1)+(x_{1}-1)(x_{2}-1)(y_{1}-1)(y_{2}-1)$,

$T^{2}_{D}=(x_{1}-1)(x_{2}-1)+2(x_{1}-1)+(x_{1}-1)(y_{2}-1)+2(y_{2}-1)+(y_{1}-1)(y_{2}-1)+2$

and using the computer algebra system Sage [14] we compute

$T^{2}_{U_{2,3}}=x_{1}^{2}x_{2}^{2}+x_{1}^{2}x_{2}-2x_{1}x_{2}^{2}+x_{1}^{2}y_{2}+x_{1}x_{2}+x_{2}^{2}+x_{1}y_{2}+y_{1}y_{2}-2x_{2}-y_{1}+1.$

Then we assume that there does exist rational functions $a,b$ such that for
any non-loop or coloop the deletion-contraction formula of Definition 2.7
holds. Examining $D$ first we have

$T^{2}_{D}=aT^{2}_{C}+bT^{2}_{L}$

which gives

$a=\frac{T^{2}_{D}-bT^{2}_{L}}{T^{2}_{C}}.$

Then in the case of $U_{2,3}$ we get

$T^{2}_{U_{2,3}}=aT^{2}_{C^{2}}+bT^{2}_{D}$

and putting these last two together gives

$b=\frac{T^{2}_{U_{2,3}}T^{2}_{C}-T^{2}_{D}}{T^{2}_{D}T^{2}_{C}-T^{2}_{C}}.$

Finally with $U_{2,4}$ we have

$T^{2}_{U_{2,4}}=aT^{2}_{U_{2,3}}+bT^{2}_{U_{1,3}}.$

Inserting our values for $a$ and $b$ and clearing denominators we find that

(1)
$(T^{2}_{D}T^{2}_{C}-T^{2}_{C})T^{2}_{C}T_{U_{2,4}}^{2}=T^{2}_{D}T^{2}_{U_{2,3}}-(T^{2}_{U_{2,3}}T^{2}_{C}-T^{2}_{D})T_{L}^{2}T^{2}_{U_{2,3}}+(T^{2}_{U_{2,3}}T^{2}_{C}-T^{2}_{D})T^{2}_{U_{1,3}}.$

Then we use Sage again to show that the left hand side of (1) is not the same
as the right hand side of (1). Hence it’s not possible for $T^{2}$ to be a
generalized Tutte-Grothendieck invariant. Since $T^{2}$ is contained in
$T^{k}$ for all $k>1$ we know that these are also not generalized Tutte-
Grothendieck invariants.

Next we define another polynomial for use in an inductive formula for the
chain Tutte polynomial which we call a split Tutte polynomial. This polynomial
has three inputs: the matroid, a ground set element, and an integer for where
the split occurs. In order to define it we need to recall some more matroid
operations. For a matroid $M=(\mathcal{A},\mathcal{I})$ the _deletion_ of $M$
by $a\in\mathcal{A}$ is the matroid $M\backslash S=(\mathcal{A}\backslash
a,\mathcal{I}^{\prime})$ where
$\mathcal{I}^{\prime}=\\{I\subseteq\mathcal{A}\backslash a\ |\
I\in\mathcal{I}\\}$. The _contraction_ of $M$ by $a\in\mathcal{A}$ is the
matroid $M\backslash a=(\mathcal{A}\backslash a,\mathcal{I}^{\prime\prime})$
where

$\mathcal{I}^{\prime\prime}=\left\\{\begin{array}[]{ll}\\{I\subseteq\mathcal{A}\backslash
S|I\cup a\in\mathcal{I}\\}&\text{ if }a\text{ is not a loop}\\\
\mathcal{I}&\text{ if }a\text{ is a loop}\end{array}\right._{.}$

Then if $S\subseteq\mathcal{A}$ we can consider the deletion and contraction
by repeatedly deleting and contracting by elements in $S$ and we denote these
by $M\backslash S$ and $M/S$ respectively. The rank functions of these
successive deletions and contractions satisfy $\mathrm{rk}_{M\backslash
S}(A)=\mathrm{rk}_{M}(A)$ and $\mathrm{rk}_{M/S}(A)=\mathrm{rk}_{M}(A\cup
S)-\mathrm{rk}_{M}(S)$ for $A\subseteq\mathcal{A}\backslash S$.

######  Definition 3.10.

Let $M$ be a matroid with atoms $\mathcal{A}$ and $k\in\mathbb{Z}_{\geq 0}$.
Then we define the $k^{th}$ _split chain Tutte polynomial_ of $M$ and
$a\in\mathcal{A}$ at split term $j$ where $0\leq j\leq k$ by
$sT^{k,0}_{M,a}=T^{k}_{M/a}$, $sT^{k,k}_{M,a}=T^{k}_{M\backslash a}$, and for
$j\in\\{1,\ldots,k-1\\}$

$sT^{k,j}_{M,a}((x_{i}),(y_{i}))=$
$\sum\limits_{(S_{i})_{1}^{k-j}\in\mathcal{C}^{k-j}_{\mathcal{A}-a}}T^{j}_{M|_{S_{1}}}\prod\limits_{i=1}^{k-j}(x_{i+j}-1)^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S_{i})}(y_{i+j}-1)^{|S_{i}|-\mathrm{rk}_{M/a}(S_{i})}\prod\limits_{i=1}^{j}(x_{i}-1)^{\mathrm{rk}(M/S_{1})}.$

Note that the split chain Tutte polynomials of Definition 3.10 are just
reorderings (so that we can see the smaller chain Tutte polynomials in the
summation) of the original chain Tutte polynomials separated by terms
containing or not containing the element $a\in M$. Those can again be
rearranged to

$\displaystyle sT^{k,j}_{M,a}((x_{i}),(y_{i}))$ $\displaystyle=$
$\displaystyle=\sum\limits_{(S_{i})_{1}^{j}\in\mathcal{C}^{j}_{\mathcal{A}-a}}\prod\limits_{i=1}^{j}(x_{i}-1)^{\mathrm{rk}(M\backslash
a)-\mathrm{rk}_{M\backslash
a}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}_{M\backslash a}(S_{i})}$
$\displaystyle\cdot\sum\limits_{\begin{subarray}{c}(S_{i})_{j+1}^{k}\in\mathcal{C}^{k-j}_{\mathcal{A}-a}\\\
S_{j}\subseteq
S_{j+1}\end{subarray}}\prod\limits_{i=j+1}^{k}(x_{i}-1)^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}_{M/a}(S_{i})}$

which is why we used the word split in the name. Hence, loosely speaking,
these polynomials are somewhere between deletion and contraction.

By construction for $a\in\mathcal{A}$ not a loop and not a coloop we can state
the classical recursion for the Tutte polynomial as

$T^{1}_{M}=sT^{1,0}_{M,a}+sT^{1,1}_{M,a}.$

Now we generalize this for $k>1$.

######  Theorem 3.11.

For a matroid $M=(\mathcal{A},\mathcal{I})$ and $a\in\mathcal{A}$ that is not
a loop and not a coloop

$T^{k}_{M}=\sum\limits_{j=0}^{k}sT^{k,j}_{M,a}.$

###### Proof.

We split the terms of $T^{k}_{M}$ up by which sets contain $a\in\mathcal{A}$.
For $j\in\\{1,\ldots,k-1\\}$ let

$st_{M,a}^{k,0}((x_{i});(y_{i}))=\sum\limits_{\begin{subarray}{c}(S_{i})_{1}^{k}\in\mathcal{C}^{k}_{\mathcal{A}}\\\
a\in
S_{1}\end{subarray}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(M)-\mathrm{rk}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}(S_{i})},$
$st_{M,a}^{k,k}((x_{i});(y_{i}))=\sum\limits_{(S_{i})_{1}^{k}\in\mathcal{C}^{k}_{\mathcal{A}-a}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(M)-\mathrm{rk}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}(S_{i})},$

and

$st_{M,a}^{k,j}((x_{i});(y_{i}))=\sum\limits_{\begin{subarray}{c}(S_{i})_{j+1}^{k}\in\mathcal{C}^{k-j}_{\mathcal{A}}\\\
a\in
S_{j+1}\end{subarray}}\sum\limits_{(S_{i})_{1}^{j}\in\mathcal{C}^{j}_{S_{j+1}-a}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(M)-\mathrm{rk}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}(S_{i})}.$

Then by construction

$T_{M}^{k}=\sum\limits_{j=0}^{k}st_{M,a}^{k,j}((x_{i});(y_{i})).$

We know that for all $S\subseteq\mathcal{A}$ with $a\in S$ we have
$\mathrm{rk}_{M}(S)=\mathrm{rk}_{M/a}(S-a)+\mathrm{rk}_{M}(a)$. Since
$a\in\mathcal{A}$ is not a loop for all $S\subseteq\mathcal{A}$ with $a\in S$
we have
$|S|-\mathrm{rk}(S)=|S-a|+1-(\mathrm{rk}_{M/a}(S-a)+\mathrm{rk}_{M}(a))=|S-a|-\mathrm{rk}_{M/a}(S-a)$.
Also, for $S\subseteq\mathcal{A}$ with $a\in S$ we have
$\mathrm{rk}(M)-\mathrm{rk}_{M}(S)=(\mathrm{rk}_{M/a}(\mathcal{A}-a)+\mathrm{rk}_{M}(a))-(\mathrm{rk}_{M/a}(S-a)+\mathrm{rk}_{M}(a))=\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S-a)$.
Putting this into the $j=0$ term we have

$st_{M,a}^{k,0}((x_{i});(y_{i}))=\sum\limits_{\begin{subarray}{c}(S_{i})_{1}^{k}\in\mathcal{C}^{k}_{\mathcal{A}}\\\
a\in
S_{1}\end{subarray}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S_{i}-a)}(y_{i}-1)^{|S_{i}-a|-\mathrm{rk}_{M/a}(S_{i}-a)}$
$=\sum\limits_{(S_{i})_{1}^{k}\in\mathcal{C}^{k}_{\mathcal{A}-a}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}_{M/a}(S_{i})}=T^{k}_{M/a}=sT^{k,0}_{M,a}.$

In the $j=k$ case the argument is much simpler. Since $a\in A$ is not a coloop
we know that $rk(M)=\mathrm{rk}(M\backslash a)$. So,

$st^{k,k}_{M,a}=\sum\limits_{(S_{i})_{1}^{k}\in\mathcal{C}^{k}_{\mathcal{A}-a}}\prod\limits_{i=1}^{k}(x_{i}-1)^{\mathrm{rk}(M\backslash
a)-\mathrm{rk}_{M\backslash
a}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}_{M\backslash
a}(S_{i})}=T^{k}_{M\backslash a}=sT^{k,k}_{M,a}.$

Now for any $j\in\\{1,\ldots,k-1\\}$ we see that

$st_{M,a}^{k,j}((x_{i});(y_{i}))=\sum\limits_{\begin{subarray}{c}(S_{i})_{j+1}^{k}\in\mathcal{C}^{k-j}_{\mathcal{A}}\\\
a\in
S_{j+1}\end{subarray}}\prod\limits_{i=j+1}^{k}(x_{i}-1)^{\mathrm{rk}(M)-\mathrm{rk}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}(S_{i})}\phi_{j}$

where

$\phi_{j}=\sum\limits_{(S_{i})_{1}^{j}\in\mathcal{C}^{j}_{S_{j+1}-a}}\prod\limits_{i=1}^{j}(x_{i}-1)^{\mathrm{rk}(M)-\mathrm{rk}(S_{i})}(y_{i}-1)^{|S_{i}|-\mathrm{rk}(S_{i})}.$

Notice that
$\mathrm{rk}(M)=\mathrm{rk}_{M\backslash[\mathcal{A}-(S_{j+1}-a)]}(S_{j+1}-a)+\mathrm{rk}_{M/(S_{j+1}-a)}(\mathcal{A}-(S_{j+1}-a))$.
Using this we see that

$\phi_{j}=\left[\prod\limits_{i=1}^{j}(x_{i}-1)^{\mathrm{rk}(M/(S_{j+1}-a))}\right]T^{j}_{M\backslash[\mathcal{A}-(S_{j+1}-a)]}.$

Then we note that for $a\in S_{j+1}\subseteq\cdots\subseteq S_{k}$ we know
that
$\mathrm{rk}(M)-\mathrm{rk}(S_{i})=\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S_{i}-a)$
and that $|S_{i}|-\mathrm{rk}_{M}(S_{i})=|S_{i}-a|-\mathrm{rk}_{M/a}(S_{i}-a)$
since $a$ is not a loop. Hence

$st^{k,j}_{M,a}=\sum\limits_{\begin{subarray}{c}(S_{i})_{j+1}^{k}\in\mathcal{C}^{k-j}_{\mathcal{A}}\\\
a\in
S_{j+1}\end{subarray}}\prod\limits_{i=j+1}^{k}(x_{i}-1)^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S_{i}-a)}(y_{i}-1)^{|S_{i}-a|-\mathrm{rk}_{M/a}(S_{i}-a)}\phi_{j}.$

Now that each term has $a$ taken out we reindex and write this as

$st^{k,j}_{M,a}=\sum\limits_{(S_{i})_{1}^{k-j}\in\mathcal{C}^{k-j}_{\mathcal{A}-a}}\prod\limits_{i=1}^{k-j}(x_{i+j}-1)^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S_{i})}(y_{i+j}-1)^{|S_{i}|-\mathrm{rk}_{M/a}(S_{i})}\phi_{j}^{\prime}$

where

$\phi_{j}^{\prime}=\left[\prod\limits_{i=1}^{j}(x_{i}-1)^{\mathrm{rk}(M/S_{1})}\right]T^{j}_{M\backslash[\mathcal{A}-S_{1}]}.$

Since this is exactly the definition of our split Tutte polynomials we are
done. ∎

Now the formulas for the cases where $a\in\mathcal{A}$ is a loop or coloop is
much simpler. The proofs follow in a similar manner by straightforward
computation.

######  Proposition 3.12.

  1. (1)

For a matroid $M=(\mathcal{A},\mathcal{I})$ and $a\in\mathcal{A}$ that is a
loop

$T^{k}_{M}(x_{1},\ldots,x_{k};y_{1},\dots,y_{k})=T^{k}_{L}(x_{1},\ldots,x_{k};y_{1},\dots,y_{k})T^{k}_{M\backslash
a}(x_{1},\ldots,x_{k};y_{1},\dots,y_{k})$

were $L$ is the matroid of a loop.

  2. (2)

For a matroid $M=(\mathcal{A},\mathcal{I})$ and $a\in\mathcal{A}$ that is a
coloop

$T^{k}_{M}(x_{1},\ldots,x_{k};y_{1},\dots,y_{k})=T^{k}_{C}(x_{1},\ldots,x_{k};y_{1},\dots,y_{k})T^{k}_{M/a}(x_{1},\ldots,x_{k};y_{1},\dots,y_{k})$

where $C$ is the matroid of a coloop.

##  4\. Generalized permutahedra and Valuations

We start with the definition of generalized permutahedra where we follow
Ardila-Sanchez [2]. Then we will focus on the submonoid of matroids and show
how our polynomials are specializations of the more general universal version.

###  4.1. Generalized permutahedra

First we note that a function $f:2^{\mathcal{A}}\to\mathbb{R}$ is
_semimodular_ if for all $A,B\subseteq\mathcal{A}$ the function $f$ satisfies
$f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$.

######  Definition 4.1.

A _generalized permutahedron_ is a polytope $P$ in $\mathbb{R}^{\mathcal{A}}$
which is of the form

$P=\\{x\in\mathbb{R}^{\mathcal{A}}\ |\
\sum\limits_{i\in\mathcal{A}}x_{i}=z(\mathcal{A})\text{ and }\sum\limits_{i\in
S}x_{i}\leq z(S)\text{ for all }S\subseteq\mathcal{A}\\}$

where $z:2^{\mathcal{A}}\to\mathbb{R}$ is a submodular function. We denote the
Hopf monoid of generalized permutahedra by ${\bf GP}$ with coproduct
$\Delta_{S_{1},\dots,S_{k}}$.

Next we need to consider how polytopes decompose into pieces. The idea is to
construct invariants on polytopes inductively by their pieces.

######  Definition 4.2.

A generalized permutahedra _subdivision_ of a polytope $P$ is a set of
generalized permutahedra $\\{P_{1},\dots,P_{s}\\}$ whose vertices are vertices
of $P$,

$P=\bigcup_{i=1}^{s}P_{i}$

and for all $1\leq i<j\leq s$ if $P_{i}\cap P_{j}\neq\emptyset$ then
$P_{i}\cap P_{j}$ is a proper face of both $P_{i}$ and $P_{j}$.

Now we can state the definition of a valuation using the subdivisions which is
the main subject of the section.

######  Definition 4.3.

A function $f:{\bf GP}\to A$ where $R$ is an algebra is a _valuation_ if for
any $P\in{\bf GP}$ and any subdivision of $P$ into $\\{P_{1},\dots,P_{k}\\}$
where $P_{i}\in{\bf GP}$ we have $f(\emptyset)=0$ and

$f(P)=\sum\limits_{\\{j_{1},\dots,j_{i}\\}\subseteq[k]}(-1)^{i}f(P_{j_{1}}\cap\cdots\cap
P_{j_{i}}).$

Next we focus on some chain polynomials which are slightly different than
those defined in Definition 3.1. To do this again we follow Ardila and Sanchez
[2]. In Definition 6.2 [2] Ardila and Sanchez present a convolution of species
maps $f_{i}:{\bf GP}\to R$ for $i\in[k]$ where $R$ is an algebra over
$\mathbb{F}$ with multiplication $m$. The _convolution_ of these functions is
the species map $f_{1}\star f_{2}\star\cdots\star f_{k}:{\bf GP}\to R$ defined
by

$f_{1}\star f_{2}\star\cdots\star
f_{k}[\mathcal{A}](P)=\sum\limits_{S_{1}\sqcup\cdots\sqcup
S_{k}=\mathcal{A}}m\circ f_{1}[S_{1}]\otimes\cdots\otimes
f_{k}[S_{k}]\circ\Delta_{S_{1},\dots,S_{k}}(P).$

Now we present a universal chain Tutte polynomial on ${\bf GP}$ defined using
a species map defined in the proof of Proposition 7.4 in [2].

######  Definition 4.4.

Let $N_{i}[\mathcal{A}](P)=u_{i}^{|\mathcal{A}|}v_{i}^{z_{P}(\mathcal{A})}$
where $z_{P}$ is the semimodular function defining $P$. The $k^{th}$
_universal chain Tutte polynomial_ is

$uT^{k}_{P}((u_{i});(v_{i}))=N_{1}\star N_{2}\star\cdots\star
N_{k}[\mathcal{A}](P).$

######  Remark 4.5.

On the wider class of extended generalized permutahedra the function in
Definition 4.3 is only a weak valuation. However, on the family of generalized
permutahedra weak valuations are equivalent to strong ([13] Theorem 3.5),
hence in our case we just refer to these functions as valuations.

Now we can state a nice fact which is a result of the construction in
Definition 4.4.

######  Proposition 4.6.

The $k^{th}$ universal chain Tutte polynomial $uT^{k}$ is a valuation on ${\bf
GP}$.

###### Proof.

In Proposition 7.4 of [2] Ardila and Sanchez show that $N_{i}$ is a valuation
on the species of extended generalized permutahedra. Then by Corollary 6.3
also in [2] we have the conclusion.∎

###  4.2. Matroid valuations

First we recall the basis matroid polytope (using [2] as our general reference
for this material). A matroid $M$ can be defined via its set of bases
$\mathcal{B}(M)$ which are all the independent sets of $M$ whose size is the
rank of $M$. Then the matroid polytope of $M$ is

$P(M)=\mathrm{Conv}\\{e_{B}|B\in\mathcal{B}(M)\\}$

where $e_{B}=e_{i_{1}}+\cdots+e_{i_{r}}$ with $B=\\{i_{1},\dots,i_{r}\\}$. Now
we need a few key definitions to state our main result. These are exactly the
same as Definitions 4.2 and 4.3 restricted to the submonoid of matroids.

######  Definition 4.7.

A _matroid polyhedral subdivision_ of a matroid polytope $P(M)$ is a
subdivision of $P(M)$ where all the pieces are matroid polytopes.

Now we want to know how invariants decompose across subdivisions which gives
rise to valuations. Again we note that weak and strong valuations are the same
on the family of matroids and call a function $f:Mat\to R$ a _matroid
valuation_ if it is a valuation of matroid polytopes.

Now we note that the monoid of matroids is a submonoid of ${\bf GP}$ so we can
restrict our universal chain Tutte polynomial to the monoid of matroids. In
the case of matroids the coproduct on a set decomposition
$\mathcal{A}=S_{1}\sqcup\cdots\sqcup S_{k}$ with $A_{0}=\emptyset$ and
$A_{i}=S_{1}\sqcup\cdots\sqcup S_{i}$ is (Lemma 2.7 [2])

$\Delta_{S_{1},\dots,S_{k}}(M)=M[A_{0},A_{1}]\otimes
M[A_{1},A_{2}]\otimes\cdots\otimes M[A_{k-1},A_{k}]$

where $M[A,B]=(M|_{B})/A$. For matroid polytopes the associated semimodular
function is exactly the rank function ($\mu_{P(M)}=\mathrm{rk}_{M}$). Then the
$i^{th}$ term in the product of $uT^{k}$ is

$N_{i}[S_{i}](P(M[A_{i-1},A_{i}]))=u_{i}^{|S_{i}|}v_{i}^{\mathrm{rk}_{(M|_{A_{i}})/A_{i-1}}(S_{i})}.$

Putting this all together the $k^{th}$ universal chain Tutte polynomial of a
matroid polytope $P(M)$ is

(2) $\displaystyle uT^{k}_{P(M)}((u_{i});(v_{i}))$
$\displaystyle=\sum\limits_{S_{1}\sqcup\cdots\sqcup
S_{k}=\mathcal{A}}\prod\limits_{i=1}^{k}N_{i}[S_{i}](P(M[A_{i-1},A_{i}]))$ (3)
$\displaystyle=\sum\limits_{A_{1},\dots,A_{k}\in\mathcal{C}_{\mathcal{A}}^{k}}\prod_{i=1}^{k}u_{i}^{|A_{i}-A_{i-1}|}v_{i}^{\mathrm{rk}(A_{i})-\mathrm{rk}(A_{i-1})}$

where $A_{0}=\emptyset$ and $A_{k}=\mathcal{A}$ in the summation (3). From
this we get the following Corollary.

######  Theorem 4.8.

The $k^{th}$ chain Whitney polynomial and chain Tutte polynomial are matroid
valuations.

###### Proof.

First we make a change of coordinates by setting $u_{k+1}=1$,
$v_{1}=b_{1}^{-1}\cdots b_{k}^{-1}$, $v_{k+1}=a_{1}\cdots a_{k}$, for
$i\in[k]$

$u_{i}=\prod_{j=i}^{k}b_{j}$

and for $1<i<k+1$

$v_{i}=\prod_{j=i}^{k}b_{j}^{-1}\prod_{j=1}^{i-1}a_{j}.$

Putting this change of coordinates into the formulation of $uT^{k+1}_{P(M)}$
in (3) we get

$uT^{k+1}_{P(M)}((u_{i});(v_{i}))=\sum\limits_{A_{1},\dots,A_{k+1}\in\mathcal{C}_{\mathcal{A}}^{k+1}}\prod_{i=1}^{k+1}u_{i}^{|A_{i}-A_{i-1}|}v_{i}^{\mathrm{rk}(A_{i})-\mathrm{rk}(A_{i-1})}$
$=\sum\limits_{A_{1},\dots,A_{k+1}\in\mathcal{C}_{\mathcal{A}}^{k+1}}\prod_{i=1}^{k}\left(\prod_{j=i}^{k}b_{j}\right)^{|A_{i}-A_{i-1}|}\left(\prod_{j=i}^{k}b_{j}^{-1}\prod_{j=1}^{i-1}a_{j}\right)^{\mathrm{rk}(A_{i})-\mathrm{rk}(A_{i-1})}(a_{1}\cdots
a_{k})^{\mathrm{rk}(A_{k+1})-\mathrm{rk}(A_{k})}.$

In each of these terms we see that the exponent of $a_{i}$ is

$\sum\limits_{j=i}^{k+1}\mathrm{rk}(A_{j+1})-\mathrm{rk}(A_{j})=\mathrm{rk}(M)-\mathrm{rk}(A_{i})$

since $A_{k+1}=\mathcal{A}$ and the exponent of $b_{i}$ is

$\sum\limits_{j=1}^{i}\big{(}|A_{j}-A_{j-1}|-(\mathrm{rk}(A_{j})-\mathrm{rk}(A_{j-1}))\big{)}=|A_{i}|-\mathrm{rk}(A_{i}).$

Hence with this change of coordinates of
$uT^{k+1}_{P(M)}((u_{i})_{1}^{k+1};(v_{i})_{1}^{k+1})$ is the chain Whitney
polynomial $W^{k}_{M}((a_{i})_{1}^{k};(b_{i})_{1}^{k})$. Then restricting to
the submonoid of matroids of ${\bf GP}$ using Proposition 4.6 we can conclude
$W^{k}_{M}$ and also $T^{k}_{M}$ are matroid valuations. ∎

######  Remark 4.9.

It’s possible that the formulation of the universal chain Tutte polynomial in
(3) is more useful or more ‘universal’ than Definition 3.1. In the next
section we use the version from Definition 3.1 to find formulas for some
interesting invariants that are not evaluations of the classic Tutte
polynomial. However it may be easier to use the version in (3) to find
formulas for other invariants like the matroid Kazhdan-Lusztig polynomials in
[16].

##  5\. Chain Tutte evaluations and specializations

In this section we study various evaluations and specializations of chain
Tutte polynomials to find information about interesting matroid invariants.
One idea we visit repeatedly is to find an evaluation that gives an
interesting invariant and then apply the recursion from Theorem 3.11 to find
new formulas. The main result of this section is that the “top” Tutte
polynomial $T^{|\mathcal{A}|}_{M}$ is equivalent to Derksen’s $G$-invariant.
We start with some basic constant evaluations and then look at some more
complicated polynomials and finish with Derksen’s $G$-invariant. For most of
this section we will just focus on $T^{2}$.

###  5.1. Constant evaluations

We begin by discussing some constant evaluations of $T^{k}_{M}$ which are
straightforward to describe combinatorially and are essentially obtained from
the classical Tutte polynomial. However, we examine some which are more
complicated and are not easily recognizable formulations. The following few
formulations of constant evaluations can be concluded directly from the
definition.

######  Proposition 5.1.

For any matroid $M$ we have

$T^{k}_{M}(1,\dots,1;1,\dots,1)=|\mathcal{B}|$

where $\mathcal{B}$ is the set of bases of $M$.

######  Proposition 5.2.

For any matroid $M$ with independent sets $\mathcal{I}$ we have

$T^{k}_{M}(2,\dots,2;1,2,\dots,2)=T^{k}_{M}(2,\dots,2;(y_{i}))=|\mathcal{I}|$

where $(y_{i})$ is any sequence that has exactly one 1 and the rest 2’s.

Next we look at an example of a different constant evaluation.

######  Example 5.3.

Let $\mathcal{B}_{n}$ be the Boolean matroid of rank $n$ (a.k.a the uniform
matroid of rank $n$ on $n$ elements). Then
$T^{k}_{\mathcal{B}_{1}}(2,\dots,2;1,\dots,1)=k+1$ since a flag of subsets of
a set with one element is determined by how many empty sets are in the
sequence. Using this and Theorem 3.5 we get that

$T^{k}_{\mathcal{B}_{n}}(2,\dots,2;1,\dots,1)=(k+1)^{n}.$

The Boolean matroids are fairly simple to understand since there is only one
basis. Still can reformulate the result of Example 5.3 in general in the $k=2$
case.

######  Proposition 5.4.

Let $M$ be a matroid and $I_{m}$ be the number of independent sets of size $m$
in $M$. Then

$T^{2}_{M}(2,2;1,1)=\sum\limits_{m=0}^{\mathrm{rk}(M)}2^{m}I_{m}.$

If we swap the 1’s and 2’s in the above we get some more complicated numbers.
Recall that $T^{1}_{M}(1;2)$ is the number of spanning sets of the matroid.
Now we examine $T^{2}_{M}(1,1;2,2)$ and again we need more notation.

######  Proposition 5.5.

Let $SP$ be the set of spanning sets of $M$ and for $X\in SP$ let $NSP(X)$ be
the number of subsets of $X$ that are also spanning. Then

$T^{2}_{M}(1,1;2,2)=\sum\limits_{X\in SP}NSP(X).$

The evaluation $T^{2}_{M}(1,2;2,1)$ is also easy since it counts the number of
independent sets that are full rank. This is the number of bases. If we switch
the 1’s and 2’s in this last evaluation we get something a little more
interesting.

######  Proposition 5.6.

For $X\in SP$ a spanning set let $NI(X)$ be the number of independent sets
inside $X$. Then

$T^{2}_{M}(2,1;1,2)=\sum\limits_{X\in SP}NI(X).$

We can phrase Proposition 5.6 in terms of graphs.

######  Example 5.7.

Let $G$ be an undirected graph with $M_{G}$ the associated matroid. Then for
any spanning subgraph $G^{\prime}$ the number of independent sets inside this
subgraph is the number of subforests. Hence

$T^{2}_{M_{G}}(2,1;1,2)=\sum\limits_{G^{\prime}\text{
spanning}}NF(G^{\prime})$

where $NF(G^{\prime})$ is the number of subforests in $G^{\prime}$. These
numbers seem interesting for complete graphs $K_{n}$ and cycle graphs $C_{n}$.
Using the computer algebra system Sage [14] we compute these evaluations in
Tables 1 and 2.

$n$ | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
$T^{2}_{M_{K_{n}}}(2,1;1,2)$ | 1 | 2 | 19 | 523 | 36478
Table 1. The (2,1;1,2) evaluations for complete graphs $n$ | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---
$T^{2}_{M_{C_{n}}}(2,1;1,2)$ | 19 | 47 | 111 | 255 | 575
Table 2. The (2,1;1,2) evaluations for cycle graphs

Now we consider slightly more complicated evaluations.

######  Proposition 5.8.

If $M$ is a matroid with minimal flat $\hat{0}$ and maximal flat $\hat{1}$
then

$T^{k}_{M}(1,1,\dots,1;0,0,\dots,0)=\left\\{\begin{array}[]{cl}1&\text{ if
}k\text{ is even}\\\ \mu(\hat{0},\hat{1})&\text{ if }k\text{ is
odd}\end{array}\right..$

###### Proof.

We compute

$T^{k}_{M}(1,1,\dots,1;0,0,\dots,0)=\sum\limits_{\begin{subarray}{c}S_{1}\subseteq\cdots\subseteq
S_{k}\subseteq\mathcal{A}\\\ \bigvee S_{1}=\cdots=\bigvee
S_{k}=\hat{1}\end{subarray}}(-1)^{\sum|S_{i}|}.$

Then Lemma 2.4 gives the result. ∎

Now switching the zeros and ones we get a similar result. Recall that
$T^{1}_{M}(0;1)$ is the reduced Euler characteristic of its independence
complex (see [1] Section 7.7.1).

######  Proposition 5.9.

If $M$ is a matroid with $\chi$ its independence complex reduced Euler
characteristic and $k\geq 1$ then

$T^{k}_{M}(0,0,\dots,0;1,1,\dots,1)=\left\\{\begin{array}[]{cl}1&\text{ if
}k\text{ is even}\\\ \chi&\text{ if }k\text{ is odd}\end{array}\right..$

###### Proof.

Assume that $k>1$ is even. In this case there is again a telescoping of the
sum but this time the sets are all independent:

$T^{k}_{M}(0,0,\dots,0;1,1,\dots,1)=\sum\limits_{\begin{subarray}{c}S_{1}\subseteq\cdots\subseteq
S_{k}\subseteq\mathcal{A}\\\
\text{independent}\end{subarray}}(-1)^{\sum|S_{i}|}$

$=\sum\limits_{\begin{subarray}{c}S_{k}\subseteq\mathcal{A}\\\
\text{independent}\end{subarray}}(-1)^{|S_{k}|}\sum\limits_{\begin{subarray}{c}S_{k-1}\subseteq
S_{k}\\\
\text{independent}\end{subarray}}(-1)^{|S_{k-1}|}\cdots\sum\limits_{\begin{subarray}{c}S_{1}\subseteq
S_{2}\\\ \text{independent}\end{subarray}}(-1)^{|S_{1}|}.$

The individual sum

$\sum\limits_{\begin{subarray}{c}S_{1}\subseteq S_{2}\\\
\text{independent}\end{subarray}}(-1)^{|S_{1}|}$

is 0 unless $S_{2}=\emptyset$. If $S_{2}=\emptyset$ then this pair

$\sum\limits_{\begin{subarray}{c}S_{2}\subseteq S_{3}\\\
\text{independent}\end{subarray}}(-1)^{|S_{2}|}\left[\sum\limits_{\begin{subarray}{c}S_{1}\subseteq
S_{2}\\\
\text{independent}\end{subarray}}(-1)^{|S_{1}|}\right]=(-1)^{|\emptyset|}=1.$

Since $k$ is even each pair reduces to 1 and we have the desired result.
Finally if $k$ is odd then the same decomposition has all the pairs inside the
sum reduce to 1 and the last summation term

$\sum\limits_{\begin{subarray}{c}S_{k}\subseteq\mathcal{A}\\\
\text{independent}\end{subarray}}(-1)^{|S_{k}|}$

remains as is exactly the reduced Euler characteristic (again see Section
7.7.1 in [1]). ∎

###  5.2. The Möbius polynomial

The Möbius polynomial was used by Jurrius in [26] to study weight enumerators
of error-correcting linear codes. Then recently Johnsen and Verdure studied
the Möbius polynomial on error-correcting codes from a commutative algebra
view point in [24]. Here we study the Möbius polynomial exclusively and find
it is a simple evaluation of the $2^{nd}$ chain Tutte polynomial.

######  Definition 5.10.

The _Möbius polynomial_ of a matroid $M$ is

$\bar{\chi}_{M}(s,t)=\sum\limits_{X\leq Y\in
L(M)}\mu(X,Y)s^{\mathrm{crk}(X)}t^{\mathrm{crk}(Y)}.$

######  Proposition 5.11.

If $M$ is a matroid then

$T^{2}_{M}(1-s,1-t;0,0)=\bar{\chi}_{M}(s,t).$

###### Proof.

First we compute the evaluation of the second flag Tutte polynomial:

$\displaystyle T^{2}_{L(M)}(1-s,1-t;0,0)=$
$\displaystyle\sum\limits_{A\subseteq B\subseteq
E}(-s)^{\mathrm{crk}(A)}(-t)^{\mathrm{crk}(B)}(-1)^{|A|+|B|-\mathrm{rk}(A)-\mathrm{rk}(B)}$
$\displaystyle=$ $\displaystyle\sum\limits_{A\subseteq B\subseteq
E}(-1)^{|A|+|B|}s^{\mathrm{crk}(A)}t^{\mathrm{crk}(B)}$ $\displaystyle=$
$\displaystyle\sum\limits_{X\leq Y\in
L(M)}\left[\sum\limits_{\begin{subarray}{c}A\subseteq B\subseteq E\\\ \bigvee
B=X\\\ \bigvee
B=Y\end{subarray}}(-1)^{|A|+|B|}\right]s^{\mathrm{crk}(X)}t^{\mathrm{crk}(Y)}.$

Then by Lemma 2.3 we are done since that is exactly the Definition 5.10 of the
Möbius polynomial.∎

Note that the Möbius polynomial is not a Tutte-Grothendieck invariant by using
the evaluation in Proposition 5.11 applied to the sequence of matroids in
Example 3.9. However, applying the recursion from Theorem 3.11 and the
evaluation for $T^{2}$ from Theorem 5.11 we get a new recursion for the Möbius
polynomial.

######  Corollary 5.12.

If $M=(\mathcal{A},\mathcal{I})$ is a matroid and $a\in\mathcal{A}$ is not a
loop or coloop then

$\displaystyle\bar{\chi}_{M}(s,t)=$ $\displaystyle\bar{\chi}_{M\backslash
a}(s,t)+\bar{\chi}_{M/a}(s,t)$
$\displaystyle+(-1)^{\mathrm{rk}(M/a)}\sum\limits_{S\subseteq\mathcal{A}-a}(-1)^{\mathrm{rk}(M/S)+|S|}s^{\mathrm{rk}(M/S)}t^{\mathrm{rk}(M/a)-\mathrm{rk}(S)}\chi_{M\backslash[\mathcal{A}-S]}(s).$

Putting Proposition 5.11 and Proposition 5.8 together gives a quick proof that
$\bar{\chi}_{M}(0,0)=1$ (which is an easy fact from the Möbius function and
should be in the literature but the author failed to find it). We also get to
conclude that the Möbius polynomial is a valuation from combining Theorem 4.8
and Proposition 5.11.

######  Corollary 5.13.

The Möbius polynomial $\bar{\chi}$ is a valuation on the submonoid of
matroids.

###  5.3. Opposite characteristic polynomial

Let $M$ be a matroid and $L(M)$ its lattice of flats. The order on $L(M)$ is
given by inclusion. If we just reverse this inclusion order we get the lattice
$L(M)^{op}$ which is the same set of flats but with reverse inclusion order
(in the case of a hyperplane arrangement $L^{op}$ would be the regular
inclusion order on intersections). This opposite order on flats is not
necessarily atomic nor semimodular. However $L(M)^{op}$ is still a ranked
lattice and so we can consider its characteristic polynomial.

######  Definition 5.14.

The _opposite characteristic polynomial_ of a matroid $M$ with top flat
$\hat{1}$ is

$\chi^{op}_{M}(t)=\chi_{L(M)^{op}}(t)=\sum\limits_{x\in
L(M)^{op}}\mu(\hat{1},x)t^{\mathrm{crk}(x)}.$

Even this polynomial has a relatively simple evaluation formula using the
chain Tutte polynomial.

######  Proposition 5.15.

If $M$ is a matroid then

$T^{2}_{M}(1-t,1;0,0)=t^{\mathrm{rk}(M)}\chi^{op}_{L(M)}(t^{-1}).$

###### Proof.

We compute the evaluation

(4) $T^{2}_{M}(1-t,1;0,0)=\sum\limits_{\begin{subarray}{c}A\subseteq
B\subseteq\mathcal{A}\\\ B\text{
spanning}\end{subarray}}(-1)^{\mathrm{rk}(M)-\mathrm{rk}(A)+|A|+|B|-\mathrm{rk}(A)-\mathrm{rk}(B)}t^{\mathrm{rk}(M)-\mathrm{rk}(A)}.$

Since $B$ is spanning we know that $\mathrm{rk}(B)=\mathrm{rk}(M)$ hence (4)
becomes

(5) $\sum\limits_{\begin{subarray}{c}A\subseteq B\subseteq\mathcal{A}\\\
B\text{
spanning}\end{subarray}}(-1)^{|A|+|B|}t^{\mathrm{rk}(M)-\mathrm{rk}(A)}.$

Then we split the sum of (5) on $A$ by flats as

(6) $\sum\limits_{X\in L(M)}\left(\sum\limits_{\begin{subarray}{c}A\subseteq
B\subseteq\mathcal{A}\\\ \bigvee A=X\\\ \bigvee
B=\hat{1}\end{subarray}}(-1)^{|A|+|B|}\right)t^{\mathrm{rk}(M)-\mathrm{rk}(X)}.$

Applying Lemma 2.3 to the inner sum of (6) we get

(7) $\sum\limits_{X\in L(M)}\mu(X,\hat{1})t^{\mathrm{rk}(M)-\mathrm{rk}(X)}.$

Since the Möbius function can be defined recursively from the top element
$\hat{1}$ we have that (7) becomes

(8) $t^{\mathrm{rk}(M)}\sum\limits_{X\in
L(M)^{op}}\mu^{op}(\hat{1},X)(t^{-1})^{\mathrm{rk}(X)}.$

Since the corank in $L(M)^{op}$ is actually the rank in $L(M)$ the expression
in (8) is actually $t^{\mathrm{rk}(M)}\chi^{op}_{L(M)}(t^{-1})$ and we have
proved the result. ∎

Again we get to combine the evaluation result, in this case Proposition 5.15,
with Theorem 4.8 to conclude the opposite characteristic polynomial is a
valuation.

######  Corollary 5.16.

The opposite characteristic polynomial is a valuation on matroids.

We also restrict the recursion from the chain Tutte polynomial in Theorem 3.11
to the opposite characteristic polynomial. Again note that the opposite
characteristic polynomial is not a Tutte-Grothendieck invariant (use the
evaluation in Proposition 5.15 with Example 3.9).

######  Corollary 5.17.

If $M=(\mathcal{A},\mathrm{rk})$ is a matroid and $a\in\mathcal{A}$ is not a
loop or coloop then

$\chi^{op}_{M}(t)=\chi^{op}_{M\backslash
a}(t)+\chi^{op}_{M/a}(t)+(-1)^{\mathrm{rk}(M)-1}\sum\limits_{\begin{subarray}{c}S\subseteq\mathcal{A}-a\\\
\text{span}M/a\end{subarray}}(-1)^{|S|}\chi_{M|_{S}}(t).$

###### Proof.

Because of the formula in Proposition 5.15 we plug that evaluation into
Theorem 3.11. We simplify the split Tutte polynomial

$\displaystyle sT^{2,1}_{M,a}(1-t,1;0,0)$
$\displaystyle=\sum\limits_{S\subseteq\mathcal{A}-a}T^{1}_{M|_{S}}(1-t;0)(0)^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(S)}(-1)^{|S|-\mathrm{rk}_{M/a}(S)}(-t)^{\mathrm{rk}(M/S)}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}S\subseteq\mathcal{A}-a\\\
\text{span}M/a\end{subarray}}\chi_{M|_{S}}(t)(-1)^{|S|-\mathrm{rk}(M/a)}(-t)^{0}$

which finishes the proof. ∎

From this recursive result we can conclude some nice things about these
opposite characteristic polynomials and an example is the next corollary (even
though it is clear from the definition).

######  Corollary 5.18.

If $M$ is a simple matroid with $\mathrm{rk}(M)>0$ then $\chi^{op}_{M}(1)=0$.

###### Proof.

We proceed by induction on the number of ground set elements of $M$. If there
is one element and the rank is one then $\chi^{op}_{M}(t)=t-1$. Then for
larger sets of ground set elements the recursion in Corollary 5.17 finished
the proof.∎

###  5.4. Generalized Möbius polynomial

In [25] a function $J$ was studied that generalizes the Möbius function and it
was used to define and study a generalized Möbius polynomial. Also in [25] it
was conjectured that this generalized Möbius polynomial was a matroid
valuation. We prove that conjecture in this subsection.

######  Definition 5.19.

The $J$-function on a matroid $M$ with ground set $\mathcal{A}$ is
$J:\mathcal{F}l_{\mathcal{A}}^{3}\to R$ where $R$ is a commutative ring and
$\mathcal{F}l_{\mathcal{A}}^{3}$ is 3-flags of flats in $L(M)$ defined
recursively by $J(x,x,x)=1$ for all $x\in L(M)$ and

$\sum\limits_{x\leq a\leq y\leq b\leq z}J(a,y,b)=\delta_{3}(x,y,z)$

for all $(x,y,z)\in\mathcal{F}l_{\mathcal{A}}^{3}$ where $\delta_{3}$ is the
3-variable Kroncker delta function.

In [25] it was shown that this $J$-function satisfies various generalizations
of the Möbius function. This led the authors there to define analogous
generalized characteristic and Möbius polynomials.

######  Definition 5.20.

The generalized $J$-Möbius polynomial of $M$ is

$\mathcal{M}_{M}(t)=\sum\limits_{(x,y,z)\in\mathcal{F}l^{3}(L(M))}J(x,y,z)t^{\mathrm{crk}(x)+\mathrm{crk}(y)+\mathrm{crk}(z)}.$

Also in [25] it was shown that this generalized $J$-Möbius polynomial
satisfies a decomposition with the classic characteristic polynomials.

######  Proposition 5.21 (Proposition 6.10 [25]).

If $M$ is a matroid then

$\mathcal{M}_{M}(t)=t^{\mathrm{rk}(M)}\sum\limits_{y\in
L(M)}t^{\mathrm{crk}(y)}\chi_{L(M)^{y}}(t)\chi_{(L(M)^{\mathrm{op}})^{y}}(t^{-1}).$

Now putting together Proposition 5.21 and Corollary 5.16 we can answer
Question 6.26 of [25].

######  Corollary 5.22.

The generalized $J$-Möbius polynomial is a valuation on matroids.

###  5.5. Expected codimension and Ford’s $S$-polynomial

Understanding properties in general of the realization space of a matroid
(a.k.a. matroid variety) is an elusive endeavor (see [38] and [33]). In [22]
Ford studied the dimension of matroid varieties and when the dimensions could
be computed combinatorially. To do this Ford defined the following.

######  Definition 5.23 (Definition 1.1 [22]).

Let $M=(\mathcal{A},\mathrm{rk})$ be a matroid and
$a:2^{\mathcal{A}}\to\mathbb{Z}$ be defined recursively by $a(\emptyset)=0$
and

$a(A)=\mathrm{crk}(A)-\sum\limits_{B\subset A}a(B).$

The _expected codimension of_ $M$ is

$ec(M)=\sum\limits_{A\subseteq\mathcal{A}}(\mathrm{rk}(M)-\mathrm{rk}(A))a(A).$

The idea behind this definition is that counting Plücker coordinates gives a
way to guess the codimension of the matroid variety. Then Ford in [22] proves
that for positroids this expected codimension is actually the codimension of
the positroids realization space. The final result in Ford’s paper on this
expected dimension is that it is a valuative property. Hence a natural
question is how we can produce this expected dimension from these chain Tutte
polynomials. It turns out we can do this via another polynomial which Ford
defines in his paper.

######  Definition 5.24 (Lemma 5.4 [22]).

Let $M=(\mathcal{A},\mathrm{rk})$ be a matroid. The Ford $S$-polynomial of $M$
is

$S_{M}(x,y,z)=\sum\limits_{A\subseteq
B\subseteq\mathcal{A}}x^{|A|-\mathrm{rk}(A)}y^{\mathrm{rk}(M)-\mathrm{rk}(B)}z^{|B|-|A|}.$

Next in [22] Ford proves that this polynomial $S_{M}(x,y,z)$ is a matroid
valuation using similar technique to Speyer’s proof in [35] that the Tutte
polynomial is a matroid valuation. It turns out that we can find this $S_{M}$
polynomial in $T^{2}$ which gives another proof that it is a matroid
valuation.

######  Proposition 5.25 (Lemma 5.4 [22]).

The Ford $S$-polynomial is a matroid valuation.

###### Proof.

Since $T^{2}$ is a matroid valuation and

$T^{2}_{M}(z+1,yz^{-1}+1;xz^{-1}+1,z+1)=S_{M}(x,y,z)$

we have concluded the result.∎

Using the Proof of Theorem 5.3 in [22] we get the formula for expected
codimension in terms of $T^{2}$.

######  Corollary 5.26.

For any matroid $M$

$ec(M)=\frac{\partial}{\partial x}\frac{\partial}{\partial
y}\left[T^{2}_{M}(z+1,yz^{-1}+1;xz^{-1}+1,z+1)\right](1,1,-1).$

Now examine the recursive result on $T^{2}$, Theorem 3.11, applied to Ford’s
$S$-polynomial.

######  Proposition 5.27.

If $M=(\mathcal{A},\mathrm{rk})$ is a matroid and $a\in\mathcal{A}$ is not a
loop or coloop then

$\displaystyle S_{M}(x,y,z)=$ $\displaystyle S_{M\backslash
a}(x,y,z)+S_{M/a}(x,y,z)$ $\displaystyle+z\sum\limits_{A\subseteq
B\subseteq\mathcal{A}-a}x^{|A|-\mathrm{rk}(A)}y^{\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(B)}z^{|B|-|A|}\
.$

Note that the recursion of Proposition 5.27 appears very close to
$S_{M\backslash a}(x,y,z)+(1+z)S_{M/a}(x,y,z)$. However this is not correct
and if it were correct then it would imply that $ec(M)=ec(M\backslash a)$
which is also not true in general.

Now putting together Proposition 5.27 and Corollary 5.26 we have a new
recursion for the expected codimension of a matroid.

######  Corollary 5.28.

If $M=(\mathcal{A},\mathrm{rk})$ is a matroid with $a\in\mathcal{A}$ not a
loop or coloop then

$ec(M)=ec(M\backslash a)+ec(M/a)-\sum\limits_{A\subseteq
B\subseteq\mathcal{A}}(|A|-\mathrm{rk}(A))(\mathrm{rk}(M/a)-\mathrm{rk}_{M/a}(B))(-1)^{|B|-|A|}.$

###  5.6. Derksen’s $G$-invariant

In this subsection we show that the polynomial $W^{|\mathcal{A}|}_{M}$ is
“combinatorially equivalent” to Derksen’s $G$-invariant. To do this we set up
some notation. We say that a sequence of integers
$(a_{1},\dots,a_{|\mathcal{A}|},b_{1},\dots,b_{|\mathcal{A}|})$ is an
_exponent complete chain_ for the matroid $M$ if
$a_{i}-b_{i}=\mathrm{rk}(M)-i$ for all $i\in\\{1,\dots,|\mathcal{A}|\\}$. Let
$EC(M)$ be the set of exponent complete chains of $M$.

######  Proposition 5.29.

If $c_{e}$ is the coefficient of the monomial $u_{1}^{a_{1}}\cdots
u_{|\mathcal{A}|}^{a_{|\mathcal{A}|}}v_{1}^{b_{1}}\cdots
v_{|\mathcal{A}|}^{b_{|\mathcal{A}|}}$ in $W^{|\mathcal{A}|}_{M}$ where
$e=(a_{1},\dots,a_{|\mathcal{A}|},b_{1},\dots,b_{|\mathcal{A}|})$ is a
exponent complete chain then the Derksen invariant is

$G(M)=\sum\limits_{e\in
EC(M)}c_{e}U_{(\mathrm{rk}(M)-a_{1},a_{1}-a_{2},\dots,a_{|\mathcal{A}|-1}-a_{|\mathcal{A}|})}.$

###### Proof.

Let $u_{1}^{a_{1}}\cdots
u_{|\mathcal{A}|}^{a_{|\mathcal{A}|}}v_{1}^{b_{1}}\cdots
v_{|\mathcal{A}|}^{b_{|\mathcal{A}|}}$ be a monomial in
$W^{|\mathcal{A}|}_{M}$ where
$e=(a_{1},\dots,a_{|\mathcal{A}|},b_{1},\dots,b_{|\mathcal{A}|})$ is a
exponent complete chain. Then the chains that make up this term in
$W^{|\mathcal{A}|}_{M}$ are of the form $(A_{1},\dots,A_{|\mathcal{A}|})$
where
$a_{i}-b_{i}=\mathrm{rk}(M)-\mathrm{rk}(A_{i})-(|A_{i}|-\mathrm{rk}(A_{i}))=\mathrm{rk}(M)-i$
for all $i\in\\{1,\dots,|\mathcal{A}|\\}$. This implies that $|A_{i}|=i$,
hence $(A_{0}=\emptyset,A_{1},\dots,A_{|\mathcal{A}|})$ is a complete chain.
The coefficient $c_{e}$ counts the number of complete chains whose ranks are
$(\mathrm{rk}(M)-a_{i})_{i=1}^{|\mathcal{A}|}$. Hence the rank vector of of
this sequence is
$(\mathrm{rk}(M)-a_{1},\mathrm{rk}(M)-a_{2}-(\mathrm{rk}(M)-a_{1})),\dots,\mathrm{rk}(M)-a_{|\mathcal{A}|}-(\mathrm{rk}(M)-a_{|\mathcal{A}|-1}))=(\mathrm{rk}(M)-a_{1},a_{1}-a_{2},\dots,a_{|\mathcal{A}|-1}-a_{|\mathcal{A}|}).$
∎

In [13] Derksen and Fink proved that the $G$-invariant is universal among
valuative invariants.

######  Theorem 5.30 ([13] Theorem 1.4).

The coefficients of $\mathcal{G}$ span the vector space of all valuative
matroid invariants with values in $\mathbb{Q}$.

Combining Theorem 4.8, Proposition 5.29, and Theorem 5.30 we can conclude the
following.

######  Corollary 5.31.

The chain Tutte polynomial $T_{M}^{|\mathcal{A}|}$ can be determined by the
$\mathcal{G}$-invariant and visa versa.

######  Remark 5.32.

Together with Proposition 3.3, Corollary 5.31 implies that $\mathcal{G}$
determines all possible chain Tutte polynomials. We do not investigate a
generalization of Theorem 1.1 in [6] attributed to Derksen. We also do not try
to find the smallest $k$ such that $T^{k}$ determines the
$\mathcal{G}$-invariant, even though it seems clear that
$T^{\mathrm{rk}(M)}_{M}$ will determine the $\mathcal{G}$-invariant due to the
catenary data presentation given by Bonin and Kung in [6]. Actually, $T^{k}$
may determine the $\mathcal{G}$-invariant when
$k=min\\{\mathrm{rk}(M),\mathrm{crk}(M)\\}$ because of Proposition 3.4.

## References

  * [1] Federico Ardila, _Algebraic and geometric methods in enumerative combinatorics_ , Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 3–172. MR 3409342
  * [2] Federico Ardila and Mario Sanchez, _Valuations and the Hopf Monoid of Generalized Permutahedra_ , Int. Math. Res. Not. IMRN (2023), no. 5, 4149–4224. MR 4565665
  * [3] Olivier Bernardi, Tamás Kálmán, and Alexander Postnikov, _Universal Tutte polynomial_ , Adv. Math. 402 (2022), Paper No. 108355, 74. MR 4401824
  * [4] Louis J. Billera, Ning Jia, and Victor Reiner, _A quasisymmetric function for matroids_ , European J. Combin. 30 (2009), no. 8, 1727–1757. MR 2552658
  * [5] Joseph E. Bonin, _Matroids with different configurations and the same $\mathcal{G}$-invariant_, J. Combin. Theory Ser. A 190 (2022), Paper No. 105637, 22. MR 4417274
  * [6] Joseph E. Bonin and Joseph P. S. Kung, _The $\mathcal{G}$-invariant and catenary data of a matroid_, Adv. in Appl. Math. 94 (2018), 39–70. MR 3739496
  * [7] Joseph E. Bonin and Kevin Long, _The free $m$-cone of a matroid and its $\mathcal{G}$-invariant_, Ann. Comb. 26 (2022), no. 4, 1021–1039. MR 4505053
  * [8] Thomas Brylawski and James Oxley, _The Tutte polynomial and its applications_ , Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 123–225. MR 1165543
  * [9] Tom Brylawski, _Intersection theory for graphs_ , J. Combin. Theory Ser. B 30 (1981), no. 2, 233–246. MR 615318
  * [10] Amanda Cameron, Rodica Dinu, Mateusz Michałek, and Tim Seynnaeve, _Flag matroids: Algebra and geometry_ , Interactions with Lattice Polytopes (Cham) (Alexander M. Kasprzyk and Benjamin Nill, eds.), Springer International Publishing, 2022, pp. 73–114.
  * [11] Henry H. Crapo, _The Tutte polynomial_ , Aequationes Math. 3 (1969), 211–229. MR 262095
  * [12] Harm Derksen, _Symmetric and quasi-symmetric functions associated to polymatroids_ , J. Algebraic Combin. 30 (2009), no. 1, 43–86. MR 2519849
  * [13] Harm Derksen and Alex Fink, _Valuative invariants for polymatroids_ , Adv. Math. 225 (2010), no. 4, 1840–1892. MR 2680193
  * [14] The Sage Developers, _Sage Mathematics Software (Version 8.1)_ , 2020, http://www.sagemath.org.
  * [15] Clément Dupont, Alex Fink, and Luca Moci, _Universal Tutte characters via combinatorial coalgebras_ , Algebr. Comb. 1 (2018), no. 5, 603–651. MR 3887405
  * [16] Ben Elias, Nicholas Proudfoot, and Max Wakefield, _The Kazhdan-Lusztig polynomial of a matroid_ , Adv. Math. 299 (2016), 36–70. MR 3519463
  * [17] J.A. Ellis-Monaghan and I. Moffatt, _Handbook of the Tutte polynomial_ , Chapman and Hall/CRC Monographs and Research Notes in Mathematics Series, C&H/CRC Press, 2022.
  * [18] Christopher Eur, _Divisors on matroids and their volumes_ , J. Combin. Theory Ser. A 169 (2020), 105135, 31. MR 4011081
  * [19] G. E. Farr, _A generalization of the Whitney rank generating function_ , Math. Proc. Cambridge Philos. Soc. 113 (1993), no. 2, 267–280. MR 1198411
  * [20] Graham E. Farr, _Tutte-Whitney polynomials: some history and generalizations_ , Combinatorics, complexity, and chance, Oxford Lecture Ser. Math. Appl., vol. 34, Oxford Univ. Press, Oxford, 2007, pp. 28–52. MR 2314560
  * [21] Luis Ferroni and Benjamin Schröter, _Valuative invariants for large classes of matroids_ , arXiv:2208.04893, 2022.
  * [22] Nicolas Ford, _The expected codimension of a matroid variety_ , J. Algebraic Combin. 41 (2015), no. 1, 29–47. MR 3296243
  * [23] Israel Gelfand, Vladimir Retakh, Shirlei Serconek, and Robert Lee Wilson, _On a class of algebras associated to directed graphs_ , Selecta Mathematica 11 (2005), no. 2, 281.
  * [24] Trygve Johnsen and Hugues Verdure, _Möbius and coboundary polynomials for matroids_ , Des. Codes Cryptogr. 89 (2021), no. 9, 2163–2177. MR 4302190
  * [25] John Johnson and Max Wakefield, _A non-associative incidence near-ring with a generalized Möbius function_ , arXiv:2204.07158, 2022.
  * [26] Relinde Jurrius, _Relations between Möbius and coboundary polynomials_ , Math. Comput. Sci. 6 (2012), no. 2, 109–120. MR 2966347
  * [27] Thomas Krajewski, Iain Moffatt, and Adrian Tanasa, _Hopf algebras and Tutte polynomials_ , Adv. in Appl. Math. 95 (2018), 271–330. MR 3759218
  * [28] Tsuyoshi Miezaki, Manabu Oura, Tadashi Sakuma, and Hidehiro Shinohara, _A generalization of the Tutte polynomials_ , Proc. Japan Acad. Ser. A Math. Sci. 95 (2019), no. 10, 111–113. MR 4038724
  * [29] Peter Orlik and Hiroaki Terao, _Arrangements of hyperplanes_ , Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. MR 1217488
  * [30] James Oxley, _Matroid theory_ , second ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819
  * [31] Ronald C. Read and Earl Glen Whitehead, Jr., _Chromatic polynomials of homeomorphism classes of graphs_ , Discrete Math. 204 (1999), no. 1-3, 337–356. MR 1691877
  * [32] Vladimir Retakh and Robert Lee Wilson, _Algebras associated to acyclic directed graphs_ , Advances in Applied Mathematics 42 (2009), no. 1, 42–59.
  * [33] Jessica Sidman, Will Traves, and Ashley Wheeler, _Geometric equations for matroid varieties_ , J. Combin. Theory Ser. A 178 (2021), Paper No. 105360, 15. MR 4175891
  * [34] Alan D. Sokal, _The multivariate Tutte polynomial (alias Potts model) for graphs and matroids_ , Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge Univ. Press, Cambridge, 2005, pp. 173–226. MR 2187739
  * [35] David E. Speyer, _Tropical linear spaces_ , SIAM J. Discrete Math. 22 (2008), no. 4, 1527–1558. MR 2448909
  * [36] Lorenzo Traldi, _Chain polynomials and Tutte polynomials_ , Discrete Math. 248 (2002), no. 1-3, 279–282. MR 1892704
  * [37] W. T. Tutte, _A contribution to the theory of chromatic polynomials_ , Canad. J. Math. 6 (1954), 80–91. MR 61366
  * [38] Ravi Vakil, _Murphy’s law in algebraic geometry: badly-behaved deformation spaces_ , Invent. Math. 164 (2006), no. 3, 569–590. MR 2227692
  * [39] Hassler Whitney, _The coloring of graphs_ , Ann. of Math. (2) 33 (1932), no. 4, 688–718. MR 1503085
  * [40] Thomas Zaslavsky, _The Möbius function and the characteristic polynomial_ , Combinatorial geometries, Encyclopedia Math. Appl., vol. 29, Cambridge Univ. Press, Cambridge, 1987, pp. 114–138. MR 921071
  * [41] by same author, _Strong Tutte functions of matroids and graphs_ , Trans. Amer. Math. Soc. 334 (1992), no. 1, 317–347. MR 1080738