# A deletion-contraction formula and monotonicity properties for the
polymatroid Tutte polynomial

Xiaxia Guana,b, Xian’an Jina, Tamás Kálmánb,c
aSchool of Mathematical Sciences, Xiamen University, P. R. China
bDepartment of Mathematics, Tokyo Institute of Technology, Japan
cInternational Institute for Sustainability with Knotted Chiral Meta Matter
(WPI-SKCM2), Hiroshima University, Japan
_Email addresses_<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The Tutte polynomial is a crucial invariant of matroids. The polymatroid Tutte
polynomial $\mathscr{T}_{P}(x,y)$, introduced by Bernardi et al., is an
extension of the classical Tutte polynomial from matroids to polymatroids $P$.
In this paper, we first obtain a deletion-contraction formula for
$\mathscr{T}_{P}(x,y)$. Then we prove two coefficientwise natural monotonicity
properties, for containment and for minors of the interior polynomial
$x^{n}\mathscr{T}_{P}(x^{-1},1)$ and the exterior polynomial
$y^{n}\mathscr{T}_{P}(1,y^{-1})$, where $P$ is a polymatroid over $[n]$. We
show by a counter-example that these monotonicity properties do not extend to
$\mathscr{T}_{P}(x,y)$. Using deletion-contraction, we obtain formulas for the
coefficients of terms of degree $n-1$ in $\mathscr{T}_{P}(x,y)$. Finally, for
all $k\geq 0$, we characterize hypergraphs $\mathcal{H}=(V,E)$ so that the
coefficient of $y^{k}$ in the exterior polynomial of the associated
polymatroid $P_{\mathcal{H}}$ attains its maximal value $\binom{|V|+k-2}{k}$.

###### keywords:

Tutte polynomial, Polymatroid, Deletion-contraction formula, Monotonicity.

###### MSC:

05C31, 05B35, 05C65

††journal:

##  1 Introduction

The Tutte polynomial [16] is an important and well-studied topic in graph and
matroid theory, having wide applications in statistical physics, knot theory
and so on. As a generalization of the one-variable evaluations $T_{G}(x,1)$
and $T_{G}(1,y)$ of the Tutte polynomial $T_{G}(x,y)$ of graphs $G$ to
hypergraphs, Kálmán [9] introduced the interior polynomial
$I_{\mathcal{H}}(x)$ and the exterior polynomial $X_{\mathcal{H}}(y)$ for
hypergraphs $\mathcal{H}$ via internal and external activities of hypertrees.
(Hypertrees were first described as ‘left or right degree vectors’ in [13].)
Later, Kálmán, Murakami, and Postnikov [10, 11] established that certain
leading terms of the HOMFLY polynomial [8], which is a generalization of the
celebrated Jones polynomial [8] in knot theory, of any special alternating
link coincide with the common interior polynomial of the pair of hypergraphs
derived from the Seifert graph (which is a bipartite graph) of the link.

Integer polymatroids are a generalization of matroids and an abstraction of
hypergraphs. Throughout this paper, only the set of bases of integer
polymatroids will be considered, and simply called polymatroids. In [1],
Bernardi, Kálmán, and Postnikov proposed the polymatroid Tutte polynomial
$\mathscr{T}_{P}(x,y)$ for polymatroids $P$, which can be reduced to the
classical Tutte polynomial $T_{M}(x,y)$ of any matroid $M$. More precisely, if
$M\subset 2^{[n]}=\\{I|I\subset[n]\\}$ is a matroid of rank $d$ over
$[n]=\\{1,\ldots,n\\}$, and $P=P(M)\subset\\{0,1\\}^{n}\subset\mathbb{Z}^{n}$
is its corresponding polymatroid, then

$T_{M}(x,y)=\frac{(x+y-xy)^{n}}{x^{n-d}y^{d}}\mathscr{T}_{P}\left(\frac{x}{x+y-xy},\frac{y}{x+y-xy}\right).$
(1)

Moreover, for a polymatroid $P$ over $[n]$, the polynomial
$\mathscr{T}_{P}(x,y)$ contains both the interior polynomial $I_{P}(x)$ and
the exterior polynomial $X_{P}(y)$ as special cases in the sense that

$I_{P}(x)=x^{n}\mathscr{T}_{P}(x^{-1},1)\ \ \ \text{and}\ \ \
X_{P}(y)=y^{n}\mathscr{T}_{P}(1,y^{-1}),$ (2)

respectively. It is also known that $\mathscr{T}_{P}(x,y)$ is translation-
invariant and satisfies a duality relation. We remark that
$\mathscr{T}_{P}(x,y)$ is equivalent to another polynomial introduced by
Cameron and Fink [3].

One of the most basic properties of the classical Tutte polynomial is its
deletion-contraction formula. Let $P$ be a polymatroid on $[n]$ and
$f:2^{[n]}\rightarrow\mathbb{Z}$ be its rank function. For any $t\in[n]$, let
$r_{t}=f(\\{t\\})+f([n]\setminus\\{t\\})-f([n])$. In Proposition 4.11 (f) of
[1], Bernardi, Kálmán, and Postnikov obtained a deletion-contraction relation
of $\mathscr{T}_{P}(x,y)$, for the cases $r_{t}=0$ and $r_{t}=1$, that
generalizes the deletion-contraction formula of the classical Tutte
polynomial. They also posed the following question.

######  Question 1.1.

Does there exist a deletion-contraction relation in the case $r_{t}>1$?

We answer this question in the affirmative by proving Theorem 3.5. It is based
on the observation that certain natural “slices” of polymatroids are again
polymatroids. We note that even if a polymatroid is hypergraphical, not all of
its slices will be so. Let us also mention that in [4], the authors introduced
a polynomial invariant similar (but not equivalent) to $\mathscr{T}_{P}$ and
established (in a limited sense) a deletion-contraction relation for it.

In 1972, Brylawski [2] proved that if a matroid $M_{1}$ is a minor of a
connected matroid $M_{2}$, then $T_{M_{1}}(x,y)\leq T_{M_{2}}(x,y)$, that is,
each coefficient of $T_{M_{1}}(x,y)$ is less then or equal to the
corresponding coefficient of $T_{M_{2}}(x,y)$. Unfortunately, we show by a
counter-example in Remark 4.9 that this monotonicity property does not hold
for the polymatroid Tutte polynomial, not even if we make the substitution in
it suggested by (1).

In [15], Stanley showed that if $\Delta$ and $\Delta^{\prime}$ are lattice
polytopes in $\mathbb{R}^{m}$ with $\Delta^{\prime}\subset\Delta$, then
$h^{\ast}_{\Delta^{\prime}}\leq h^{\ast}_{\Delta}$, where $h^{\ast}$ denotes
the $h^{\ast}$-polynomial. In [12], Kato observed, based on results of Kálmán
and Postnikov [11], that the interior polynomial of any connected hypergraph
is equal to the $h^{\ast}$-polynomial of the so-called root polytope of the
associated bipartite graph. The two theorems together imply a natural
monotonicity property of the interior polynomial of hypergraphs, that is, for
two connected hypergraphs $\mathcal{H}=(V,E)$ and
$\mathcal{H}^{\prime}=(V^{\prime},E^{\prime})$, if the associated bipartite
graph $\mathrm{Bip}\mathcal{H}^{\prime}$ of $\mathcal{H}^{\prime}$ is a
subgraph of $\mathrm{Bip}\mathcal{H}$, then $I_{\mathcal{H}^{\prime}}\leq
I_{\mathcal{H}}$.

In this paper, we extend this monotonicity property to the interior polynomial
and the exterior polynomial of arbitrary polymatroids in Theorems 4.2 and 4.7.
Namely, we show that for two polymatroids $P$ and $P^{\prime}$, if
$P^{\prime}\subset P$ or $P^{\prime}$ is a minor of $P$, then
$I_{P^{\prime}}\leq I_{P}$ and $X_{P^{\prime}}\leq X_{P}$. In hypergraphical
cases, we obtain that if the associated bipartite graph of the hypergraph
$\mathcal{H}^{\prime}$ is a subgraph of the associated bipartite graph of the
hypergraph $\mathcal{H}$ (even if $\mathcal{H}$ and $\mathcal{H}^{\prime}$ are
not necessarily connected), then $I_{\mathcal{H}^{\prime}}\leq
I_{\mathcal{H}}$ and $X_{\mathcal{H}^{\prime}}\leq X_{\mathcal{H}}$ (see
Corollary 4.8).

We also examine certain individual coefficients of the polymatroid Tutte
polynomial. Let $P$ be a polymatroid over $[n]$. From Proposition 4.11 (d) of
[1], one knows that for any $k\in[n]\cup\\{0\\}$,

$x^{k}y^{n-k}[\mathscr{T}_{P}(x,y)]=\binom{n}{k}.$

In other words, the top degree terms of $\mathscr{T}_{P}$ form a standard
binomial expansion. Let $f$ be the rank function of the polymatroid $P$. In
[6], the authors computed the coefficients
$x^{n-1}[\mathscr{T}_{P}(x,1)]=\sum_{i\in[n]}f(\\{i\\})-f([n])$ and
$y^{n-1}[\mathscr{T}_{P}(1,y)]=\sum_{i\in[n]}f([n]\setminus\\{i\\})-(n-1)f([n])$.
From there it is easy to get formulas for the coefficients
$x^{n-1}[\mathscr{T}_{P}(x,y)]$ and $y^{n-1}[\mathscr{T}_{P}(x,y)]$. As a
generalization, using our deletion-contraction relation of
$\mathscr{T}_{P}(x,y)$, we obtain

$x^{n-k}y^{k-1}[\mathscr{T}_{P}(x,y)]=\sum_{\stackrel{{\scriptstyle
S\subset[n]}}{{|S|=k-1}}}f(S)+\sum_{\stackrel{{\scriptstyle
S^{\prime}\subset[n]}}{{|S^{\prime}|=k}}}f(S^{\prime})-\binom{n}{k-1}f([n])-k\binom{n}{k}$

for any $k\in[n]$ in Theorem 5.3. Likewise, formulas for the coefficients
$x^{n-2}[\mathscr{T}_{P}(x,y)]$ and $y^{n-2}[\mathscr{T}_{P}(x,y)]$ can be
obtained as well (see Theorem 5.4). They imply formulas for the coefficients
$x^{n-2}[\mathscr{T}_{P}(x,1)]$ and $y^{n-2}[\mathscr{T}_{P}(1,y)]$ (see
Corollary 5.5).

Connectivity plays a critical role in graphs and hypergraphs. In Theorem 5.9
of this paper, using our deletion-contraction formula and monotonicity
property of the exterior polynomial, we prove that for all $k\geq 0$ and for
any bipartite graph $G=(E\cup V,\mathcal{E})$, the subgraph $G-E^{\prime}$ is
connected for all $E^{\prime}\subset E$ with $|E^{\prime}|=k$, if and only if
$y^{i}[X_{\mathcal{H}}(y)]=\binom{|V|+i-2}{i}$ for any $i\leq k$, where
$\mathcal{H}$ is the hypergraph induced by $G$ so that $E$ is the set of
hyperedges. We remark that the coefficient $y^{i}[X_{\mathcal{H}}(y)]$ can
never be higher than $\binom{|V|+i-2}{i}$.

The paper is organized as follows. In Section 2, we make some necessary
preparations. Section 3 is devoted to the deletion-contraction relation of the
polymatroid Tutte polynomial. Our monotonicity properties of the interior
polynomial and the exterior polynomial for polymatroids are proven in Section
4. In Section 5, we apply the deletion-contraction formula of Section 3 to
derive formulas for the coefficients $x^{n-k}y^{k-1}[\mathscr{T}_{P}(x,y)]$
for any $k\in[n]$, $x^{n-2}[\mathscr{T}_{P}(x,y)]$, and
$y^{n-2}[\mathscr{T}_{P}(x,y)]$ for polymatroids $P$ and to characterize the
connectivity of hypergraphs using the exterior polynomial.

##  2 Preliminaries

In this section, we will give some definitions and summarize some known
results used in the next sections. Throughout the paper, let
$[n]=\\{1,2,\ldots,n\\}$, $2^{[n]}=\\{I|I\subset[n]\\}$, and let
$\textbf{e}_{1},\textbf{e}_{2},\ldots,\textbf{e}_{n}$ denote the canonical
basis of $\mathbb{R}^{n}$. We first recall the definition of polymatroids.

######  Definition 2.1.

A _polymatroid_ $P=P_{f}\subset\mathbb{Z}^{n}$ (in other words, over the
ground set $[n]$) with the rank function $f$ is given as

$P=\left\\{(a_{1},\cdots,a_{n})\in\mathbb{Z}^{n}\bigg{|}\sum_{i\in I}a_{i}\leq
f(I)\ \text{for any}\ I\subset[n]\ \text{and}\
\sum_{i\in[n]}a_{i}=f([n])\right\\},$

where $f:2^{[n]}\rightarrow\mathbb{Z}$ satisfies

  1. (i)

$f(\emptyset)=0$;

  2. (ii)

$f(I)+f(J)\geq f(I\cup J)+f(I\cap J)$ for any $I,J\subset[n]$ (submodularity).

Polymatroids are non-empty. It is also easy to see that the base polytope of
any matroid (more precisely, the set of its vertices) is a polymatroid. We
remark that in other papers on the subject, cf. [5], polymatroids are often
defined as slightly larger sets, and the set $P$ of Definition 2.1 is referred
to as the set of integer bases of a polymatroid.

Conversely, if $P$ is a polymatroid on $[n]$, then its rank function
$f=f_{P}\colon 2^{[n]}\rightarrow\mathbb{Z}$ can be recovered as

$f_{P}(I)=\max_{\textbf{a}\in P}\sum_{i\in I}a_{i},\ \text{for any subset}\
I\subset[n].$ (3)

We refer the readers to [5] and chapter 44 of [14] for more details.

A _hypergraph_ is a pair $\mathcal{H}=(V,E)$, where $V$ is a finite set and
$E$ is a finite multiset of non-empty subsets of $V$. Elements of $V$ are
called _vertices_ and elements of $E$ are called _hyperedges_ , respectively,
of the hypergraph. For a hypergraph $\mathcal{H}=(V,E)$, its _associated
bipartite graph_ $\mathrm{Bip}\mathcal{H}$ is defined as follows. The sets $V$
and $E$ are the color classes of $\mathrm{Bip}\mathcal{H}$, and an element $v$
of $V$ is connected to an element $e$ of $E$ in $\mathrm{Bip}\mathcal{H}$ if
and only if $v\in e$. For a subset $E^{\prime}\subset E$, let
$\mathrm{Bip}\mathcal{H}|_{E^{\prime}}$ denote the bipartite graph formed by
$E^{\prime}$, all edges of $\mathrm{Bip}\mathcal{H}$ incident with elements of
$E^{\prime}$, and their endpoints in $V$. Define $\mu(E^{\prime})=0$ for
$E^{\prime}=\emptyset$, and $\mu(E^{\prime})=|\bigcup
E^{\prime}|-c(E^{\prime})$ for $E^{\prime}\neq\emptyset$, where $\bigcup
E^{\prime}=V\cap(\mathrm{Bip}\mathcal{H}|_{E^{\prime}})$ and $c(E^{\prime})$
is the number of connected components of
$\mathrm{Bip}\mathcal{H}|_{E^{\prime}}$. Kálmán [9] proved that $\mu$ is
submodular. In that sense, polymatroids are an abstraction of hypergraphs. The
elements of the polymatroid induced by $\mu$ (in the sense of Definition 2.1)
will be referred to as hypertrees because they are essentially degree
distribution of spanning forests of $\mathrm{Bip}\mathcal{H}$, cf. [9]. A
polymatroid is called a _hypergraphical polymatroid_ , denoted by
$P_{\mathcal{H}}$, if it is the set of all hypertrees of some hypergraph
$\mathcal{H}$.

A nonempty finite subset $B\subset\mathbb{Z}^{n}$ is a polymatroid on $[n]$ if
and only if $B$ satisfies the following two conditions [7].

  1. (1)

For any $(a_{1},a_{2},\cdots,a_{n})\in B$ and $(b_{1},b_{2},\cdots,b_{n})\in
B$, we have $\sum_{i\in[n]}a_{i}=\sum_{i\in[n]}b_{i}$.

  2. (2)

For any $\textbf{a}=(a_{1},a_{2},\cdots,a_{n})\in B$,
$\textbf{b}=(b_{1},b_{2},\cdots,b_{n})\in B$, and any $i\in[n]$ with
$a_{i}>b_{i}$, there exists some $j\in[n]$ such that $a_{j}<b_{j}$ and
$\textbf{a}+\textbf{e}_{j}-\textbf{e}_{i}\in B$, as well as
$\textbf{b}+\textbf{e}_{i}-\textbf{e}_{j}\in B$.

Condition (2) is called the _Exchange Axiom_. This description easily implies
that adding the same vector of $\mathbb{Z}^{n}$ to each element of a
polymatroid yields another polymatroid.

We next recall (internal and external) activity of a basis of a polymatroid.
Note that the following definition relies on the natural order of the set
$[n]$.

######  Definition 2.2.

Let $P$ be a polymatroid over $[n]$. For a basis $\textbf{a}\in P$, an index
$i\in[n]$ is _internally active_ if
$\textbf{a}-\textbf{e}_{i}+\textbf{e}_{j}\notin P$ for any $j<i$. Let
$\mathrm{Int}(\textbf{a})=\mathrm{Int}_{P}(\textbf{a})\subset[n]$ denote the
set of all internally active indices with respect to a. Furthermore, let
$\iota(\textbf{a})=|\mathrm{Int}(\textbf{a})|$ and
$\overline{\iota}(\textbf{a})=n-|\mathrm{Int}(\textbf{a})|$.

For a basis $\textbf{a}\in P$, we call $i\in[n]$ _externally active_ if
$\textbf{a}+\textbf{e}_{i}-\textbf{e}_{j}\notin P$ for any $j<i$. Let
$\mathrm{Ext}(\textbf{a})=\mathrm{Ext}_{P}(\textbf{a})\subset[n]$ denote the
set of all externally active indices with respect to a, and let
$\epsilon(\textbf{a})=|\mathrm{Ext}(\textbf{a})|$ and
$\overline{\epsilon}(\textbf{a})=n-|\mathrm{Ext}(\textbf{a})|$.

Let $P$ be a polymatroid over $[n]$ and $f$ be its rank function. For a basis
$\textbf{a}=(a_{1},a_{2},\cdots,a_{n})\in P$, let

$\mathcal{I}(\textbf{a}):=\mathcal{I}_{P}(\textbf{a})=\left\\{I\subset[n]\bigg{|}\sum_{i\in
I}a_{i}=f(I)\right\\}.$

We call this the set of _tight_ sets for a.

The next result holds due to [14, Theorem 44.2], since $f$ is submodular.

######  Theorem 2.3.

[14] Let $P$ be a polymatroid. For any basis $\textbf{a}\in P$, if
$I,J\in\mathcal{I}(\textbf{a})$, then $I\cup J,I\cap
J\in\mathcal{I}(\textbf{a})$.

We now state a conclusion obtained in Lemma 4.2 in [1].

######  Theorem 2.4.

[1] Let $P$ be a polymatroid over $[n]$. For any $\textbf{a}\in P$,

  * (1)

an index $i\in[n]$ is internally active with respect to a if and only if there
exists a subset $I\subset[n]$ such that $i=\min(I)$ and $[n]\setminus
I\in\mathcal{I}(\textbf{a})$;

  * (2)

an index $i\in[n]$ is externally active with respect to a if and only if there
exists a subset $I^{\prime}\subset[n]$ such that $i=\min(I^{\prime})$ and
$I^{\prime}\in\mathcal{I}(\textbf{a})$.

To close this section, we will recall the polymatroid Tutte polynomial.

######  Definition 2.5.

[1] Let $P$ be a polymatroid over $[n]$. The _polymatroid Tutte polynomial_
$\mathscr{T}_{P}(x,y)$ is defined as

$\mathscr{T}_{P}(x,y):=\sum_{\textbf{a}\in
P}x^{oi(\textbf{a})}y^{oe(\textbf{a})}(x+y-1)^{ie(\textbf{a})},$

where

$oi(\textbf{a}):=|\mathrm{Int}(\textbf{a})\setminus\mathrm{Ext}(\textbf{a})|,$
$oe(\textbf{a}):=|\mathrm{Ext}(\textbf{a})\setminus\mathrm{Int}(\textbf{a})|,$
$ie(\textbf{a}):=|\mathrm{Int}(\textbf{a})\cap\mathrm{Ext}(\textbf{a})|.$

Note that the smallest index $i=1$ must be simultaneously internally and
externally active for any basis of any polymatroid. Thus the polynomial
$\mathscr{T}_{P}(x,y)$ is always divisible by $x+y-1$.

For a polymatroid $P$ over $[n]$, Kálmán [9] defined _the interior polynomial_

$I_{P}(x):=\sum_{\textbf{a}\in P}x^{\overline{\iota}(\textbf{a})}$

and _the exterior polynomial_

$X_{P}(y):=\sum_{\textbf{a}\in P}y^{\overline{\epsilon}(\textbf{a})}.$

It is easy to verify that if $P$ is a polymatroid over $[n]$, then we have
$I_{P}(x)=x^{n}\mathscr{T}_{P}(x^{-1},1)$ and
$X_{P}(y)=y^{n}\mathscr{T}_{P}(1,y^{-1})$. Moreover, the coefficients of
$I_{P}$ and $X_{P}$ are non-negative integers.

Let $P$ be a polymatroid over $[n]$. Let the symmetric group $S_{n}$ act on
$\mathbb{Z}^{n}$ by permutations of coordinates. I.e., for a permutation $w\in
S_{n}$ and a point $\textbf{a}=(a_{1},\ldots,a_{n})\in\mathbb{Z}^{n}$, define
$w(\textbf{a}):=(a_{w(1)},\ldots,a_{w(n)})$, and

$w(P):=\\{w(\textbf{a})|\textbf{a}\in P\\}.$

For any $\textbf{c}=(c_{1},\ldots,c_{n})\in\mathbb{Z}^{n}$, let

$P+\textbf{c}:=\\{(a_{1}+c_{1},\ldots,a_{n}+c_{n})|(a_{1},\ldots,a_{n})\in
P\\}.$

The _dual_ polymatroid of a polymatroid $P$ is denoted by $-P$, where

$-P:=\\{(-a_{1},\ldots,-a_{n})|(a_{1},\ldots,a_{n})\in P\\}.$

The following invariance properties of the polymatroid Tutte polynomial have
been proved in [1].

######  Theorem 2.6.

[1] Let $P$ be a polymatroid on $[n]$ and let $-P$ be the dual polymatroid of
$P$. Then

  * (1)

$\mathscr{T}_{P}(x,y)=\mathscr{T}_{P+\textbf{c}}(x,y)$ for any
$\textbf{c}\in\mathbb{Z}^{n}$ (translation invariance);

  * (2)

$\mathscr{T}_{P}(x,y)=\mathscr{T}_{w(P)}(x,y)$ for any $w\in S_{n}$
($S_{n}$-invariance);

  * (3)

$\mathscr{T}_{P}(x,y)=\mathscr{T}_{-P}(y,x)$ (duality).

Regarding Theorem 2.6 (2), we note again that the order $1<2<\ldots<n$ plays
an implicit role in Definition 2.5, but it does turn out that
$\mathscr{T}_{P}$ depends only on $P$ and not on this order. In particular,
$I_{P}$ and $X_{P}$ also depend only on $P$, that is, they also satisfy
$S_{n}$-invariance. Moreover, for $I_{P}$ and $X_{P}$, duality takes the form

$I_{-P}=X_{P}\ \text{and}\ I_{P}=X_{-P}.$ (4)

By the definition of the dual polymatroid, it is clear that for any
polymatroid $P$, we have that

$-(-P)=P.$ (5)

Hence, $I_{-P}=X_{P}$ is equivalent to $I_{P}=X_{-P}$.

##  3 A deletion-contraction formula

In this section, we will study a deletion-contraction formula of the
polymatroid Tutte polynomial which answers Question 1.1.

Let $P$ be a polymatroid on $[n]$ and $f$ be its rank function. For
convenience, for any $t\in[n]$, let
$\alpha_{t}=f([n])-f([n]\setminus\\{t\\})$, $\beta_{t}=f(\\{t\\})$ and
$T_{t}=\\{\alpha_{t},\alpha_{t}+1,\ldots,\beta_{t}\\}$. For any $j\in T_{t}$,
define

$P^{t}_{j}:=\\{(a_{1},\ldots,a_{n})\in P\mid a_{t}=j\\}$

and its projection

$\widehat{P}^{t}_{j}:=\\{(a_{1},\ldots,a_{t-1},a_{t+1},\ldots,a_{n})\in\mathbb{Z}^{n-1}\mid(a_{1},\ldots,a_{n})\in
P^{t}_{j}\\}.$ (6)

Here the range $T_{t}$ is chosen so that $P^{t}_{j}$ and $\widehat{P}^{t}_{j}$
are nonempty if and only if $j\in T_{t}$. By the Exchange Axiom, $P^{t}_{j}$
and $\widehat{P}^{t}_{j}$ are polymatroids on $[n]$ and on
$[n]\setminus\\{t\\}$, respectively. We next study the relation between the
rank function of $P$ and the rank function of the polymatroid $P^{t}_{j}$. We
first state a result due to Kálmán.

######  Lemma 3.1 ([9]).

Let $P$ be a polymatroid on $[n]$. For any basis $\textbf{a}\in P$ and any
subset $I\subset[n]$, if $I\notin\mathcal{I}(\textbf{a})$, then there are
$j\in I$ and $k\in[n]\setminus I$ so that
$\textbf{a}-\textbf{e}_{k}+\textbf{e}_{j}\in P$.

######  Proposition 3.2.

Let $P$ be a polymatroid on $[n]$ and $f$ be its rank function. For some
$t\in[n]$, let $\alpha_{t}$, $\beta_{t}$, $T_{t}$ and $\widehat{P}^{t}_{j}$ be
defined as above. Let $f^{t}_{j}$ be the rank function of the polymatroid
$\widehat{P}^{t}_{j}$. Then for any subset $I\subset[n]\setminus\\{t\\}$, we
have $f^{t}_{j}(I)=\min\\{f(I),f(I\cup\\{t\\})-j\\}$. In particular,
$f^{t}_{\alpha_{t}}(I)=f(I)$ and
$f^{t}_{\beta_{t}}(I)=f(I\cup\\{t\\})-f(\\{t\\})$.

###### Proof.

For any $(a_{1},\ldots,a_{n})\in P$, we know that $\sum_{i\in I}a_{i}\leq
f(I)$ and $\sum_{i\in I}a_{i}+a_{t}\leq f(I\cup\\{t\\})$. Then for any $j\in
T_{t}$, we have that $f^{t}_{j}(I)\leq\min\\{f(I),f(I\cup\\{t\\})-j\\}$ as
$a_{t}=j$.

We now show that there is a basis $\textbf{c}=(c_{1},\ldots,c_{n})\in
P^{t}_{j}$ so that $\sum_{i\in I}c_{i}=\min\\{f(I),f(I\cup\\{t\\})-j\\}$. Let
$\textbf{b}=(b_{1},\ldots,b_{n})\in P$ be a basis of $P$ satisfying
$\sum_{i\in I}b_{i}=f(I)$ and $\sum_{i\in I}b_{i}+b_{t}=f(I\cup\\{t\\})$.
(Such a basis must exist, for example, it can be taken as the
lexicographically maximal basis of $P$ with respect to some order in which $I$
forms the first $|I|$ elements of $[n]$ and $t$ is the $(|I|+1)$’st.)

  1. (i)

Assume that $f(I)=f(I\cup\\{t\\})-j$. Then the basis b belongs to $P^{t}_{j}$
and satisfies the required property.

  2. (ii)

Assume that $f(I)<f(I\cup\\{t\\})-j$. Then $j<f(I\cup\\{t\\})-f(I)=b_{t}$.
Note that $j\geq\alpha_{t}=f([n])-f([n]\setminus\\{t\\})$. By Lemma 3.1, we
have that for any $\textbf{d}\in P$ satisfying $d_{t}>j$, there is
$k\in[n]\setminus\\{t\\}$ so that $\textbf{d}-\textbf{e}_{t}+\textbf{e}_{k}\in
P$ as $[n]\setminus\\{t\\}\notin\mathcal{I}(\textbf{d})$. This implies that
for any $m\in[1,b_{t}-j]$, there is $k_{m}\in[n]\setminus\\{t\\}$ so that
$\textbf{b}^{m+1}=\textbf{b}^{m}-\textbf{e}_{t}+\textbf{e}_{k_{m}}\in P$,
where $\textbf{b}^{1}=\textbf{b}$. Note also that $k_{m}\notin I$ as
$I\in\mathcal{I}(\textbf{b}^{m})$ for all $m$. Hence, the basis
$\textbf{c}=\textbf{b}^{b_{t}-j+1}$ satisfies the required property.

  3. (iii)

Assume that $f(I)>f(I\cup\\{t\\})-j$. Similar to (ii), by Lemma 3.1, for any
$m\in[1,j-b_{t}]$, there is $k^{\prime}_{m}\in[n]\setminus\\{t\\}$ so that
$\textbf{c}^{m+1}=\textbf{c}^{m}+\textbf{e}_{t}-\textbf{e}_{k^{\prime}_{m}}\in
P$ since $\\{t\\}\notin\mathcal{I}(\textbf{c}^{m})$, where
$\textbf{c}^{1}=\textbf{b}$. We know that
$k^{\prime}_{m}\notin[n]\setminus(I\cup\\{t\\})$ as
$I\cup\\{t\\}\in\mathcal{I}(\textbf{c}^{m})$, that is, $k^{\prime}_{m}\in I$
for all $m$. This implies the basis $\textbf{c}=\textbf{c}^{j-b_{t}+1}$
satisfies the required property.

The before first claim holds.

By the submodularity of $f$, for any subset $I\subset[n]\setminus\\{t\\}$, we
have

$f(I\cup\\{t\\})+f([n]\setminus\\{t\\})\geq f([n])+f(I)$

and

$f(\\{t\\})+f(I)\geq f(I\cup\\{t\\}),$

whereby the second claim also holds. ∎

######  Definition 3.3.

Let $P$ be a polymatroid on $[n]$ with rank function $f$. For a subset
$A\subset[n]$, the _deletion_ $P\setminus A$ and _contraction_ $P/A$, which
are polymatroids on $[n]\setminus A$, are given by the rank functions
$f_{P\setminus A}(T)=f(T)$ and $f_{P/A}(T)=f(T\cup A)-f(A)$, for any subset
$T\subset[n]\setminus A$, respectively.

Hence, Proposition 3.2 implies that

$\displaystyle\widehat{P}^{t}_{\alpha_{t}}=P\setminus\\{t\\}\ \text{and}\
\widehat{P}^{t}_{\beta_{t}}=P/\\{t\\}.$ (7)

The following conclusion is given in Proposition 4.11 (f) of [1].

######  Theorem 3.4.

[1] Let $P$ be a polymatroid on $[n]$. For some $t\in[n]$, let $\alpha_{t}$,
$\beta_{t}$, and $\widehat{P}^{t}_{j}$ be defined as above.

  1. (1)

If $\beta_{t}-\alpha_{t}=0$, then

$\mathscr{T}_{P}(x,y)=(x+y-1)\mathscr{T}_{\widehat{P}^{t}_{\alpha_{t}}}(x,y)=(x+y-1)\mathscr{T}_{\widehat{P}^{t}_{\beta_{t}}}(x,y).$

  2. (2)

If $\beta_{t}-\alpha_{t}=1$, then

$\mathscr{T}_{P}(x,y)=x\mathscr{T}_{\widehat{P}^{t}_{\alpha_{t}}}(x,y)+y\mathscr{T}_{\widehat{P}^{t}_{\beta_{t}}}(x,y).$

In fact, this relation generalizes the deletion-contraction formula of the
classical Tutte polynomial. In other words, if $M\subset 2^{[n]}$ is a matroid
of rank $d$, and $P=P(M)\subset\\{0,1\\}^{n}$ is its corresponding
polymatroid, then Theorem 3.4 is consistent with the deletion-contraction
formula of $T_{M}(x,y)$. Theorem 3.4 (1) and the earlier relation (2) imply
that

$\displaystyle I_{\widehat{P}^{t}_{j}}=I_{P^{t}_{j}}\ \text{and}\
X_{\widehat{P}^{t}_{j}}=X_{P^{t}_{j}}\ \text{for any}\ j\in T_{t}.$ (8)

That is, when we consider essentially the same $P$ as a polymatroid over a
ground set with an extra element, $\mathscr{T}_{P}$ changes but $I_{P}$ and
$X_{P}$ do not change. We now present a deletion-contraction formula for the
case $\beta_{t}-\alpha_{t}>0$ which generalizes Theorem 3.4 (2).

######  Theorem 3.5.

Let $P$ be a polymatroid on $[n]$. For some $t\in[n]$, let $\alpha_{t}$,
$\beta_{t}$, $T_{t}$ and $\widehat{P}^{t}_{j}$ be given by the above
definitions. If $\beta_{t}-\alpha_{t}>0$, then

$\mathscr{T}_{P}(x,y)=x\mathscr{T}_{\widehat{P}^{t}_{\alpha_{t}}}(x,y)+y\mathscr{T}_{\widehat{P}^{t}_{\beta_{t}}}(x,y)+\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}\mathscr{T}_{\widehat{P}^{t}_{j}}(x,y).$

###### Proof.

By the $S_{n}$-invariance of $\mathscr{T}_{P}(x,y)$, we may let $t=n$. Then we
have the following two claims.

Claim 1. If $\beta_{t}-\alpha_{t}>0$, then

  1. (i)

$t\in\mathrm{Int}_{P}(\textbf{a})\setminus\mathrm{Ext}_{P}(\textbf{a})$ for
any $\textbf{a}\in P^{t}_{\alpha_{t}}$;

  2. (ii)

$t\in\mathrm{Ext}_{P}(\textbf{a})\setminus\mathrm{Int}_{P}(\textbf{a})$ for
any $\textbf{a}\in P^{t}_{\beta_{t}}$;

  3. (iii)

$t\in[n]\setminus(\mathrm{Ext}_{P}(\textbf{a})\cup\mathrm{Int}_{P}(\textbf{a}))$
for any $\textbf{a}\in P^{t}_{j}$, where $j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}$;

  4. (iv)

$t\in\mathrm{Ext}_{P^{t}_{j}}(\textbf{a})\cap\mathrm{Int}_{P^{t}_{j}}(\textbf{a})$
for any $\textbf{a}\in P^{t}_{j}$, where $j\in T_{t}$.

_Proof of Claim 1._ For any $\textbf{a}\in P^{t}_{\alpha_{t}}$, we have that
$[n]\setminus\\{t\\}\in\mathcal{I}_{P}(\textbf{a})$ by the definition of
$P^{t}_{\alpha_{t}}$. Then $t\in\mathrm{Int}_{P}(\textbf{a})$ by Theorem 2.4
(1). If $\textbf{a}\in P^{t}_{\beta_{t}}$, then
$t\in\mathrm{Ext}_{P}(\textbf{a})$ by Theorem 2.4 (2) as
$\\{t\\}\in\mathcal{I}_{P}(\textbf{a})$. It is clear that for any $j\in
T_{t}$, we have that
$t\in\mathrm{Int}_{P^{t}_{j}}(\textbf{a})\cap\mathrm{Ext}_{P^{t}_{j}}(\textbf{a})$
for any $\textbf{a}\in P^{t}_{j}$, since $a_{t}=j$, that is,
$[n]\setminus\\{t\\}\in\mathcal{I}_{P^{t}_{j}}(\textbf{a})$ and
$\\{t\\}\in\mathcal{I}_{P^{t}_{j}}(\textbf{a})$. The other results are true by
the Exchange Axiom.

Claim 2. For any $j\in T_{t}$, let $\textbf{a}\in P^{t}_{j}$ be a basis of the
polymatroid $P^{t}_{j}$. Then for any $k\in[n]\setminus\\{t\\}$, we have that
$k\in\mathrm{Int}_{P}(\textbf{a})$ if and only if
$k\in\mathrm{Int}_{P^{t}_{j}}(\textbf{a})$, and
$k\in\mathrm{Ext}_{P}(\textbf{a})$ if and only if
$k\in\mathrm{Ext}_{P^{t}_{j}}(\textbf{a})$.

_Proof of Claim 2._ It is easy to see that
$\mathrm{Int}_{P}(\textbf{a})\subset\mathrm{Int}_{P^{t}_{j}}(\textbf{a})$ and
$\mathrm{Ext}_{P}(\textbf{a})\subset\mathrm{Ext}_{P^{t}_{j}}(\textbf{a})$ as
$P^{t}_{j}\subset P$.

If $k\notin\mathrm{Int}_{P}(\textbf{a})$, then there is $k^{\prime}<k$ so that
$\textbf{b}=\textbf{a}-\textbf{e}_{k}+\textbf{e}_{k^{\prime}}\in P$. Note that
$b_{t}=a_{t}=j$, that is, $\textbf{b}\in P^{t}_{j}$. It implies that
$k\notin\mathrm{Int}_{P^{t}_{j}}(\textbf{a})$. Similarly, if
$k\notin\mathrm{Ext}_{P}(\textbf{a})$, then there is $k^{\prime\prime}<k$ so
that $\textbf{c}=\textbf{a}+\textbf{e}_{k}-\textbf{e}_{k^{\prime\prime}}\in
P$. Hence, $k\notin\mathrm{Ext}_{P^{t}_{j}}(\textbf{a})$ because
$\textbf{c}\in P^{t}_{j}$. Thus, the claim holds.

We know that for any basis $\textbf{a}\in P$, there is an integer $j\in T_{t}$
so that $\textbf{a}\in P^{t}_{j}$. Then by Claims 1 and 2,

$\displaystyle\mathscr{T}_{P}(x,y)$ $\displaystyle=$
$\displaystyle\sum_{\textbf{a}\in
P}x^{oi_{P}(\textbf{a})}y^{oe_{P}(\textbf{a})}(x+y-1)^{ie_{P}(\textbf{a})}$
$\displaystyle=$ $\displaystyle\sum_{\textbf{a}\in
P^{t}_{\alpha_{t}}}x^{oi_{P}(\textbf{a})}y^{oe_{P}(\textbf{a})}(x+y-1)^{ie_{P}(\textbf{a})}+\sum_{\textbf{a}\in
P^{t}_{\beta_{t}}}x^{oi_{P}(\textbf{a})}y^{oe_{P}(\textbf{a})}(x+y-1)^{ie_{P}(\textbf{a})}$
$\displaystyle+\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}\left[\sum_{\textbf{a}\in
P^{t}_{j}}x^{oi_{P}(\textbf{a})}y^{oe_{P}(\textbf{a})}(x+y-1)^{ie_{P}(\textbf{a})}\right]$
$\displaystyle=$ $\displaystyle\sum_{\textbf{a}\in
P^{t}_{\alpha_{t}}}x^{oi_{P^{t}_{\alpha_{t}}}(\textbf{a})+1}y^{oe_{P^{t}_{\alpha_{t}}}(\textbf{a})}(x+y-1)^{ie_{P^{t}_{\alpha_{t}}}(\textbf{a})-1}$
$\displaystyle+\sum_{\textbf{a}\in
P^{t}_{\beta_{t}}}x^{oi_{P^{t}_{\beta_{t}}}(\textbf{a})}y^{oe_{P^{t}_{\beta_{t}}}(\textbf{a})+1}(x+y-1)^{ie_{P^{t}_{\beta_{t}}}(\textbf{a})-1}$
$\displaystyle+\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}\left[\sum_{\textbf{a}\in
P^{t}_{j}}x^{oi_{P^{t}_{j}}(\textbf{a})}y^{oe_{P^{t}_{j}}(\textbf{a})}(x+y-1)^{ie_{P^{t}_{j}}(\textbf{a})-1}\right]$
$\displaystyle=$
$\displaystyle(x+y-1)^{-1}\left[x\mathscr{T}_{P^{t}_{\alpha_{t}}}(x,y)+y\mathscr{T}_{P^{t}_{\beta_{t}}}(x,y)+\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}\mathscr{T}_{P^{t}_{j}}(x,y)\right].$

Hence,
$\mathscr{T}_{P}(x,y)=x\mathscr{T}_{\widehat{P}^{t}_{\alpha_{t}}}(x,y)+y\mathscr{T}_{\widehat{P}^{t}_{\beta_{t}}}(x,y)+\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}\mathscr{T}_{\widehat{P}^{t}_{j}}(x,y)$
since
$\mathscr{T}_{\widehat{P}^{t}_{j}}(x,y)=(x+y-1)^{-1}\mathscr{T}_{P^{t}_{j}}(x,y)$
for any $j\in T_{t}$ by Theorem 3.4 (1). ∎

Note that if $P$ is a hypergraphical polymatroid, then both
$\widehat{P}^{t}_{\alpha_{t}}$ and $\widehat{P}^{t}_{\beta_{t}}$ are
hypergraphical. However, $\widehat{P}^{t}_{j}$ is not necessarily
hypergraphical for $j\in T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}$.

A deletion-contraction formula of interior and exterior polynomials of
polymatroids can be obtained from Theorems 3.4 (1) and 3.5.

######  Corollary 3.6.

Let $P$ be a polymatroid on $[n]$. For some $t\in[n]$, let $\alpha_{t}$,
$\beta_{t}$, $T_{t}$ and $\widehat{P}^{t}_{j}$ be defined as above. Then

$I_{P}(x)=I_{\widehat{P}^{t}_{\alpha_{t}}}(x)+x\sum_{j\in
T_{t}\setminus\\{\alpha_{t}\\}}I_{\widehat{P}^{t}_{j}}(x)$

and

$X_{P}(y)=X_{\widehat{P}^{t}_{\beta_{t}}}(y)+y\sum_{j\in
T_{t}\setminus\\{\beta_{t}\\}}X_{\widehat{P}^{t}_{j}}(y).$

###### Proof.

We first consider the statement of the interior polynomial. If
$\beta_{t}-\alpha_{t}=0$, then as $T_{t}\setminus\\{\alpha_{t}\\}=\emptyset$,
the conclusion is true by Theorem 3.4 (1) and the fact that
$I_{P}(x)=x^{n}\mathscr{T}_{P}(x^{-1},1)$.

If $\beta_{t}-\alpha_{t}>0$, by Theorem 3.5, we have

$\displaystyle I_{P}(x)$ $\displaystyle=$ $\displaystyle
x^{n}\mathscr{T}_{P}(x^{-1},1)$ $\displaystyle=$ $\displaystyle
x^{n}(x^{-1}\mathscr{T}_{\widehat{P}^{t}_{\alpha_{t}}}(x^{-1},1)+\sum_{j\in
T_{t}\setminus\\{\alpha_{t}\\}}\mathscr{T}_{\widehat{P}^{t}_{j}}(x^{-1},1))$
$\displaystyle=$ $\displaystyle
x^{n-1}\mathscr{T}_{\widehat{P}^{t}_{\alpha_{t}}}(x^{-1},1)+x^{n}\sum_{j\in
T_{t}\setminus\\{\alpha_{t}\\}}\mathscr{T}_{\widehat{P}^{t}_{j}}(x^{-1},1)$
$\displaystyle=$ $\displaystyle
I_{\widehat{P}^{t}_{\alpha_{t}}}(x)+x\sum_{j\in
T_{t}\setminus\\{\alpha_{t}\\}}I_{\widehat{P}^{t}_{j}}(x).$

Similarly, the statement regarding the exterior polynomial also holds by
$X_{P}(y)=y^{n}\mathscr{T}_{P}(1,y^{-1})$, Theorems 3.4 (1) and 3.5. ∎

##  4 Monotonicity properties

In this section, we prove two monotonicity properties of interior and exterior
polynomials of polymatroids. For two polynomials $g_{1}$ and $g_{2}$, we say
$g_{1}\leq g_{2}$ if each coefficient of $g_{1}$ is less than or equal to the
corresponding coefficient of $g_{2}$.

We first consider the case when there is an inclusion of the two polymatroids.
We start with a result from [6].

######  Lemma 4.1 ([6]).

Let $P$ be a polymatroid on $[n]$ and $f$ be its rank function. Then the
coefficients of the terms of degree $n-1$ for $\mathscr{T}_{P}(x,1)$ and
$\mathscr{T}_{P}(1,y)$ are $\sum_{i\in[n]}f(\\{i\\})-f([n])$ and
$\sum_{i\in[n]}f([n]\setminus\\{i\\})-(n-1)f([n])$, respectively.

Then our first main claim is as follows.

######  Theorem 4.2.

Let $P$ and $P^{\prime}$ be two polymatroids on the same ground set $[n]$. If
$P^{\prime}\subset P$, then $I_{P^{\prime}}\leq I_{P}$ and $X_{P^{\prime}}\leq
X_{P}$.

###### Proof.

It is enough to prove the statement for the exterior polynomial because of (4)
and because $P^{\prime}\subset P$ implies $-P^{\prime}\subset-P$. We now prove
the claim by induction on $n$.

Let $f$ and $f^{\prime}$ be the rank functions of $P$ and $P^{\prime}$,
respectively. Then $f^{\prime}([n])=f([n])$ and by (3) we also have
$f^{\prime}(I)\leq f(I)$ for all $I\subset[n]$ as $P^{\prime}\subset P$. Note
that the constant term of the exterior polynomial of any polymatroid is 1.
Then the statement is clear in the cases $n=1$ and $n=2$ by Lemma 4.1. Assume
that the conclusion holds for $n\leq m-1$. Then for $n=m$, we divide the proof
into two cases.

Case 1. Assume that there is some $t\in[n]$ so that
$f^{\prime}(\\{t\\})=f(\\{t\\})$. Let
$T_{t}=\\{f([n])-f([n]\setminus\\{t\\}),\ldots,f(\\{t\\})\\}$ and
$T^{\prime}_{t}=\\{f^{\prime}([n])-f^{\prime}([n]\setminus\\{t\\}),\ldots,f^{\prime}(\\{t\\})\\}$.
Note that as $P^{\prime}\subset P$, we have $T^{\prime}_{t}\subset T_{t}$ and
$\widehat{P}^{\prime t}_{j}\subset\widehat{P}^{t}_{j}$ (cf. (6)) for any $j\in
T^{\prime}_{t}$. By the induction hypothesis and Corollary 3.6, we know that

$\displaystyle X_{P}(y)$ $\displaystyle=$ $\displaystyle
X_{\widehat{P}^{t}_{f(\\{t\\})}}(y)+y\sum_{j\in
T_{t}\setminus\\{f(\\{t\\})\\}}X_{\widehat{P}^{t}_{j}}(y)$ $\displaystyle=$
$\displaystyle X_{\widehat{P}^{t}_{f(\\{t\\})}}(y)+y\sum_{j\in
T_{t}^{\prime}\setminus\\{f(\\{t\\})\\}}X_{\widehat{P}^{t}_{j}}(y)+y\sum_{j\in
T_{t}\setminus T^{\prime}_{t}}X_{\widehat{P}^{t}_{j}}(y)$ $\displaystyle\geq$
$\displaystyle X_{\widehat{P}^{\prime t}_{f^{\prime}(\\{t\\})}}(y)+y\sum_{j\in
T_{t}^{\prime}\setminus\\{f^{\prime}(\\{t\\})\\}}X_{\widehat{P}^{\prime
t}_{j}}(y)+y\sum_{j\in T_{t}\setminus
T^{\prime}_{t}}X_{\widehat{P}^{t}_{j}}(y)$ $\displaystyle=$ $\displaystyle
X_{P^{\prime}}(y)+y\sum_{j\in T_{t}\setminus
T^{\prime}_{t}}X_{\widehat{P}^{t}_{j}}(y)$ $\displaystyle\geq$ $\displaystyle
X_{P^{\prime}}(y).$

Case 2. Assume that $f^{\prime}(\\{t^{\prime}\\})<f(\\{t^{\prime}\\})$ for all
$t^{\prime}\in[n]$. Then choose an arbitrary index $t\in[n]$. By the Exchange
Axiom, the set $P^{\prime\prime}=\\{\textbf{a}\in P\mid a_{t}\leq
f^{\prime}(\\{t\\})\\}$ is also a polymatroid. Case 1 implies that
$X_{P^{\prime}}\leq X_{P^{\prime\prime}}$. We now prove that
$X_{P^{\prime\prime}}\leq X_{P}$. This in fact follows from Case 1 applied to
any coordinate other that $t$, but we will follow a different route.

By the $S_{n}$-invariance of the exterior polynomial, we may assume that
$t=1$. We claim that

$\displaystyle\mathrm{Ext}_{P}(\textbf{b})=\mathrm{Ext}_{P^{\prime\prime}}(\textbf{b})\
\text{for any}\ \textbf{b}\in P^{\prime\prime}.$ (9)

  1. (i)

It is obvious that
$\mathrm{Ext}_{P}(\textbf{b})\subset\mathrm{Ext}_{P^{\prime\prime}}(\textbf{b})$
as $P^{\prime\prime}\subset P$.

  2. (ii)

If $i\notin\mathrm{Ext}_{P}(\textbf{b})$, then by definition, there exists
some $i^{\prime}\in[n]$ with $i^{\prime}<i$ so that
$\textbf{c}=\textbf{b}-\textbf{e}_{i^{\prime}}+\textbf{e}_{i}\in P$. Note that
$\textbf{c}\in P^{\prime\prime}$ as $c_{t}\leq b_{t}\leq f^{\prime}(\\{t\\})$.
Hence, $i\notin\mathrm{Ext}_{P^{\prime\prime}}(\textbf{b})$.

(9) implies that
$\overline{\epsilon}_{P}(\textbf{b})=\overline{\epsilon}_{P^{\prime\prime}}(\textbf{b})$
for any $\textbf{b}\in P^{\prime\prime}$. Then

$\displaystyle X_{P}(y)$ $\displaystyle=$ $\displaystyle\sum_{\textbf{b}\in
P}y^{\overline{\epsilon}_{P}(\textbf{b})}$ $\displaystyle=$
$\displaystyle\sum_{\textbf{b}\in
P^{\prime\prime}}y^{\overline{\epsilon}_{P}(\textbf{b})}+\sum_{\textbf{b}\in
P\setminus P^{\prime\prime}}y^{\overline{\epsilon}_{P}(\textbf{b})}$
$\displaystyle=$ $\displaystyle\sum_{\textbf{b}\in
P^{\prime\prime}}y^{\overline{\epsilon}_{P^{\prime\prime}}(\textbf{b})}+\sum_{\textbf{b}\in
P\setminus P^{\prime\prime}}y^{\overline{\epsilon}_{P}(\textbf{b})}$
$\displaystyle=$ $\displaystyle X_{P^{\prime\prime}}(y)+\sum_{\textbf{b}\in
P\setminus P^{\prime\prime}}y^{\overline{\epsilon}_{P}(\textbf{b})}$
$\displaystyle\geq$ $\displaystyle X_{P^{\prime\prime}}(y).$

This completes the proof. ∎

We next consider the case of minors.

######  Definition 4.3.

Let $P$ be a polymatroid on $[n]$. A polymatroid $P^{\prime}$ is a _minor_ of
$P$ if $P^{\prime}=(P\setminus A)/B$ or $P^{\prime}=(P/B)\setminus A$ for
disjoint subsets $A$ and $B$ of $[n]$.

The deletion and contraction are well-defined in the following sense.

######  Proposition 4.4.

Let $P$ be a polymatroid on $[n]$. Then $(P\setminus A)\setminus B=(P\setminus
B)\setminus A=P\setminus(A\cup B)$ and $(P/A)/B=(P/B)/A=P/(A\cup B)$ for
disjoint subsets $A$ and $B$ of $[n]$.

###### Proof.

Let $f_{P}$, $f_{P\setminus A}$, $f_{(P\setminus A)\setminus B}$,
$f_{P\setminus(A\cup B)}$, $f_{(P/A)/B}$, $f_{P/A}$ and $f_{P/(A\cup B)}$ be
the rank functions of the polymatroids $P$, $P\setminus A$, $(P\setminus
A)\setminus B$, $P\setminus(A\cup B)$, $(P/A)/B$, $P/A$ and $P/(A\cup B)$,
respectively. Then for any subset $T\subset[n]\setminus A\setminus B$,

$\displaystyle f_{(P\setminus A)\setminus B}(T)$ $\displaystyle=$
$\displaystyle f_{P\setminus A}(T)$ $\displaystyle=$ $\displaystyle f_{P}(T)$
$\displaystyle=$ $\displaystyle f_{P\setminus(A\cup B)}(T)$

and

$\displaystyle f_{(P/A)/B}(T)$ $\displaystyle=$ $\displaystyle f_{P/A}(T\cup
B)-f_{P/A}(B)$ $\displaystyle=$ $\displaystyle(f_{P}(T\cup B\cup
A)-f_{P}(A))-(f_{P}(B\cup A)-f_{P}(A))$ $\displaystyle=$ $\displaystyle
f_{P}(T\cup(B\cup A))-f_{P}(B\cup A)$ $\displaystyle=$ $\displaystyle
f_{P/(A\cup B)}(T).$

Hence, $(P\setminus A)\setminus B=P\setminus(A\cup B)$ and $(P/A)/B=P/(A\cup
B)$. Similarly, we also have that $(P\setminus B)\setminus A=P\setminus(A\cup
B)$ and $(P/B)/A=P/(A\cup B)$. This completes the proof. ∎

For a polymatroid $P$, let $f_{P}$ and $f_{-P}$ be the rank functions of the
polymatroids $P$ and $-P$, respectively. Then by (3) and the definition of the
dual polymatroid, we have that

$f_{-P}(T)=f_{P}([n]\setminus T)-f_{P}([n])$

for any subset $T\subset[n]$. Then the relation of the dual polymatroid and
contraction and deletion is as follows.

######  Proposition 4.5.

Let $P$ be a polymatroid on $[n]$. Then $-(P\setminus A)=(-P)/A$ and
$-(P/A)=(-P)\setminus A$ for any subset $A\subset[n]$.

###### Proof.

Let $f_{P}$, $f_{P\setminus A}$, $f_{-(P\setminus A)}$, $f_{(-P)/A}$ and
$f_{-P}$ be the rank functions of the polymatroids $P$, $P\setminus A$,
$-(P\setminus A)$, $(-P)/A$ and $-P$, respectively. Then for any subset
$T\subset[n]\setminus A$,

$\displaystyle f_{-(P\setminus A)}(T)$ $\displaystyle=$ $\displaystyle
f_{P\setminus A}([n]\setminus A\setminus T)-f_{P\setminus A}([n]\setminus A)$
$\displaystyle=$ $\displaystyle f_{P}([n]\setminus A\setminus
T)-f_{P}([n]\setminus A)$ $\displaystyle=$
$\displaystyle(f_{P}([n]\setminus(A\cup T))-f_{P}([n]))-(f_{P}([n]\setminus
A)-f_{P}([n]))$ $\displaystyle=$ $\displaystyle f_{-P}(T\cup A)-f_{-P}(A)$
$\displaystyle=$ $\displaystyle f_{(-P)/A}(T).$

Hence, $-(P\setminus A)=(-P)/A$. This implies that $-((-P)\setminus A)=P/A$.
Therefore, by (5), $-(P/A)=(-P)\setminus A$ also holds. ∎

We study monotonicity properties of the deletion and contraction before our
second main claim.

######  Lemma 4.6.

Let $P$ be a polymatroid on $[n]$. Then $I_{P\setminus A}\leq I_{P}$,
$I_{P/A}\leq I_{P}$, $X_{P\setminus A}\leq X_{P}$ and $X_{P/A}\leq X_{P}$ for
any subset $A\subset[n]$.

###### Proof.

It is enough to prove that the statements $I_{P\setminus A}\leq I_{P}$ and
$I_{P/A}\leq I_{P}$ hold because of (4) and Proposition 4.5. By Proposition
4.3, it suffices to consider the case that $A$ is a singleton set $\\{t\\}$.
In order to prove $I_{P\setminus\\{t\\}}\leq I_{P}$ and $I_{P/\\{t\\}}\leq
I_{P}$, by (7) and (8), it is equivalent to prove that
$I_{P^{t}_{\alpha_{t}}}\leq I_{P}$ and $I_{P^{t}_{\beta_{t}}}\leq I_{P}$.
These follow from Theorem 4.2. This completes the proof. ∎

######  Theorem 4.7.

If $P^{\prime}$ is a minor of a polymatroid $P$, then $I_{P^{\prime}}\leq
I_{P}$ and $X_{P^{\prime}}\leq X_{P}$.

###### Proof.

Without loss of generality, we can assume that $P$ is a polymatroid on $[n]$
and $P^{\prime}=(P\setminus A)/B$ for disjoint subsets $A\subset[n]$ and
$B\subset[n]$. (It is obvious that $(P\setminus A)/B=(P/B)\setminus A$.) Then
$I_{P^{\prime}}\leq I_{P\setminus A}\leq I_{P}$ and $X_{P^{\prime}}\leq
X_{P\setminus A}\leq X_{P}$ by Lemma 4.6. ∎

Now let us focus on the hypergraphical cases. We can also obtain a
monotonicity property of interior and exterior polynomials of hypergraphs by
Theorems 4.2, 4.7 and 2.6 (1).

######  Corollary 4.8.

Let $\mathcal{H}=(V,E)$ and $\mathcal{H}^{\prime}=(V^{\prime},E^{\prime})$ be
two hypergraphs. Let $\mathrm{Bip}\mathcal{H}$ and
$\mathrm{Bip}\mathcal{H}^{\prime}$ be the associated bipartite graphs of
$\mathcal{H}$ and $\mathcal{H}^{\prime}$, respectively. If
$\mathrm{Bip}\mathcal{H}^{\prime}$ is a subgraph of $\mathrm{Bip}\mathcal{H}$,
then $I_{\mathcal{H}^{\prime}}\leq I_{\mathcal{H}}$ and
$X_{\mathcal{H}^{\prime}}\leq X_{\mathcal{H}}$.

###### Proof.

Let $\mathrm{Bip}\mathcal{H}^{\prime\prime}$ be the bipartite graph obtained
by removing all vertices of $E\setminus E^{\prime}$ and all edges incident
with elements of $E\setminus E^{\prime}$ from $\mathrm{Bip}\mathcal{H}$. Then
$I_{\mathcal{H}^{\prime\prime}}\leq I_{\mathcal{H}}$ and
$X_{\mathcal{H}^{\prime\prime}}\leq X_{\mathcal{H}}$ by Theorem 4.7.

Let $\mathrm{Bip}\mathcal{H}^{\prime\prime\prime}$ be a bipartite graph
obtained by adding $|V\setminus V^{\prime}|$ vertices to $V^{\prime}$ and
$|V\setminus V^{\prime}|-c$ edges from $\mathrm{Bip}\mathcal{H}^{\prime}$ so
that there exists exactly an edge $uv^{\prime}$ incident with each vertex
$v^{\prime}$, of $V\setminus V^{\prime}$, incident with at least one edge in
$\mathrm{Bip}\mathcal{H}^{\prime\prime}$, where $uv^{\prime}$ is an edge of
$\mathrm{Bip}\mathcal{H}^{\prime\prime}$, and $c$ is the number of vertices,
of $V\setminus V^{\prime}$, incident with $0$ edges in
$\mathrm{Bip}\mathcal{H}^{\prime\prime}$. Then
$I_{\mathcal{H}^{\prime\prime\prime}}=I_{\mathcal{H}^{\prime}}$ and
$X_{\mathcal{H}^{\prime\prime\prime}}=X_{\mathcal{H}^{\prime}}$ by Theorem 2.6
(1).

Let $c(\mathrm{Bip}\mathcal{H}^{\prime\prime})$ and
$c(\mathrm{Bip}\mathcal{H}^{\prime\prime\prime})$ be the number of connected
components of $\mathrm{Bip}\mathcal{H}^{\prime\prime}$ and
$\mathrm{Bip}\mathcal{H}^{\prime\prime\prime}$, respectively. Note that
$\mathrm{Bip}\mathcal{H}^{\prime\prime\prime}\subset\mathrm{Bip}\mathcal{H}^{\prime\prime}$.
Then $c(\mathrm{Bip}\mathcal{H}^{\prime\prime\prime})\geq
c(\mathrm{Bip}\mathcal{H}^{\prime\prime})$. Arbitrarily choose
$c(\mathrm{Bip}\mathcal{H}^{\prime\prime\prime})-c(\mathrm{Bip}\mathcal{H}^{\prime\prime})$
edges $\widehat{E}$ in $\mathrm{Bip}\mathcal{H}^{\prime\prime}$ so that
$c(\mathrm{Bip}\mathcal{H}^{\prime\prime\prime}+\widehat{E})=c(\mathrm{Bip}\mathcal{H}^{\prime\prime})$.
Let $\mathrm{Bip}\mathcal{H}^{4}$ be a bipartite graph obtained by adding
$c(\mathrm{Bip}\mathcal{H}^{\prime\prime\prime})-c(\mathrm{Bip}\mathcal{H}^{\prime\prime})$
vertices $\widehat{V}$ to $V$ and replacing $uv$ by an edge joining $u$ to
some vertex of $\widehat{V}$ for each edge $uv\in\widehat{E}$ from
$\mathrm{Bip}\mathcal{H}^{\prime\prime\prime}+\widehat{E}$, where $u\in
E^{\prime}$ and $v\in V$, so that for each $v\in\widehat{V}$, there exists
exactly an edge incident with $v$. Note that
$\mu_{\mathrm{Bip}\mathcal{H}^{4}}(T)\leq\mu_{\mathrm{Bip}\mathcal{H}^{\prime\prime}}(T)$
for all $T\subset E^{\prime}$, and
$\mu_{\mathrm{Bip}\mathcal{H}^{4}}(E^{\prime})=\mu_{\mathrm{Bip}\mathcal{H}^{\prime\prime}}(E^{\prime})$.
Then by Theorem 4.2, we know that $I_{\mathcal{H}^{4}}\leq
I_{\mathcal{H}^{\prime\prime}}$ and $X_{\mathcal{H}^{4}}\leq
X_{\mathcal{H}^{\prime\prime}}$. Moreover, by Theorem 2.6 (1), we have that
$I_{\mathcal{H}^{\prime}}=I_{\mathcal{H}^{4}}$ and
$X_{\mathcal{H}^{\prime}}=X_{\mathcal{H}^{4}}$. Hence, the conclusion holds.

See Figure 1 for an illustration. ∎

######  Remark 4.9.

Let $P$ and $P^{\prime}$ be polymatroids on the same set $[n]$. If
$P^{\prime}\subset P$, then it is possible that there are $i,j\in\mathbb{Z}$
so that
$x^{i}y^{j}[\mathscr{T}_{P^{\prime}}(x,y)]>x^{i}y^{j}[\mathscr{T}_{P}(x,y)]$.
Likewise, this monotonicity property of the polymatroid Tutte polynomial does
not hold for minors either. Counterexamples can already be found among
hypergraphical cases. Furthermore, for a polymatroid $P$ over $[n]$ with rank
$d$, let us define

$T_{P}(x,y):=\frac{(x+y-xy)^{n}}{x^{n-d}y^{d}}\mathscr{T}_{P}(\frac{x}{x+y-xy},\frac{y}{x+y-xy}).$

This is an equivalent form of $\mathscr{T}_{P}$ and when written in this way,
the invariant becames a direct generalization of the Tutte polynomial of
matroids, cf. (1). Moreover, $T_{P}(x,y)$ does not satisfy the monotonicity
property, either.

For example, let us consider the hypergraphical polymatroids $P_{\mathcal{H}}$
and $P_{\mathcal{H}^{\prime}}$ over $\\{1,2,3\\}$, where the hypergraphs
$\mathcal{H}$ and $\mathcal{H}^{\prime}$ are defined by their associated
bipartite graphs in Figure 2 (1) and (2), respectively. Let also
$P_{\mathcal{H}^{\prime\prime}}=P_{\mathcal{H}}\setminus\\{1\\}$; see Figure 2
(3) for the associated bipartite graph. Then $P_{\mathcal{H}^{\prime}}\subset
P_{\mathcal{H}}$ and $P_{\mathcal{H}^{\prime\prime}}$ is a minor of
$P_{\mathcal{H}}$. On the other hand,

$\mathscr{T}_{P_{\mathcal{H}}}(x,y)=x^{3}+3x^{2}y+3xy^{2}+y^{3}+2x^{2}+3xy+y^{2}-x-2,$
$\mathscr{T}_{P_{\mathcal{H}^{\prime}}}(x,y)=x^{3}+3x^{2}y+3xy^{2}+y^{3}-2x^{2}-4xy-2y^{2}+x+y,$

and

$\mathscr{T}_{P_{\mathcal{H}^{\prime\prime}}}(x,y)=x^{2}+2xy+y^{2}-x-y.$

In particular, we have
$xy^{0}[\mathscr{T}_{P_{\mathcal{H}^{\prime}}}(x,y)]>xy^{0}[\mathscr{T}_{P_{\mathcal{H}}}(x,y)]$,
$x^{0}y[\mathscr{T}_{P_{\mathcal{H}^{\prime}}}(x,y)]>x^{0}y[\mathscr{T}_{P_{\mathcal{H}}}(x,y)]$,
$x^{0}y^{0}[\mathscr{T}_{P_{\mathcal{H}^{\prime}}}(x,y)]>x^{0}y^{0}[\mathscr{T}_{P_{\mathcal{H}}}(x,y)]$,
and
$x^{0}y^{0}[\mathscr{T}_{P_{\mathcal{H}^{\prime\prime}}}(x,y)]>x^{0}y^{0}[\mathscr{T}_{P_{\mathcal{H}}}(x,y)]$.

Note that
$\mathscr{T}_{P_{\mathcal{H}}}(x,y)-\mathscr{T}_{P_{\mathcal{H^{\prime}}}}(x,y)=4x^{2}+7xy+3y^{2}-2x-y-2.$
This yields

$\displaystyle T_{P_{\mathcal{H}}}(x,y)-T_{P_{\mathcal{H}^{\prime}}}(x,y)$
$\displaystyle=$
$\displaystyle\left(\mathscr{T}_{P_{\mathcal{H}}}(\frac{x}{x+y-xy},\frac{y}{x+y-xy})-\mathscr{T}_{P^{\prime}_{\mathcal{H^{\prime}}}}(\frac{x}{x+y-xy},\frac{y}{x+y-xy})\right)$
$\displaystyle\cdot\frac{(x+y-xy)^{3}}{x^{-1}y^{4}}$ $\displaystyle=$
$\displaystyle
xy^{-4}(2x^{3}y^{3}-8x^{3}y^{2}-7x^{2}y^{3}+11x^{2}y^{2}+6x^{3}y+5xy^{3}).$

Hence, we have
$x^{4}y^{-2}[T_{P_{\mathcal{H}^{\prime}}}(x,y)]>x^{4}y^{-2}[T_{P_{\mathcal{H}}}(x,y)]$
and
$x^{3}y^{-1}[T_{P_{\mathcal{H}^{\prime\prime}}}(x,y)]>x^{3}y^{-1}[T_{P_{\mathcal{H}}}(x,y)]$.

As to $\mathcal{H}^{\prime\prime}$, whose $n$ value differs from that of
$\mathcal{H}$, we have

$T_{P_{\mathcal{H}^{\prime\prime}}}(x,y)=x^{2}y^{-4}(x^{2}+2xy+y^{2}-(x+y)(x+y-xy)).$

In particular, $x^{4}y^{-2}[T_{P_{\mathcal{H}^{\prime\prime}}}(x,y)]=0$. On
the other hand,

$\displaystyle T_{P_{\mathcal{H}}}(x,y)$ $\displaystyle=$ $\displaystyle
xy^{-4}(x^{3}+3x^{2}y+3xy^{2}+y^{3}+(2x^{2}+3xy+y^{2})(x+y-xy)$
$\displaystyle-x(x+y-xy)^{2}-2(x+y-xy)^{3})$

has
$x^{4}y^{-2}[T_{P_{\mathcal{H}}}(x,y)]=-7<0=x^{4}y^{-2}[T_{P_{\mathcal{H}^{\prime\prime}}}(x,y)]$.

##  5 Further applications of the deletion-contraction formula

In this section, by applying the deletion-contraction formula of Section 3, we
compute the coefficients of some terms of the polymatroid Tutte polynomial and
characterize a family hypergraphs.

###  5.1 The extremal coefficients of $\mathscr{T}_{P}(x,y)$

In this subsection, we study the coefficients of some extremal terms of the
polymatroid Tutte polynomial.

In [1, Proposition 4.11 (d)], Bernardi, Kálmán, and Postnikov derived the
coefficients of the top degree terms of the polymatroid Tutte polynomial.

######  Lemma 5.1.

[1] Let $P$ be a polymatroid over $[n]$. Then for any $k\in[n]\cup\\{0\\}$,

$x^{k}y^{n-k}[\mathscr{T}_{P}(x,y)]=\binom{n}{k}.$

By Lemmas 4.1 and 5.1, we have the following statement.

######  Lemma 5.2.

Let $P$ be a polymatroid over $[n]$ with the rank function $f$. Then

$x^{n-1}[\mathscr{T}_{P}(x,y)]=\sum_{i\in[n]}f(\\{i\\})-f([n])-n$

and

$y^{n-1}[\mathscr{T}_{P}(x,y)]=\sum_{i\in[n]}f([n]\setminus\\{i\\})-(n-1)f([n])-n.$

We next study the coefficients of the degree $n-1$ terms in
$\mathscr{T}_{P}(x,y)$ that generalizes Lemma 5.2, using the deletion-
contraction relation obtained in Section 3.

######  Theorem 5.3.

Let $P$ be a polymatroid on $[n]$ with the rank function $f$. Then for any
$k\in[n]$,

$x^{n-k}y^{k-1}[\mathscr{T}_{P}(x,y)]=\sum_{\stackrel{{\scriptstyle
S\subset[n]}}{{|S|=k-1}}}f(S)+\sum_{\stackrel{{\scriptstyle
S^{\prime}\subset[n]}}{{|S^{\prime}|=k}}}f(S^{\prime})-\binom{n}{k-1}f([n])-k\binom{n}{k}.$
(10)

###### Proof.

For any $t\in[n]$, let $\alpha_{t}=f([n])-f([n]\setminus\\{t\\})$ and
$\beta_{t}=f(\\{t\\})$.

If $\alpha_{t^{\prime}}=\beta_{t^{\prime}}$ for all $t^{\prime}\in[n]$, then
$P$ has unique basis. Hence,

$\mathscr{T}_{P}(x,y)=(x+y-1)^{n}.$

Then the left-hand side of the equation (10) is

$x^{n-k}y^{k-1}[\mathscr{T}_{P}(x,y)]=-\binom{n}{n-1}\binom{n-1}{k-1}=-n\binom{n-1}{k-1}.$

Note that in this case,

$\sum_{\stackrel{{\scriptstyle
S\subset[n]}}{{|S|=k-1}}}f(S)=\binom{n-1}{k-2}f([n])\ \ \ \text{and}\ \ \
\sum_{\stackrel{{\scriptstyle
S^{\prime}\subset[n]}}{{|S^{\prime}|=k}}}f(S)=\binom{n-1}{k-1}f([n]).$

Then the right-hand side of the equation (10) is

$\sum_{\stackrel{{\scriptstyle
S\subset[n]}}{{|S|=k-1}}}f(S)+\sum_{\stackrel{{\scriptstyle
S^{\prime}\subset[n]}}{{|S^{\prime}|=k}}}f(S^{\prime})-\binom{n}{k-1}f([n])-k\binom{n}{k}=-k\binom{n}{k}=-n\binom{n-1}{k-1}.$

Assume that there exists some $t\in[n]$ satisfying $\alpha_{t}\neq\beta_{t}$.
Then we prove the equation (10) by induction on $n$. It is obvious in the
cases $n=1$ and $n=2$ by Lemma 4.1. Suppose that $n\geq 3$. Let
$T_{t}=\\{\alpha_{t},\alpha_{t}+1,\ldots,\beta_{t}\\}$. For any $j\in T_{t}$,
let $P^{t}_{j}=\\{(a_{1},\ldots,a_{n})\in P\mid a_{t}=j\\}$ and
$\widehat{P}^{t}_{j}=\\{(a_{1},\ldots,a_{t-1},a_{t+1},\ldots,a_{n})\in\mathbb{Z}^{n-1}\mid(a_{1},\ldots,a_{n})\in
P^{t}_{j}\\}$, and let $f^{t}_{j}$ be the rank function of
$\widehat{P}^{t}_{j}$.

By Proposition 3.2, for any subset $I\subset[n]\setminus\\{t\\}$, we note that
$f^{t}_{\alpha_{t}}(I)=f(I)$ and
$f^{t}_{\beta_{t}}(I)=f(I\cup\\{t\\})-f(\\{t\\})$. Then by the induction
hypothesis,

$\displaystyle x^{n-k-1}y^{k-1}[\mathscr{T}_{P^{t}_{\alpha_{t}}}(x,y)]$
$\displaystyle=$ $\displaystyle\sum_{\stackrel{{\scriptstyle
T\subset[n]\setminus\\{t\\}}}{{|T|=k-1}}}f^{t}_{\alpha_{t}}(T)+\sum_{\stackrel{{\scriptstyle
T^{\prime}\subset[n]\setminus\\{t\\}}}{{|T^{\prime}|=k}}}f^{t}_{\alpha_{t}}(T^{\prime})-\binom{n-1}{k-1}f^{t}_{\alpha_{t}}([n]\setminus\\{t\\})-k\binom{n-1}{k}$
$\displaystyle=$ $\displaystyle\sum_{\stackrel{{\scriptstyle
T\subset[n]\setminus\\{t\\}}}{{|T|=k-1}}}f(T)+\sum_{\stackrel{{\scriptstyle
T^{\prime}\subset[n]\setminus\\{t\\}}}{{|T^{\prime}|=k}}}f(T^{\prime})-\binom{n-1}{k-1}f([n]\setminus\\{t\\})-k\binom{n-1}{k}.$

and

$\displaystyle x^{n-k}y^{k-2}[\mathscr{T}_{P^{t}_{\beta_{t}}}(x,y)]$
$\displaystyle=$ $\displaystyle\sum_{\stackrel{{\scriptstyle
T\subset[n]\setminus\\{t\\}}}{{|T|=k-2}}}f^{t}_{\beta_{t}}(T)+\sum_{\stackrel{{\scriptstyle
T^{\prime}\subset[n]\setminus\\{t\\}}}{{|T^{\prime}|=k-1}}}f^{t}_{\beta_{t}}(T^{\prime})-\binom{n-1}{k-2}f^{t}_{\beta_{t}}([n]\setminus\\{t\\})$
$\displaystyle-(k-1)\binom{n-1}{k-1}$ $\displaystyle=$
$\displaystyle\sum_{\stackrel{{\scriptstyle
T\subset[n]\setminus\\{t\\}}}{{|T|=k-2}}}(f(T\cup\\{t\\})-f(\\{t\\}))+\sum_{\stackrel{{\scriptstyle
T\subset[n]\setminus\\{t\\}}}{{|T^{\prime}|=k-1}}}(f(T^{\prime}\cup\\{t\\})-f(\\{t\\}))$
$\displaystyle-\binom{n-1}{k-2}(f([n])-f(\\{t\\}))-(k-1)\binom{n-1}{k-1}$
$\displaystyle=$ $\displaystyle\sum_{\stackrel{{\scriptstyle
T\subset[n]\setminus\\{t\\}}}{{|T|=k-2}}}f(T\cup\\{t\\})+\sum_{\stackrel{{\scriptstyle
T\subset[n]\setminus\\{t\\}}}{{|T^{\prime}|=k-1}}}f(T^{\prime}\cup\\{t\\})-\binom{n-1}{k-1}f(\\{t\\})$
$\displaystyle-\binom{n-1}{k-2}(f([n])-(k-1)\binom{n-1}{k-1}.$

By Lemma 5.1,

$\displaystyle\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}x^{n-k}y^{k-1}[\mathscr{T}_{P^{t}_{j}}(x,y)]$
$\displaystyle=$ $\displaystyle\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}\binom{n-1}{k-1}$ $\displaystyle=$
$\displaystyle\binom{n-1}{k-1}(\beta_{t}-\alpha_{t}-1)$ $\displaystyle=$
$\displaystyle\binom{n-1}{k-1}(f(\\{t\\})+f([n]\setminus\\{t\\})-f([n])-1).$

By Theorems 3.5,

$x^{n-k}y^{k-1}[\mathscr{T}_{P}(x,y)]=x^{n-k-1}y^{k-1}[\mathscr{T}_{\widehat{P}^{t}_{\alpha_{t}}}(x,y)]+x^{n-k}y^{k-2}[\mathscr{T}_{\widehat{P}^{t}_{\beta_{t}}}(x,y)]\\\
+\sum_{j\in
T_{t}\setminus\\{\alpha_{t},\beta_{t}\\}}x^{n-k}y^{k-1}[\mathscr{T}_{\widehat{P}^{t}_{j}}(x,y)].$

Hence, the equation (10) holds. ∎

Similarly, we can get formulas for the coefficients
$x^{n-2}[\mathscr{T}_{P}(x,y)]$ and $y^{n-2}[\mathscr{T}_{P}(x,y)]$. The proof
is left for the readers.

######  Theorem 5.4.

Let $P$ be a polymatroid on $[n]$ with the rank function $f$. Then

  1. (1)

$x^{n-2}[\mathscr{T}_{P}(x,y)]=\binom{\sum\limits_{i\in[n]}f(\\{i\\})-f([n])+1-n}{2}-\left(\sum\limits_{\\{i,j\\}\subset[n]}\binom{f(\\{i\\})+f(\\{j\\})-f(\\{i,j\\})}{2}\right)$;

  2. (2)

$y^{n-2}[\mathscr{T}_{P}(x,y)]=\binom{\sum\limits_{i\in[n]}f([n]\setminus\\{i\\})-(n-1)f([n])+1-n}{2}\\\
-\left(\sum\limits_{\\{i,j\\}\subset[n]}\binom{f([n]\setminus\\{i\\})+f([n]\setminus\\{j\\})-f([n]\setminus\\{i,j\\})-f([n])}{2}\right)$.

Lemma 5.1, Theorems 5.3 and 5.4 imply the following conclusion.

######  Corollary 5.5.

For a polymatroid $P$ on $[n]$ with the rank function $f$,

  1. (1)

$x^{n-2}[\mathscr{T}_{P}(x,1)]=\binom{\sum\limits_{i\in[n]}f(\\{i\\})-f([n])+1}{2}-\left(\sum\limits_{\\{i,j\\}\subset[n]}\binom{f(\\{i\\})+f(\\{j\\})-f(\\{i,j\\})+1}{2}\right)$;

  2. (2)

$y^{n-2}[\mathscr{T}_{P}(1,y)]=\binom{\sum\limits_{i\in[n]}f([n]\setminus\\{i\\})-(n-1)f([n])+1}{2}\\\
-\left(\sum_{\\{i,j\\}\subset[n]}\binom{f([n]\setminus\\{i\\})+f([n]\setminus\\{j\\})-f([n]\setminus\\{i,j\\})-f([n])+1}{2}\right)$.

###### Proof.

This follows from Lemma 5.1, Theorems 5.3 and 5.4, since

$x^{n-2}[\mathscr{T}_{P}(x,1)]=x^{n-2}[\mathscr{T}_{P}(x,y)]+x^{n-2}y[\mathscr{T}_{P}(x,y)]+x^{n-2}y^{2}[\mathscr{T}_{P}(x,y)]$

and

$y^{n-2}[\mathscr{T}_{P}(1,y)]=y^{n-2}[\mathscr{T}_{P}(x,y)]+xy^{n-2}[\mathscr{T}_{P}(x,y)]+x^{2}y^{n-2}[\mathscr{T}_{P}(x,y)]$

∎

For hypergraphical cases, Corollary 5.5 (1) is consistent with the result in
[11].

######  Corollary 5.6.

[11, Proposition 5.5] Let $\mathcal{H}$ be a hypergraph and let
$\mathrm{Bip}\mathcal{H}=(V\cup E,\mathcal{E})$ be its associated bipartite
graph. Then $x^{2}[I_{\mathcal{H}}(x)]=\binom{|\mathcal{E}|-|V|-|E|+2}{2}-N$,
where $N$ is the number of 4-cycles in $\mathrm{Bip}\mathcal{H}$.

###  5.2 A characterization of the connectivity of hypergraphs

In this subsection, we characterize a family hypergraphs using the external
polynomial.

Kálmán [9] obtained the exterior polynomial of hypergraphs induced by complete
bipartite graphs.

######  Observation 5.7 ([9]).

Let $P$ be a polymatroid on $[n]$ and $f$ be its rank function. If
$f(I)=f([n])$ for all nonempty subset $I\subset[n]$, then
$y^{i}[X_{\mathcal{H}}(y)]=\binom{f([n])+i-1}{i}$ for all nonnegative integer
$i\leq n-1$.

By Corollary 4.8 and Observation 5.7, we know that the coefficient of the
degree $k$ term of the exterior polynomial of any hypergraph
$\mathcal{H}=(V,E)$ is at most $\binom{|V|+k-2}{k}$. We now characterize
hypergraphs attaining this maximal value. We first show the key lemma in this
subsection.

######  Lemma 5.8.

Let $P\subset\mathbb{Z}^{n}_{\geq 0}$ be a polymatroid and let $f$ be its rank
function. Then for all $k\geq 0$, $f([n]\setminus J)=f([n])$ for all
$J\subset[n]$ with $|J|=k$ if and only if
$y^{i}[X_{P}(y)]=\binom{f([n])+i-1}{i}$ for all $i\leq k$.

###### Proof.

It is obvious for the case $k=0$ since the constant term of the exterior
polynomial for any polymatroid is $1$. We now assume that $k\geq 1$. We first
prove the necessity by induction on $n$. If $n=k+1$, then this follows from
Observation 5.7.

Assume that $n>k+1$. Note that if $P\subset\mathbb{Z}^{n}_{\geq 0}$, then $f$
is non-decreasing by (3). This implies that $f([n]\setminus I)=f([n])$ for all
subset $I\subset[n]$ with $|I|\leq k$. Hence,
$T_{t}=\\{0,1,2,\ldots,f(\\{t\\})\\}$ for any $t\in[n]$. For any $j\in T_{t}$,
let $f^{t}_{j}$ be the rank function of the polymatroid $\widehat{P}^{t}_{j}$.
We have that

  1. (1)

for any $j\in T_{t}\setminus\\{f(\\{t\\})\\}$ and any subset
$J^{\prime}\subset[n]\setminus\\{t\\}$ with $|J^{\prime}|=k-1$,
$f([n]\setminus J^{\prime})-j=f([n])-j\leq
f([n])=f([n]\setminus\\{t\\}\setminus J^{\prime})$. Then
$f^{t}_{j}([n]\setminus\\{t\\}\setminus
J^{\prime})=f([n])-j=f^{t}_{j}([n]\setminus\\{t\\})$ by Proposition 3.2;

  2. (2)

$f^{t}_{f(\\{t\\})}([n]\setminus\\{t\\}\setminus
J^{\prime\prime})=f([n]\setminus
J^{\prime\prime})-f(\\{t\\})=f([n])-f(\\{t\\})=f^{t}_{f(\\{t\\})}([n]\setminus\\{t\\})$
for any subset $J^{\prime\prime}\subset[n]\setminus\\{t\\}$ with
$|J^{\prime\prime}|=k$ by Proposition 3.2.

By the induction hypothesis, for any nonnegative integer $i\leq k$, we have
$y^{i}[X_{\widehat{P}^{t}_{f(\\{t\\})}}(y)]=\binom{f([n])+i-1-f(\\{t\\})}{i}$
and $y^{i-1}[X_{\widehat{P}^{t}_{j}}(y)]=\binom{f([n])-j+i-1-1}{i-1}$ for any
$j\in T_{t}\setminus\\{f(\\{t\\})\\}$. Hence, by Corollary 3.6, we know that

$\displaystyle y^{i}[X_{P}(y)]$ $\displaystyle=$ $\displaystyle
y^{i}[X_{\widehat{P}^{t}_{f(\\{t\\})}}(y)]+\sum_{j\in
T_{t}\setminus\\{f(\\{t\\})\\}}y^{i-1}[X_{\widehat{P}^{t}_{j}}(y)]$
$\displaystyle=$ $\displaystyle\binom{f([n])+i-1-f(\\{t\\})}{i}+\sum_{j\in
T_{t}\setminus\\{f(\\{t\\})\\}}\binom{f([n])-j+i-2}{i-1}$ $\displaystyle=$
$\displaystyle\binom{f([n])+i-1}{i}.$

For the sufficiency, by induction on $n$, we prove
$y^{i}[X_{P}(y)]<\binom{f([n])+i-1}{i}$ for some $i\leq k$ if $f([n]\setminus
T^{\prime})<f([n])$ for some subset $T^{\prime}\subset[n]$ of size $k$.

If $n=k+1$, then it is clear as $|P|<\sum_{i=0}^{k}\binom{f([n])+i-1}{i}$.
(This is because that $\textbf{a}\notin P$ if
$\textbf{a}=(a_{1},\ldots,a_{n})\in\mathbb{Z}^{n}$ satisfies
$\sum_{i\in[n]\setminus T^{\prime}}a_{i}=f([n])$.)

Assume that $n>k+1$. Let $t^{\prime}$ be an element of $[n]\setminus
T^{\prime}$. Then the subset $T^{\prime}\subset[n]\setminus\\{t^{\prime}\\}$
satisfies
$f^{t^{\prime}}_{f(\\{t^{\prime}\\})}([n]\setminus\\{t^{\prime}\\}\setminus
T^{\prime})=f([n]\setminus
T^{\prime})-f(\\{t^{\prime}\\})<f([n])-f(\\{t^{\prime}\\})=f^{t^{\prime}}_{f(\\{t^{\prime}\\})}([n]\setminus\\{t^{\prime}\\})$.
By the induction hypothesis,
$y^{i}[X_{\widehat{P}^{t^{\prime}}_{f(\\{t^{\prime}\\})}}]<\binom{f([n])+i-1-f(t^{\prime})}{i}$
for some $i\leq k$. By Theorem 4.2 and Observation 5.7, for all $j\in
T_{t^{\prime}}\setminus\\{f(\\{t^{\prime}\\})\\}$,
$y^{i-1}[X_{\widehat{P}^{t^{\prime}}_{j}}]\leq\binom{f([n])-j+i-2}{i-1}$ as
$\widehat{P}^{t^{\prime}}_{j}\subset P^{\prime}$, where $P^{\prime}$ is the
polymatroid on the ground set $[n]\setminus\\{t^{\prime}\\}$ so that the rank
of $I$ equals $f([n])-j$ for all nonempty subset
$I\subset[n]\setminus\\{t^{\prime}\\}$. By Corollary 3.6,

$y^{i}[X_{P}(y)]=y^{i}[X_{\widehat{P}^{t^{\prime}}_{f(\\{t\\})}}(y)]+\sum_{j\in
T_{t^{\prime}}\setminus\\{f(\\{t^{\prime}\\})\\}}y^{i-1}[X_{\widehat{P}^{t^{\prime}}_{j}}(y)]<\binom{f([n])+i-1}{i},$

a contraction. This completes the proof. ∎

######  Theorem 5.9.

Let $\mathcal{H}=(V,E)$ be a hypergraph and $\mathrm{Bip}\mathcal{H}$ be its
associated bipartite graph. Then for all $k\geq 0$, we have
$y^{i}[X_{\mathcal{H}}]=\binom{|V|+i-2}{i}$ for all $i\leq k$ if and only if
$\mathrm{Bip}\mathcal{H}-E^{\prime}$ is connected for any $E^{\prime}\subset
E$ with $|E^{\prime}|=k$.

###### Proof.

It follows from Lemma 5.8 since if $\mathrm{Bip}\mathcal{H}-E^{\prime}$ is
connected, then $f(E\setminus E^{\prime})=f(E)=|V|-1$, where $f$ is the rank
function of $\mathcal{H}$. ∎

######  Corollary 5.10.

For a graph $G=(V,E)$ and an integer $k\geq 0$,
$y^{i}[T_{G}(1,y)]=\binom{|E|+|V|+i-2}{i}$ for all $|E|-|V|+2-k\leq
i\leq|E|-|V|+1$ if and only if $G$ is $k-$edge connected.

######  Remark 5.11.

Let $\mathcal{H}=(V,E)$ be a hypergraph and $\mathrm{Bip}\mathcal{H}$ be its
associated bipartite graph. For all $k\geq 0$, if there is a subset
$E^{\prime}\subset E$ with $|E^{\prime}|=k$ so that
$\mathrm{Bip}\mathcal{H}-E^{\prime}$ is connected and there two at least two
edge incident with $e$ in $\mathrm{Bip}\mathcal{H}$ for all $e\in E^{\prime}$,
then $y^{i}[X_{\mathcal{H}}]>0$ for all $i\leq k$.

_Proof._ Given an order of $E$ so that the elements of $E^{\prime}$ is the
last $|E^{\prime}|$ elements of $E$, there exists a vector
$\textbf{a}=(a_{1},\ldots,a_{|E|-|E^{\prime}|},0,\ldots,0)$) is a basis of its
hypergraphical polymatroid $P_{\mathcal{H}}$, since
$\mathrm{Bip}\mathcal{H}-E^{\prime}$ is connected. Let $f$ be the rank
function of $P_{\mathcal{H}}$. Then for all $e\in E^{\prime}$,
$f(E^{\prime\prime})>0$ for all $E^{\prime\prime}$ with $e\in
E^{\prime\prime}$. This implies that $\sum_{e\in
E^{\prime\prime\prime}}a_{e}=0<f(E^{\prime\prime\prime})$ for all subset
$E^{\prime\prime\prime}\subset E$ with $e\in E^{\prime\prime\prime}$ and
$e=\min(E^{\prime\prime})$. So,
$e\notin\mathrm{Ext}_{P_{\mathcal{H}}}(\textbf{a})$. We have that
$\epsilon(\textbf{a})\leq|E|-k$. By the interpolatory property of the exterior
polynomial (see [6, Theorem 14]), $y^{i}[X_{\mathcal{H}}]>0$ for all $i\leq
k$.

## Acknowledgements

This paper was written while the first author visited the Tokyo Institute of
Technology in 2022-2023. It is a pleasure to acknowledge the hospitality, as
well as the financial support from China Scholarship Council (No.
202206310079), that made the visit possible.

XJ was supported by National Natural Science Foundation of China (No.
12171402).

TK was supported by consecutive Japan Society for the Promotion of Science
(JSPS) Grants-in-Aid for Scientific Research C (Nos. 17K05244 and 23K03108).

## References

## References

  * [1] O. Bernardi, T. Kálmán and A. Postnikov, Universal Tutte polynomial, Adv. Math. 402 (2022) 108355.
  * [2] T. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972) 235-282.
  * [3] A. Cameron and A. Fink, The Tutte polynomial via lattice point counting, J. Combin. Theory Ser. A 188 (2022) 105584.
  * [4] L. Chávez–Lomelí, C. Merino, G. Sánchez and G. Whittle, A new polynomial for polymatroids, Australasian J. Combinatorics 80(3) (2021) 342-360.
  * [5] J. Edmonds, Submodular functions, matroids, and certain polyhedra, in: Combinatorial Structures and Their Applications, Proc. Calgary Internat. Conf., Calgary, Alta., 1969, Gordon and Breach, New York, 1970, pp. 69-87.
  * [6] X. Guan, W. Yang and X. Jin, On the polymatroid Tutte polynomial, J. Combin. Theory Ser. A. 201 (2024) 105798.
  * [7] J. Herzog and T. Hibi, Discrete Polymatroids, J. Algebraic Combinatorics 16 (2002), 239-268.
  * [8] V. Jones, Hecke algebra representations of braid groups and link polynomials. Ann. Math. 126 (1987), 335-388.
  * [9] T. Kálmán, A version of Tutte’s polynomial for hypergraphs, Adv. Math. 244 (2013) 823-873.
  * [10] T. Kálmán and H. Murakami, Root polytopes, parking functions, and the HOMFLY polynomial, Quantum Topol. 8(2) (2017) 205-248.
  * [11] T. Kálmán and A. Postnikov, Root polytopes, Tutte polynomial, and a duality theorem for bipartite graphs, Proc. Lond. Math. Soc. 114(3) (2017) 561-588.
  * [12] K. Kato, Interior polynomial of signed bipartite graphs and the HOMFLY polynomial, J. Knot Theory Ramifications 29(12) (2020) 2050077.
  * [13] A. Postnikov, Permutohedra, Associahedra, and Beyond, Int. Math. Res. Not. 6 (2009) 1026-1106.
  * [14] A. Schrijver, Combinatorial optimization: Polyhedra and efficiency, Algorithms and Combinatorics, 24 (Springer-Verlag, Berlin, 2003).
  * [15] R. P. Stanley, A Monotonicity Property of $h$-vectors and $h^{\ast}$-vectors, Europ. J. Combinatorics, 14 (1993) 251-258.
  * [16] W. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80-91.