# Polymatroids are to finite groups as matroids are to finite fields

Ed Swartz
Cornell University, Ithaca, NY

Prairie Wentworth-Nice
Cornell University, Ithaca, NY

Alexander Xue
UCLA, Los Angeles, CA

###### Abstract

Given a subgroup $\mathcal{H}$ of a product of finite groups
$\mathcal{G}=\displaystyle\prod^{n}_{i=1}\Gamma_{i}$ and $b>1,$ we define a
polymatroid $P(\mathcal{H},b).$ If all of the $\Gamma_{i}$ are isomorphic to
$\mathbb{Z}/p\mathbb{Z},~{}p$ a prime, and $b=p,$ then $P(\mathcal{H},b)$ is
the usual matroid associated to any $\mathbb{Z}/p\mathbb{Z}$-matrix whose row
space equals $\mathcal{H}.$ In general, there are many ways in which the
relationship between $P(\mathcal{H},b)$ and $\mathcal{H}$ mirrors that of the
relationship between a matroid and a subspace of a finite vector space. These
include representability by excluded minors, the Crapo-Rota critical theorem,
the existence of a concrete algebraic object representing the polymatroid dual
of $P(\mathcal{H},b),$ analogs of Greene’s theorem and the MacWilliams
identities when $\mathcal{H}$ is a group code over a nonabelian group, and a
connection to the combinatorial Laplacian of a quotient space determined by
$\mathcal{G}$ and $\mathcal{H}.$ We use the group Crapo-Rota critical theorem
to demonstrate an extension to hypergraphs of the classical duality between
proper colorings and nowhere-zero flows on graphs.

##  1 Introduction

It has been almost ninety years since Whitney began the theory of matroids
[45]. Since then, the reach and interest in matroids has expanded so
dramatically that it is no longer possible to give a reasonably sized review
of the literature involved. A significant portion of that literature involves
linear algebra over finite fields. One of the most common settings for
matroids starts with a matrix $A$ with coefficients in a finite field
${\mathbb{F}}.$ Let $E$ be the columns of $A.$ Then $E$ is the ground set for
a matroid $M[A]$. The rank function, $r_{A},$ of $M[A]$ assigns to every
subset $S$ of the columns of $A,$ the dimension of the span of the columns in
$S$ in the column space of $A.$ An alternative approach is to start with a
subspace $W$ of the ${\mathbb{F}}$-vector space ${\mathbb{F}}^{E}.$ Then
choose a matrix $A$ whose row space equals $W$ and set $M[W]$ to be the
matroid $M[A].$ Since matrices with the same row space have the same column
dependence relations, $M[W]$ is well defined. It was this point of view,
applied to elements of the complex Grassmannian and its moment map, that led
Gelfand, Goresky, MacPherson, and Serganova to rediscover Edmonds’ matroid
polytopes [17].

Matroid polytopes are a special case of polymatroid polytopes. The latter were
introduced by Edmonds over fifty years ago as a polyhedral generalization of
the matroid greedy algorithm, which itself was a generalization of the greedy
algorithm for finding maximal weight spanning trees in a graph [13]. Since
Postnikov’s influential paper [35], polymatroids have also been known as
‘generalized permutahedra’. Investigations from that perspective tend to
emphasize the polyhedral and algebraic geometry of Edmonds’ original polytopal
presentation. We do not examine any connection between this approach and ours.
However, it seems reasonable to hope, indeed expect, that the two lines of
research will eventually intersect.

Our main objective is to demonstrate that the relationship between subspaces
$W$ of a finite vector space ${\mathbb{F}}^{E}$ and their associated matroids
$M[W],$ is similar to a previously unrecognized relationship between
polymatroids and subgroups of a product of finite groups. Given such a $W,$
let $A$ be a matrix whose row space equals $W.$ For $S\subseteq E$ let
$\pi_{S}(W)$ be the projection of $W$ to ${\mathbb{F}}^{S}.$ Since
${\mathbb{F}}$ is finite, $r_{A}(S)$ equals
$\log_{|{\mathbb{F}}|}|\pi_{S}(W)|.$ We can think of $r_{A}$ as a CT-scan of
$W.$ Just as a CT-scan measures how much mass interferes with x-rays from a
variety of projections, $r_{A}$ records how much of $W$ lies in a variety of
projections.

Let us replace ${\mathbb{F}}^{E}$ with a product of finite groups
$\mathcal{G}=\displaystyle\prod_{x\in E}\Gamma_{x},$ and replace $W$ with a
subgroup $\mathcal{H}$ of $\mathcal{G}.$ Fix a real number $b>1.$ Now our
figurative CT-scan of $\mathcal{H}$ consists of the set of logarithms base $b$
of the cardinality of the projections of $\mathcal{H}$ to
$\displaystyle\prod_{x\in S}\Gamma_{x}$ for all $S\subseteq E.$ This
collection of data forms a polymatroid (Theorem 3.1) which we denote by
$P(\mathcal{H},b)$ or $P(\mathcal{H})$ for brevity.

An algebraic characterization of subgroups of a product of two groups goes
back to Goursat’s Lemma [19]. Bauer, Sen and Zvengrowski established algebraic
criteria for subgroups of an arbitrary finite product of groups [4]. Our
purpose here is very different. Most of the paper is devoted to showing
several ways in which $P(\mathcal{H})$ interacts with $\mathcal{H}$ in a
fashion similar to the way $M[W]$ interacts with $W.$ We do this for several
areas where matroids and finite fields meet. The last two are new even for
matroids.

  * •

The class of matroids of the form $M[W]$ as $W$ ranges over all subspaces of
finite ${\mathbb{F}}$-vector spaces is closed under minors. The class of
polymatroids of the form $P[\mathcal{H}]$ as $\mathcal{H}$ ranges over all
subgroups of finite products of a fixed finite group $\Gamma$ is closed under
minors. (Section 4)

  * •

Theorem 7.2 is a Crapo-Rota critical formula for finite groups which is
virtually identical to its finite field counterpart. We use this theorem to
give a uniform critical theorem proof of Helgason’s formula for the number of
proper colorings of a hypergraph in terms of the characteristic polynomial of
an associated polymatroid. We are also led by Theorem 7.2 to a hypergraph
analog of the classical duality between proper colorings and nowhere-zero
flows on graphs. (Theorem 8.4)

  * •

As Whitney showed in [45], if $W^{\perp}$ is the orthogonal complement of $W$
in ${\mathbb{F}}^{E},$ then $M[W^{\perp}]$ is the matroid dual of $M[W].$ We
define a representation-theoretic object, denoted by
${\mathcal{R}}(\mathcal{H}),$ which is a realization of the polymatroid dual
of $P(\mathcal{H})$. Many duality properties of $M[W^{\perp}]$ in the matroid
setting are mimicked by ${\mathcal{R}}(\mathcal{H})$ in the polymatroid
setting. (Section 9)

  * •

Viewed as a linear code, $W^{\perp}$ is the dual code of $W$ and satisfies
Greene’s theorem which relates the Tutte polynomial of $M[W]$ to the weight
enumerator of $W.$ This leads to a simple proof of the famous MacWilliams
identity between the code weight enumerator of $W$ and that of its dual code.
When viewed as a group code, $\mathcal{H}$ and ${\mathcal{R}}(\mathcal{H})$
satisfy an analog of Greene’s theorem which leads to a MacWilliams identity
for $\mathcal{H}$ and ${\mathcal{R}}(\mathcal{H}).$ When $\mathcal{H}$ is a
subgroup of $(\mathbb{Z}/p\mathbb{Z})^{n},~{}p$ a prime, this is the usual
MacWilliams identity. There is also a MacWilliams identity relating the
complete weight enumerators of $\mathcal{H}$ and ${\mathcal{R}}(\mathcal{H})$
[42]. If $\mathcal{H}\leq\Gamma^{E}$ with $\Gamma$ an abelian group, then the
MacWilliams identity for the complete weight enumerator of $\mathcal{H}$ and
${\mathcal{R}}(\mathcal{H})$ is the usual one. (Section 10)

  * •

The elementary abelian $2$-group $(\mathbb{Z}/2\mathbb{Z})^{n}$ acts
coordinate-wise on $\partial CP_{n},$ the boundary of the $n$-dimensional
cross polytope. Let $W$ be a subgroup of $(\mathbb{Z}/2\mathbb{Z})^{n},$ so
$W$ inherits this action. Denote the quotient space $\partial CP_{n}/W$ by
$X_{W}.$ If $M[W]$ has no coloops, then the eigenvalues of the top-dimensional
combinatorial Laplacian applied to $X_{W}$ contains the same information as
the code weight enumerator of the dual code $W^{\perp}$ (Theorem 11.1). A
statement which reduces to this result holds for $\mathcal{H}$ a subgroup of
$\mathcal{G}$ with ${\mathcal{R}}(\mathcal{H})$ substituting for $W^{\perp}$
and a quotient space $X_{\mathcal{H}}$ derived from $\mathcal{G}$ and
$\mathcal{H}$ replacing $\partial CP_{n}.$ (Theorem 11.7)

  * •

The dimension of $H^{n-1}(X_{W};\mathbb{Q})$ equals the characteristic
polynomial of $M[W]^{\ast}$ evaluated at two. The characteristic polynomial of
$P(\mathcal{H},b)^{\ast}$ evaluated at $b$ equals
$H^{n-1}(X_{\mathcal{H}};\mathbb{C}).$ (Theorem 11.10)

A secondary, perhaps more subtle, objective of this paper is the simplicity of
the proof of Theorem 3.1. Anytime subobjects of product spaces are under
consideration, especially in an algebraic setting, there is a possibility that
an interesting polymatroid is hiding in plain sight. For an example, see [5].

By using rank functions which agree with the usual matroid rank functions when
the groups are the additive groups of vector subspaces, our rank functions are
frequently not integers. While this shines a clear light on the similarities
between the polymatroid and matroid settings, it does have the effect of, to a
certain extent, hiding the fundamental integral nature of the objects
involved. In principle, using something along the lines of the Rédei function
of [23] could keep everything in the integers. Whether or not a purely
integral approach leads to better insight or understanding remains to be seen.

##  2 Matroids and polymatroids

In this section we introduce several basic matroid and polymatroid notions.
Other definitions and notation for matroids, polymatroids and other subjects
will appear later as they are needed.

A polymatroid is a pair, $P=(E,r),$ where $E$ is a finite ground set and $r$
is a rank function $r:2^{E}\to\mathbb{R}_{\geq 0}$ such that

  1. P1.

$r(\emptyset)=0.$ (normalization)

  2. P2.

If $S\subseteq T,$ then $r(S)\leq r(T).$ (monotonicity)

  3. P3.

For all $S,T\subseteq E,~{}r(S)+r(T)\geq r(S\cup T)+r(S\cap T).$
(submodularity)

A cryptomorphic definition is obtained by replacing P3 with the axiom of
diminishing returns:

  1. P3’.

For all $S\subseteq T$ and $x\in E,$ $r(S\cup\\{x\\})-r(S)\geq
r(T\cup\\{x\\})-r(T).$

Two polymatroids $P=(E,r)$ and $P^{\prime}=(E^{\prime},r^{\prime})$ are
isomorphic, written $P\cong P^{\prime},$ if there is a rank-preserving
bijection from $E$ to $E^{\prime}.$ Throughout the paper $P=(E,r)$ is a
polymatroid, $n=|E|$, and $[n]=\\{1,\dots,n\\}.$ Often $P$ (and $E$ and $r$)
will be decorated in various ways in order to distinguish explicitly which
polymatroid is under consideration.

A polymatroid is subcardinal if for all $S\subseteq E,r(S)\leq|S|.$ A
subcardinal polymatroid which is integer valued is a matroid. From here on $M$
will be a matroid, frequently decorated to specify which matroid. Matroids
were first defined by Whitney [45]. For a more complete early history of
matroids see [25]. This includes a frequently forgotten contemporaneous
equivalent definition by Nakasawa [29], [30], [31]. Polymatroids were first
introduced by Edmonds as a polytopal generalization of the greedy algorithm
for matroids [13].

The prototypical example of a matroid starts with an $m\times n$ matrix $A$
with coefficients in a field ${\mathbb{F}}.$ The elements of the ground set
$E$ are the columns of $A$ in ${\mathbb{F}}^{m}.$ Distinct columns of $A$ are
distinct elements of $E,$ even if as column vectors in ${\mathbb{F}}^{m}$ they
are identical. The rank $r_{A}(S)$ of a subset $S$ of $E$ is the dimension of
the span of the column vectors in $S.$ A matroid is representable over
${\mathbb{F}}$ if it is isomorphic to $(E,r_{A})$ for some $A.$ In that case
$A$ is a realization of the matroid. Usually we use $M[A]$ to denote
$(E,r_{A}).$

An alternative, but equivalent, approach to matroid representability is
through subspaces. Suppose $W$ is a subspace of ${\mathbb{F}}^{n}.$ If $A$ and
$B$ are two matrices whose row spaces $R(A)$ and $R(B)$ are equal to $W,$ then
$M[A]$ is isomorphic to $M[B]$. Indeed, $A$ and $B$ are connected through a
series of elementary row operations (where inserting or removing a row of
zeros is included as an elementary row operation) and row operations do not
alter column independence relations. In this situation, we will use $M[W]$ to
stand for this isomorphism class of matroids. As with matrices, if $M$ is a
matroid and $M$ is isomorphic to $M[W],$ then $M$ is representable over
${\mathbb{F}},$ and $W$ is a realization of $M.$

Another motivating example for matroids comes from graphs. Given a graph $G,$
let $E(G)$ be the edge set of $G.$ The rank of a subset $S$ of edges of $G$ is
assigned the rank $r_{G}(S)$ equal to the cardinality of the largest acyclic
subset of edges in $S.$ Then $(E(G),r_{G})$ is the cycle matroid of $G$ which
we denote by $M[G].$ In fact, $M[G]$ is equal to $M[A]$ where $A$ is the
following adjacency matrix. First choose an orientation of the edges of $G.$
The columns of $A$ are indexed by edges of $G$ and the rows are indexed by the
vertices of $G.$ The entry of $A$ corresponding to an edge $x$ and vertex $v$
is: $1,$ if $v$ is the head of $x,~{}-1$ if $v$ is the tail of $x,$ and $0$ if
$x$ and $v$ are not incident or $x$ is a loop. Then $A$ is a realization of
$M[G]$ over every field.

A (usually not subcardinal) polymatroid whose rank function is integer-valued
is often referred to as a discrete or integer polymatroid. Some authors define
polymatroids to be integer valued. Another common nomenclature is
$k$-polymatroids for discrete polymatroids such that $k\geq\max_{x\in
E}r(\\{x\\}).$ One way to produce integer polymatroids is to start with a
matroid $M=(E,r)$ and let $\\{T_{1},\dots,T_{n}\\}$ be a multiset of subsets
of $E.$ For $S\subseteq[n]$ define $r^{\prime}(S)$ to be the rank in $M$ of
$\displaystyle\cup_{i\in S}T_{i}.$ Then $P=([n],r^{\prime})$ is a polymatroid.
In fact, all integer polymatroids are isomorphic to such a construction [34,
Theorem 11.1.9]. In this case, $P$ is constructed from $M$ and
$\\{T_{1},\dots,T_{n}\\}.$ When there is no cause for confusion, the reference
to $\\{T_{1},\dots,T_{n}\\}$ is omitted. An integer polymatroid $P$ is
representable over a field ${\mathbb{F}}$ if there exists a matrix $A$ with
coefficients in ${\mathbb{F}}$ such that $P$ is constructed from $M[A].$ In
this case $A$ (and $\\{T_{1},\dots,T_{n}\\}$) is a realization of $P.$ In a
fashion similar to matroids, representability of polymatroids over a field
${\mathbb{F}}$ can be approached using a subspace $W$ of ${\mathbb{F}}^{m},$
where $m=\displaystyle\sum^{n}_{i=1}r(\\{i\\}),$ and choosing a basis of $W$
to be the rows of $A.$

As for matroids, a flat of a polymatroid $P$ is a subset $S$ of $E$ such that
for all $x$ not in $S,~{}r(S\cup\\{x\\})>r(S).$ The poset of the flats of a
polymatroid ordered by inclusion forms a lattice, called the lattice of flats
of $P$, with meet being intersection. In fact, any finite lattice is the
lattice of flats of a polymatroid. One can even insist that the polymatroid be
one constructed from $M[K_{n}],$ where $K_{n}$ is the complete graph on $n$
vertices. See [36] for a description and history of this result. We will use
$\mathcal{L}_{P}$ to represent the lattice of flats of the polymatroid $P.$

There is a polymatroid analog of the characteristic polynomial of a matroid.
However, unless the polymatroid is discrete, it is generally not a polynomial.
Despite this, we will still call it the characteristic polynomial  of a
polymatroid. It is defined completely analogously to the definition of the
characteristic polynomial of a matroid.

${\chi}_{P}(t)=\displaystyle\sum_{S\subseteq E}(-1)^{|S|}t^{r(E)-r(S)}.$

The characteristic polynomial of a polymatroid $P$ has many properties in
common with its matroid counterpart. For instance, the characteristic
polynomial of $P$ is the zero function if $P$ has an element $x\in E$ such
that $r(\\{x\\})=0.$ Such an element is called a loop. There is also a formula
for ${\chi}_{P}$ based on the Möbius function $\mu_{P}$ of $\mathcal{L}_{P}$
that is identical to the usual matroid definition.

###### Proposition 2.1

If $P$ has a loop, then ${\chi}_{P}\equiv 0.$ If $P$ does not contain a loop,
then

${\chi}_{P}(t)=\displaystyle\sum_{S\in\mathcal{L}_{P}}\mu_{\mathcal{L}_{P}}(\emptyset,S)t^{r(E)-r(S)}.$

Proof:  The same proof as for matroids works here. See, for instance, [50,
Proposition 7.2.1]. $\square$

##  3 From finite groups to polymatroids

The notation in this paragraph will be used in the remainder of the paper. For
all $x\in E,~{}\Gamma_{x}$ is a finite group. In general, $\Gamma_{x}$ may or
may not be isomorphic to $\Gamma_{y}.$ In addition,
$\mathcal{G}=\displaystyle\prod_{x\in E}\Gamma_{x},$ and $\mathcal{H}$ is a
subgroup of $\mathcal{G}.$ For $S\subseteq
E,~{}\mathcal{G}_{S}=\displaystyle\prod_{x\in S}\Gamma_{x}$ and $\pi_{S}$ is
the projection map $\pi_{S}:\mathcal{G}\to\mathcal{G}_{S}.$ We denote the
image $\pi_{S}(\mathcal{H})$ by $\mathcal{H}_{S}.$ By convention,
$\mathcal{G}_{\emptyset}$ and $\mathcal{H}_{\emptyset}$ are the trivial
groups.

The connection between a subgroup $\mathcal{H}\leq\mathcal{G}$ and
polymatroids is through a rank function. Choose $b>1,b\in\mathbb{R}.$ For all
$S\subseteq E$ define

$r_{\mathcal{H},b}(S)\equiv\log_{b}|\mathcal{H}_{S}|.$ (1)

Different choices of $b$ lead to rank functions which differ by a constant.
Indeed,

$r_{\mathcal{H},b}=\frac{\ln b^{\prime}}{\ln b}r_{\mathcal{H},b^{\prime}}.$

###### Theorem 3.1

The pair $(E,r_{\mathcal{H},b})$ is a polymatroid.

Proof:  Normality and monotonicity are evident, so let us check the law of
diminishing returns for $S\subseteq T\subseteq E.$ If $x\in T$ then, (3’) is
automatically satisfied, so assume that $x\notin T.$ In general, for any
$S\subseteq E,$

$r_{\mathcal{H},b}(S\cup\\{x\\})-r_{\mathcal{H},b}(S)=\log_{b}\frac{|\mathcal{H}_{S\cup\\{x\\}}|}{|\mathcal{H}_{S}|}=\log_{b}|\ker\pi_{S}:\mathcal{H}_{S\cup\\{x\\}}\to\mathcal{H}_{S}|.$
(2)

Let $\mathcal{K}_{S}$ be
$\ker\pi_{S}:\mathcal{H}_{S\cup\\{x\\}}\to\mathcal{H}_{S}$ and
$\mathcal{K}_{T}$ be
$\ker\pi_{T}:\mathcal{H}_{T\cup\\{x\\}}\to\mathcal{H}_{T}.$ Since $S\subseteq
T,~{}\pi_{S\cup\\{x\\}}:\mathcal{G}_{T\cup\\{x\\}}\to\mathcal{G}_{S\cup\\{x\\}}$
becomes an injection $\pi_{S\cup\\{x\\}}:\mathcal{K}_{T}\to\mathcal{K}_{S}$
when restricted to $\mathcal{K}_{T}.$ Hence
$|\mathcal{K}_{T}|\leq|\mathcal{K}_{S}|$ as required. $\square$

We will use $P(\mathcal{H},b)$ to denote the polymatroid
$(E,r_{\mathcal{H},b}).$ Most of the time $b$ is understood or not relevant,
so we suppress it and use $P(\mathcal{H}).$

###### Example 3.2

Let $E=[n]$ and for all $1\leq i\leq
n,~{}\Gamma_{i}=\mathbb{Z}/p\mathbb{Z},~{}p$ a fixed prime, and
$\mathcal{G}=(\mathbb{Z}/p\mathbb{Z})^{n}.$ A subgroup $\mathcal{H}$ of
$\mathcal{G}$ is a also a subspace of the vector space $\mathcal{G}$ over
${\mathbb{F}}=\mathbb{Z}/p\mathbb{Z}.$ Then, with $b=p,~{}P(\mathcal{H})$ is a
matroid and is isomorphic to $M[\mathcal{H}].$

In principle, the definition of $r_{\mathcal{H},b}$ makes sense for any
collection of sets $\\{\Lambda_{x}\\}$ indexed by $E$ and finite subset
$\mathcal{H}$ of $\prod_{x\in E}{\Lambda}_{x}.$ It is not clear what sort of
structure is needed on the $\mathcal{H}$ and the $\Lambda_{x}$ to guarantee
that $r_{\mathcal{H},b}$ is submodular. What is clear is that some structure
is needed.

###### Example 3.3

Let $\Lambda_{1}=\Lambda_{2}=\Lambda_{3}=\\{1,2\\},E=\\{1,2,3\\},$ and
$L\subseteq\Lambda_{1}\times\Lambda_{2}\times\Lambda_{3}$ be

$L=\\{(2,2,2),(2,1,2),(1,1,2),(1,1,1),(2,1,1)\\}.$

Then $|L_{\\{1,2\\}}|\cdot|L_{\\{2,3\\}}|=3\cdot
3<|L_{\\{1,2,3\\}}|\cdot|L_{\\{2\\}}|=5\cdot 2.$ Hence $r_{L,b}$ is not
submodular for all $b.$

##  4 Representability

Throughout Sections 4, 5 and 6 we will be assuming that all of the
$\Gamma_{x}$ are isomorphic to a fixed finite group $\Gamma$ and that
$b=|\Gamma|.$ Consequently we will suppress all appearances of $b$ from the
notation. In this section we introduce the definition of a polymatroid being
representable over a finite group that is analogous to matroid
representability over a field.

###### Definition 4.1

A polymatroid $P=(E,r)$ is representable over a finite group $\Gamma$ if there
exists a finite set $E^{\prime}$ and subgroup $\mathcal{H}$ of
$\Gamma^{E^{\prime}}$ such that $P$ is isomorphic to $P(\mathcal{H}).$ In this
case, $\mathcal{H}$ is a $\Gamma$-realization of $P.$

If $\Gamma=\mathbb{Z}/p\mathbb{Z},~{}p$ a prime, then Example 3.2 shows that a
polymatroid $P$ is representable over the group $\mathbb{Z}/p\mathbb{Z}$ if
and only if it is representable over the field $\mathbb{Z}/p\mathbb{Z}.$ In
both cases, $P$ must actually be a matroid. Another way that polymatroid
realizability over a group mirrors matroid realizability over a field is that
it is closed under deletion, contraction and hence minors.

Given $S\subseteq E$ the deletion of $S$ from $P$ is the polymatroid
$P\setminus S$ with ground set $E-S$ and rank function equal to $r$ restricted
to the subsets of $E-S.$ If $\mathcal{H}$ is a $\Gamma$-realization of $P,$
then $\mathcal{H}_{E-S}$ is a $\Gamma$-realization of $P\setminus S.$

Another polymatroid with ground set $E-S$ is $P/S,$ the contraction of $P$ by
$S.$ For $T\subseteq E-S,$ the rank function of $P/S$ is

$r_{P/S}(T)=r(S\cup T)-r(S).$

If $\mathcal{H}$ is a realization of $P$, then
$\mathcal{K}=\pi_{E-S}(\ker\pi_{S})$ is a realization of $P/S.$ To see this,
let $T\subseteq E-S.$ Then $\pi_{T}$ is an isomorphism between
$\mathcal{K}_{T}$ and $\ker\pi_{S}:\mathcal{H}_{S\cup T}\to\mathcal{H}_{S}.$
Since $\pi_{S}$ is a surjection,

$|\mathcal{K}_{T}|=|\ker\pi_{S}:\mathcal{H}_{S\cup
T}\to\mathcal{H}_{S}|=\frac{|\mathcal{H}_{S\cup T}|}{|\mathcal{H}_{S}|}.$

Minors of polymatroids are defined as they are for matroids. A minor of a
polymatroid $P$ is a polymatroid $Q$ that can be obtained from $P$ by a
sequence of deletions and/or contractions. Let $\mathcal{C}(\Gamma)$ be the
isomorphism classes of polymatroids representable over $\Gamma.$ The above
discussion shows that $\mathcal{C}(\Gamma)$ is closed under minors. Let
$\mathcal{C}$ be a class of polymatroids. We say $\mathcal{C}$ is minor closed
if $\mathcal{C}$ is closed under isomorphism and minors. An excluded minor of
$\mathcal{C}$ is a polymatroid $P$ such that $P\notin\mathcal{C},$ but every
deletion and contraction of $P$ is in $\mathcal{C}.$ Minor closed classes of
polymatroids can be described by listing their excluded minors. Before
discussing excluded minors for $\mathcal{C}(\Gamma)$ we consider excluded
minors for matroids representable over $\Gamma.$

##  5 Matroid representability

In this section we restrict our attention to representability of matroids over
a finite group $\Gamma.$ We denote the class of matroids representable over
$\Gamma$ by $\mathcal{C}^{Ma}(\Gamma).$ For instance, the polymatroid
$P=(\\{1,2,3,4\\},r)$ with $r(S)=\min(1,|S|/2)$ is an excluded minor for
$\mathcal{C}(\mathbb{Z}/4\mathbb{Z}),$ but is not a matroid and hence not an
excluded minor for $\mathcal{C}^{Ma}(\mathbb{Z}/4\mathbb{Z}).$

Given nonnegative integers $d\leq n,$ the uniform matroid $U_{d,n}$ is the
matroid with ground set $[n]$ and rank function $r(S)=\min(d,|S|).$ Two
distinct elements $\\{x,y\\}$ in a polymatroid $P=(E,r)$ are parallel if
$0<r(\\{x\\})=r(\\{y\\})=r(\\{x,y\\}).$ Diminishing returns (P3’) implies that
the relation ‘is parallel to’ is an equivalence relation and the equivalence
classes are called the parallel classes of the polymatroid. The simplification
of a matroid is the matroid obtained by deleting all loops and all but one
element of every parallel class.

The unique excluded minor for $\mathcal{C}^{Ma}(\Gamma)$ when $\Gamma$ is a
nonabelian group is $U_{2,3}.$ Specifically, we have the following result.

###### Theorem 5.1

Let $\Gamma$ be a nonabelian group. Then the following are equivalent for a
matroid $M.$

  1. 1.

$M\in\mathcal{C}^{Ma}(\Gamma)$.

  2. 2.

$M$ does not have $U_{2,3}$ as a minor.

  3. 3.

The simplification of $M$ is $U_{n,n}$ for some $n,$ or $M$ consists entirely
of loops.

  4. 4.

$M$ is representable over every finite group.

Proof:

(1) implies (2): To avoid confusion with too many numerals, we use
$E=\\{x,y,z\\}$ as the ground set of $U_{2,3}.$ Suppose $\mathcal{H}$ is a
subgroup of $\Gamma_{x}\times\Gamma_{y}\times\Gamma_{z}$ so that
$P(\mathcal{H})$ is isomorphic to $U_{2,3}.$ Let $\gamma$ and
$\gamma^{\prime}$ be elements of $\Gamma$ which do not commute. Since
$r(\\{x,y\\})=2=r(\\{x,y,z\\})$ we know that $\mathcal{H}_{\\{x,y\\}}$ is
$\Gamma_{x}\times\Gamma_{y}$ and for every ordered pair
$(\gamma_{x},\gamma_{y})\in\Gamma_{x}\times\Gamma_{y}$ there exists a unique
$\gamma_{z}\in\Gamma_{z}$ such that
$(\gamma_{x},\gamma_{y},\gamma_{z})\in\mathcal{H}.$ Applying the same
reasoning to $(1_{\Gamma},\gamma)\in\Gamma_{x}\times\Gamma_{z}$ and
$(1_{\Gamma},\gamma^{\prime})\in\Gamma_{y}\times\Gamma_{z},$ there exist
triples $(1_{\Gamma},\gamma_{y},\gamma)$ and
$(\gamma_{x},1_{\Gamma},\gamma^{\prime})$ in $\mathcal{H}.$ But this implies
that $(\gamma_{x},\gamma_{y},\gamma\cdot\gamma^{\prime})$ and
$(\gamma_{x},\gamma_{y},\gamma^{\prime}\cdot\gamma)$ are both in
$\mathcal{H},$ a contradiction.

(2) implies (3) is a matroid exercise.

(3) implies (4): A set of $n$ loops can be realized via $\mathcal{H}$ equal to
the trivial subgroup of $\mathcal{G}=\Gamma^{n}.$ If we let
$\mathcal{H}=\mathcal{G}=\Gamma^{n},$ then $([n],r_{\mathcal{H}})$ is
isomorphic to $U_{n,n}.$ Now suppose
$\mathcal{H}\subseteq\mathcal{G}=\Gamma^{E}$ realizes a matroid $M.$ To
realize $M$ with a loop added, let $E^{\prime}$ be $E$ with a new element $y$
included. For all $h\in\mathcal{H},$ define $h^{\prime}\in\Gamma^{E^{\prime}}$
by $h^{\prime}_{x}=h_{x}$ for $x\in E$ and $h^{\prime}_{y}=1_{\Gamma}.$ Then
$\mathcal{H}^{\prime}=\\{h^{\prime}:h\in\mathcal{H}\\}$ realizes $M$ with a
loop added. Similarly, a new element parallel to $x\in E$ can be adjoined to
the matroid represented by $\mathcal{H}$ by introducing a new coordinate $y$
and setting it equal to the $x$ coordinate for all $h\in\mathcal{H}.$

(4) implies (1) is immediate.

$\square$

Determining the excluded minors for matroids representable over
$\mathbb{Z}/p\mathbb{Z}$ for $p$ a prime has been a critical motivating
problem for decades. See for instance, [34], and the announcement of a proof
of Rota’s conjecture that there are a finite number of excluded minors for
matroids realizable over any fixed finite field [18].

A totally unimodular matrix is a real matrix all of whose subdeterminants are
$-1,0$ or $1.$ In particular, all of the entries of the matrix are $-1,0$ or
$1.$ A matroid $M$ is regular if there exists a totally unimodular matrix $A$
such that $M$ is isomorphic to $M[A].$ The Fano matroid is the matroid
realized over $\mathbb{Z}/2\mathbb{Z}$ by the matrix whose columns are the
seven nonzero vectors of $(\mathbb{Z}/2\mathbb{Z})^{3}.$ The dual of the Fano
is the matroid realized over $\mathbb{Z}/2\mathbb{Z}$ by the subspace of
$(\mathbb{Z}/2\mathbb{Z})^{7}$ which is orthogonal to the row space of the
Fano. See Section 8 for an explanation for the term dual. The following
excluded minor characterization of regular matroids is originally due to
Tutte.

###### Theorem 5.2

[41] For a matroid $M$ the following are equivalent.

  * •

$M$ is a regular matroid.

  * •

$M$ does not have $U_{2,4},$ the Fano or the dual of the Fano as a minor.

  * •

$M$ is representable over the field $\mathbb{Z}/2\mathbb{Z}$ and a field
${\mathbb{F}}$ whose characteristic is not two.

  * •

$M$ is representable over all fields.

Here are two results for non prime cyclic groups whose proofs will appear in
[43].

###### Theorem 5.3

If $n$ is even and greater than two, then $M$ is representable over
$\mathbb{Z}/n\mathbb{Z}$ if and only if $M$ is regular.

###### Theorem 5.4

If $n=ml,~{}m$ and $l$ relatively prime, then a matroid $M$ is representable
over $\mathbb{Z}/n\mathbb{Z}$ if and only if it is representable over
$\mathbb{Z}/m\mathbb{Z}$ and $\mathbb{Z}/l\mathbb{Z}.$

The following two theorems follow immediately from Theorem 5.4 and the main
results of [47].

###### Theorem 5.5

A matroid $M$ is representable over $\mathbb{Z}/3p\mathbb{Z},~{}p$ an odd
prime congruent to $2\mod 3,$ if and only if $M$ is realized by a rational-
valued matroid all of whose nonzero subdeterminants are of the form $\pm
2^{j},j\in\mathbb{Z}.$

###### Theorem 5.6

A matroid $M$ is representable over $\mathbb{Z}/3p\mathbb{Z},~{}p$ a prime
congruent to $1\mod 3,$ if and only if $M$ is realized by a complex-valued
matroid all of whose nonzero subdeterminants are sixth-roots of unity.

##  6 Polymatroid representability

As in the last section, $\Gamma$ is a fixed finite group and
$\mathcal{G}=\Gamma^{n}.$ Several of the proofs and further discussion will
appear in [43].

Does it make sense to ask if $\Gamma$-representable polymatroids have a finite
list of excluded minors? One trivial answer is ‘no’. Any polymatroid with
exactly one element whose rank is a positive real number $s$ less than one is
a minimal excluded minor for $\Gamma$-representability whenever $s^{|\Gamma|}$
is not an integer which divides $|\Gamma|.$ However, this does not capture the
same point of view as matroids, even when $\Gamma=\mathbb{Z}/p\mathbb{Z}$ and
$\Gamma$-representability over polymatroids is the same as
$\Gamma$-representability for matroids. One possible approach of describing
polymatroid representability over $\Gamma$ in a way that does mimic matroid
representability is the following.

###### Definition 6.1

A polymatroid $P=(E,r)$ is $\Gamma$-possible  if for all $S\subseteq
E,~{}|\Gamma|^{r(S)}$ is an integer which divides $|\Gamma|^{|S|}.$

###### Remark 6.2

Stronger requirements could reasonably be imposed on the definition of
$\Gamma$-possible polymatroids. For instance, since $\mathcal{C}(\Gamma)$ is
closed under contraction, if $P\in\mathcal{C}(\Gamma),$ then for all
$S\subseteq T,~{}|\Gamma|^{r(T-S)}$ divides $|\Gamma|^{|T-S|}.$

By restricting our attention to $\Gamma$-possible polymatroids it is now
possible for there to be a finite list of excluded minors for $\Gamma.$
Matroids are $\Gamma$-possible for any $\Gamma.$ More importantly, if $P$ is
$\Gamma$-representable, then $P$ is $\Gamma$-possible. If $|\Gamma|$ is a
prime power $p^{k},$ then the class of polymatroids which are
$\Gamma$-possible is the class of all subcardinal polymatroids $P$ such that
all ranks are rationals of the form $j/k,~{}j\in\mathbb{Z}_{\geq 0}.$ In this
case, $P$ is $\Gamma$-possible if and only if $kP=(E,kr)$ is a
$k$-polymatroid. The particular case of representability over an elementary
abelian $p$-group, $\Gamma=(\mathbb{Z}/p\mathbb{Z})^{k},$ has already been
considered under the guise of $k$-polymatroid representability over the field
$\mathbb{Z}/p\mathbb{Z}.$

###### Proposition 6.3

Let $p$ be a prime. Then a $k$-polymatroid $P$ is representable over the
_field_ $(\mathbb{Z}/p\mathbb{Z})$ if and only if $(1/k)P$ is representable
over the _group_ $(\mathbb{Z}/p\mathbb{Z})^{k}.$

In [33] Oxley, Semple and Whittle prove that when $k\geq 2$ there are
infinitely many excluded minors for $k$-polymatroids over any prime field
$\mathbb{Z}/p\mathbb{Z}.$ Combining this with the previous proposition gives
us the following result.

###### Theorem 6.4

Let $p$ be a prime and $k\geq 2.$ Then $(\mathbb{Z}/p\mathbb{Z})^{k}$ has
infinitely many excluded minors among $(\mathbb{Z}/p\mathbb{Z})^{k}$-possible
polymatroids.

The classical notion of equivalence of realizations of a matroid over a field
can be extended to realizations of polymatroids over finite groups. Two
matrices $A$ and $B$ with coefficients in a field ${\mathbb{F}}$ are
equivalent realizations of a matroid $M$ if $M\cong M[A]\cong M[B]$ and $A$
can be obtained from $B$ by a sequence of one or more of the following
operations.

  * •

A permutation of the columns of the matrix.

  * •

Multiplying a column by a nonzero scalar.

  * •

An elementary row operation. (Including insertion or removal of a row of
zeros.)

  * •

Applying a field automorphism $\theta:{\mathbb{F}}\to{\mathbb{F}}$ to every
entry of the matrix.

Since elementary row operations do not change row spaces, equivalence of
realizations of a matroid by subspaces can be described as follows. Two
subspaces $U$ and $V$ of ${\mathbb{F}}^{E}$ are equivalent realizations of a
matroid $M$ if $M\cong M[U]\cong M[V]$ and $U$ can be obtained from $V$ by a
sequence of one or more of the following operations.

  * •

A permutation of the coordinates.

  * •

Fix $x\in E$ and multiply every $x$-coordinate of $v\in V$ by a fixed nonzero
scalar $c_{x}\in{\mathbb{F}}.$

  * •

Apply a fixed field automorphism $\theta:{\mathbb{F}}\to{\mathbb{F}}$ to all
coordinates of all $v\in V.$

Our approach to equivalence of realizations of polymatroids by groups can be
reduced to two operations. Suppose $\mathcal{H}$ and $\mathcal{H}^{\prime}$
are two realizations of $P.$ Then $\mathcal{H}$ and $\mathcal{H}^{\prime}$ are
equivalent realizations if $\mathcal{H}^{\prime}$ can be obtained from
$\mathcal{H}$ by a sequence of the following two operations.

  * •

A permutation of the coordinates.

  * •

Apply a group automorphism $\theta:\Gamma\to\Gamma$ to one coordinate.

When $p$ is a prime there are no nontrivial field automorphisms of
$\mathbb{Z}/p\mathbb{Z}$ and all group automorphisms of
$\mathbb{Z}/p\mathbb{Z}$ are multiplication by a nonzero scalar. Hence the
definition of equivalent realizations of matroids realizable over
$\mathbb{Z}/p\mathbb{Z}$ as a field and a group coincide. One of the basic
facts of matroid theory is that all subspace realizations of matroids over
$\mathbb{Z}/2\mathbb{Z}$ are equivalent. The same holds for
$\mathbb{Z}/3\mathbb{Z}.$ However, for primes $p\geq 5,$ and some matroids $M$
representable over $\mathbb{Z}/p\mathbb{Z},$ there are many nonequivalent
realizations of $M.$

###### Theorem 6.5

If $\mathcal{H}$ and $\mathcal{H}^{\prime}$ are realizations of a polymatroid
$P$ over $\mathbb{Z}/4\mathbb{Z},$ then $\mathcal{H}$ and
$\mathcal{H}^{\prime}$ are equivalent.

A proof of Theorem 6.5 can be based on the presentation in [34] of the unique
representability of regular matroids.

###### Theorem 6.6

If $\mathcal{H}$ and $\mathcal{H}^{\prime}$ are realizations of a polymatroid
$P$ over $\mathbb{Z}/6\mathbb{Z},$ then $\mathcal{H}$ and
$\mathcal{H}^{\prime}$ are equivalent.

The main idea behind our proofs of Theorems 5.3, 5.4 and 6.6 is to use the
fact that unlike fields, groups can have endomorphisms which are neither
trivial nor automorphisms. Here is an example where this idea is applied to
polymatroid representability.

Suppose $\Gamma$ is the direct sum of two groups $\Gamma_{1}$ and $\Gamma_{2}$
whose orders are relatively prime, and $P$ is a $\Gamma$-possible polymatroid.
Then for any $S\subseteq E,~{}|\Gamma^{r(S)}|$ can be written uniquely as a
product $a(S)b(S),$ where $a(S)$ divides $|\Gamma_{1}|^{|S|}$ and $b(S)$
divides $|\Gamma_{2}|^{|S|}.$ Let $r_{1}$ and $r_{2}$ be the set functions
defined by $r_{1}(S)=\log_{|\Gamma_{1}|}a(S)$ and
$r_{2}(S)=\log_{|\Gamma_{2}|}b(S).$ Even if $P$ is $\Gamma$-possible
$(E,r_{1})$ and/or $(E,r_{2})$ may not be polymatroids.

###### Theorem 6.7

With the above assumptions and notation, $P$ is representable over $\Gamma$ if
and only if $(E,r_{1})$ is a representable polymatroid over $\Gamma_{1}$ and
$(E,r_{2})$ is a representable polymatroid over $\Gamma_{2}.$

##  7 Critical theorem for finite groups

One of the cornerstones of enumerative matroid theory is Crapo and Rota’s
critical theorem. The characteristic polynomial of a matroid occurs in
applications with astonishing frequency and many times the reason can be
traced back to the ideas behind this result. Here we establish a finite group
analog of the critical theorem. When $\mathcal{G}$ is the additive group of a
vector space and $\mathcal{H}$ is the additive group of a subspace of that
vector space, Theorem 7.2 below is equivalent to Crapo and Rota’s original
result.

A forerunner of Theorem 7.2 and its dual, Theorem 9.16 below, for abelian
groups is in Section 6 of a paper by Kung, Murty and Rota [23]. Indeed, with
enough translation from the Rédei functions in [23] to the rank functions
here, one can view Theorem 7.2 applied to abelian groups as a special case of
[23, Theorem 10].

The classical Crapo-Rota critical theorem is usually given in a coordinate-
free form. Let $E=\\{v_{1},\dots,v_{n}\\}$ be vectors in a finite vector space
$V$ over a (finite) field ${\mathbb{F}},~{}W$ the span of $E,$ and
$s=\dim_{\mathbb{F}}W.$ Then the Crapo-Rota critical theorem says that the
number of $k$-tuples $(l_{1},\dots,l_{k})\in(V^{\ast})^{k}$ such that
$E\cap\ker l_{1}\cap\cdots\cap\ker l_{k}=\emptyset$ is
$|{\mathbb{F}}|^{k(n-s)}{\chi}_{M[W]}(|{\mathbb{F}}|^{k}).$ It is a linear
algebra exercise to recognize that this is equivalent to Theorem 7.1 which
relates the zero sets of row vectors of a matrix $A$ whose coefficients are in
a finite field ${\mathbb{F}},$ to the characteristic polynomial of the matroid
$M[A].$

Let $A$ be an $m\times n$ matrix with row space $R(A).$ For
$w=(w_{1},\dots,w_{n})\in R(A)$ define the zero set of $w$ to be
$Z(w)=\\{i:w_{i}=0\\}.$

###### Theorem 7.1

[8] Let $A$ be an $m\times n$ matrix with coefficients in a finite field
${\mathbb{F}}.$ Then

${\chi}_{M[A]}(|{\mathbb{F}}|^{k})=|\\{(u_{1},\dots,u_{k})\in
R(A)^{k}:Z(u_{1})\cap\cdots\cap Z(u_{k})=\emptyset\\}|.$ (3)

For the remainder of this section we no longer assume that all the
$\Gamma_{x}$ are isomorphic. We will continue to suppress $b$ from the
notation with the understanding that $b$ can be any fixed real number greater
than one. To state the analog of Theorem 7.1 for groups and polymatroids we
substitute $\mathcal{H}\leq\mathcal{G}$ for the row space and define an analog
of $Z(w)$. For $h\in\mathcal{H}$ let $I(h)=\\{x\in E:h_{x}=1_{\Gamma_{x}}.\\}$
So, if $A$ is a matrix with coefficients in
${\mathbb{F}},~{}\mathcal{H}=R(A),$ and for all $x\in E,~{}\Gamma_{x}$ is the
additive group of ${\mathbb{F}},$ then $I(h)=Z(h).$

###### Theorem 7.2

(Crapo-Rota for finite groups) Suppose $\mathcal{H}$ is a subgroup of
$\mathcal{G}$ which realizes the polymatroid $P.$ Then

${\chi}_{P}(b^{k})=|\\{(h_{1},\dots,h_{k})\in\mathcal{H}^{k}:\displaystyle\bigcap^{k}_{j=1}I(h_{j})=\emptyset\\}|.$
(4)

Observe that if $\Gamma_{x}$ is the additive group of a fixed finite field
${\mathbb{F}}$ for every $x,$ and $b=|{\mathbb{F}}|,$ then Theorem 7.2 becomes
Theorem 7.1.

Our proof of this theorem closely follows the usual Möbius inversion proof of
the Crapo-Rota critical theorem. To prepare for this, we start by
demonstrating several ways that $I(h)$ for realized polymatroids is similar to
$Z(w)$ for realized matroids. The next corollary and two propositions are
polymatroid analogs of standard properties of realized matroids.

###### Corollary 7.3

If $h\in\mathcal{H},$ then $S=I(h)$ is a flat of $P(\mathcal{H}).$

Proof:  If $x\notin S,$ then $h$ is a nontrivial element of
$\ker\pi_{S}:\mathcal{H}_{S\cup\\{x\\}}\to\mathcal{H}_{S}.$ Hence (2) shows
that $r_{\mathcal{H}}(S\cup\\{x\\})-r_{\mathcal{H}}(S)>0.$ $\square$

###### Proposition 7.4

If $S$ is a coatom of $\mathcal{L}_{P(\mathcal{H})},$ then there exists
$h\in\mathcal{H}$ such that $I(h)=S.$

Proof:  Let $S$ be a coatom of $\mathcal{L}_{P(\mathcal{H})}$ and set
$\mathcal{H}^{\prime}=\ker\pi_{S}:\mathcal{H}\to\mathcal{H}_{S}.$ Since
$\pi_{E-S}\mathcal{H}^{\prime}$ is a realization of
$P(\mathcal{H})/S,~{}\mathcal{H}^{\prime}$ is not the trivial group. Now, any
$h^{\prime}\in\mathcal{H}^{\prime}$ which is not the identity must satisfy
$I(h^{\prime})=S.$ $\square$

###### Proposition 7.5

If $S$ is a flat of $P$ then there exists
$\\{h_{1},\dots,h_{l}\\},~{}l\leq|E-S|,$ such that
$S=\displaystyle\cap^{l}_{i=1}I(h_{i}).$

Proof:  Let $x\in E-S.$ Since $S$ is a flat, $x$ is not a loop of
$P(\mathcal{H})/S.$ Therefore, there exists
$h\in\ker\pi_{S}:\mathcal{H}\to\mathcal{H}_{S}$ such that $h_{x}\neq
1_{\Gamma}.$ For each $x\in E-S$ choose such an $h$ and denote it by $h(x).$
Then

$S=\bigcap_{x\in E-S}I(h(x))$

as required. $\square$

Proof:  (of Theorem 7.2) The proof follows the same pattern as the usual
Möbius inversion proof of the Crapo-Rota critical theorem for finite fields.
If $x$ is a loop of $P$, then for all
$h\in\mathcal{H},~{}h_{x}=1_{\Gamma_{x}}$ and both sides of (4) are zero.

So assume that $P$ has no loops. Thus the empty set is a flat of
$\mathcal{L}_{P(\mathcal{H})}$ and we can apply Proposition 2.1 when needed
later. Since $I(h)$ is always a flat of $P$, and the flats of $P$ are closed
under intersection, we can define
$\phi:\mathcal{H}^{k}\to\mathcal{L}_{P(\mathcal{H})}$ by
$\phi(h_{1},\dots,h_{k})=I(h_{1})\cap\cdots\cap I(h_{k}).$ Now let
$f:\mathcal{L}_{P(\mathcal{H})}\to\mathbb{Z}_{\geq 0}$ be defined by
$f(S)=|\phi^{-1}(S)|$. Then $\displaystyle\sum_{T\supseteq S}f(T)$ is the
number of $(h_{1},\dots,h_{k})\in\mathcal{H}^{k}$ with
$(h_{i})_{x}=1_{\Gamma_{x}}$ for all $1\leq i\leq k$ and $x\in S.$ This is

$|\ker\pi_{S}:\mathcal{H}\to\mathcal{H}_{S}|^{k}=\bigg{(}\frac{|\mathcal{H}|}{|\mathcal{H}_{S}|}\bigg{)}^{k}=(b^{r(E)-r(S)})^{k}=(b^{k})^{r(E)-r(S)}.$

Lemma 2.1 and Möbius inversion finish the proof.

$\square$

In [21] Helgason used Möbius inversion to prove that the classical
relationship between the chromatic polynomial of a graph and the
characteristic polynomial of the cycle matroid of the graph extends to
hypergraph coloring and the characteristic polynomial of a related
polymatroid. Later, Whittle provided a deletion/contraction proof of the same
result [46]. Whittle also shows how to relate this to a polymatroid version of
the Crapo-Rota critical theorem for polymatroids representable over a field
whenever the number of colors is a prime power. In addition, he discusses how
to extend these ideas to an arbitrary number of colors by using Dowling
geometries. Here we use Theorem 7.2 to relate hypergraph coloring to critical
problems over groups for any number of colors. In section 8 we will use
Theorem 7.2 to establish a hypergraph analog of the usual duality between
nowhere-zero flows and proper colorings for graphs.

A hypergraph is a pair $H=(E,V)$ consisting of a finite vertex set $V$ and a
finite multiset of hyperedges $E.$ Each hyperedge is a finite multiset of $V.$
When necessary we write $E(H)$ and $V(H)$ for the hyperedges and vertices of
$H$. We will use $|x|$ to indicate the cardinality of a hyperedge $x$ as a
multiset. So, if $x=\\{a,a,b,b,b,c\\},$ then $|x|=6.$ Given an undirected
graph $G$ we can associate a cryptomorphic hypergraph $H(G)$ whose vertices
are the vertices of the graphs, loops based at a vertex $\\{a\\}$ are listed
as a hyperedge $\\{a,a\\},$ and edges with distinct incident vertices $a$ and
$b$ are listed as hyperedges $\\{a,b\\}$ as many times as there are edges in
$G$ with end points $a$ and $b.$

We associate two different graphs to a hypergraph $H.$ The first graph
attached to $H$ is a union of star-like multigraphs and is denoted by
$\mathcal{SG}(H).$ The vertices of $\mathcal{SG}(H)$ are equal to the vertices
of $H.$ To enumerate the edges of $\mathcal{SG}(H)$ we first define a set of
edges $E(x)$ for every $x\in E.$ Given a hyperedge $x$ of $H$ choose one
vertex $v_{x}$ in $x.$ If $v\neq v_{x}$ has multiplicity $s$ in $x,$ then
$E(x)$ has $s$ parallel edges whose end points are $v$ and $v_{x}.$ The set of
edges in $E(x)$ also contains $t-1$ loops where $t$ is the multiplicity of
$v_{x}$ in $x.$ Hence, the total number of edges in $E(x)$ is $|x|-1.$ The set
of edges of $\mathcal{SG}(H)$ is the union of all of the $E(x).$ Thus the
total number of edges in $\mathcal{SG}(H)$ is $\displaystyle\sum_{x\in
E}|x|-1.$ See Figure 1 and Figure 2 for an example of $\mathcal{SG}(H).$ If
$H$ is equal to $H(G)$ for a graph $G,$ then $\mathcal{SG}(H)=G.$

The second graph we associate to $H$ is the usual bipartite graph which
contains the same information as $H.$ We hold off its description until we
need it in Section 8.

For the remainder of this section $\Gamma$ is a finite abelian group. A proper
$\Gamma$-coloring of a hypergraph $H$ is a map $\phi:V\to\Gamma$ so that for
all $x\in E$ there exist vertices $a,b$ in $x$ such that $\phi(a)\neq\phi(b).$
Observe that for a graph $G,$ proper $\Gamma$-colorings of $H(G)$ are the same
as proper $\Gamma$-colorings of $G.$ The cardinality of $\Gamma$ determines
the number of proper $\Gamma$-colorings of $H,$ so we let $C_{H}(\lambda)$ be
the number of proper $\Gamma$-colorings of $H$ for any $\Gamma$ of cardinality
$\lambda.$ While the group structure of $\Gamma$ is not needed to define
proper colorings, it will be needed for the duality with nowhere-zero flows in
section 8.

The polymatroid defined in [46] is isomorphic to the polymatroid
$P(H)=(E,r_{H})$ constructed from $M[\mathcal{SG}(H)]$ and the partition
$\\{E(x_{1}),\dots,E(x_{n})\\}$ of $E(\mathcal{SG}(H)).$ We analyze $P(H)$
using an adjacency matrix $A(H)$ of $\mathcal{SG}(H).$ Start by ordering the
edges and vertices of $H$,
$E=\\{x_{1},\dots,x_{n}\\},~{}V=\\{v_{1},\dots,v_{m}\\}.$ The rows of $A(H)$
are indexed by $V.$ The columns are labelled by edges of $\mathcal{SG}(H)$ as
follows. The edges are listed so that those in $E(x_{1})$ come first, those in
$E(x_{2})$ come second, up to $E(x_{n}).$ Then, for $S\subseteq E,~{}r_{H}(S)$
is the dimension of the column space spanned by the union of all of the
$E(x),~{}x\in S.$ If we direct all the edges in $E(x)$ so that the tail is
$v_{x},$ then $A(H)$ is the usual adjacency matrix of a directed graph.
Specifically, the entry of $A(H)$ in a row labelled by $v\in V$ and column
labelled by $\\{v_{x},w\\}\in E(x)$ is given by

$\begin{cases}1&\mbox{ if }v=w\mbox{ and},~{}w\neq v_{x}.\\\ 0&v\notin x\mbox{
or }v=w\mbox{ and }w=v_{x}\\\ -1&\mbox{ if }v=v_{x}\mbox{ and }w\neq
v_{x}.\end{cases}$

###### Example 7.6

Let $V=\\{a,b,c,d\\}$ and
$E=\\{\\{a,b,c\\},\\{a,b,b,d\\},\\{a,b,b,b\\},\\{c,d\\}\\}$ and choose $v_{x}$
to be the alphabetically last vertex in each hyperedge. Then

$A(H)=\begin{bmatrix}\
&\\{c,a\\}&\\{c,b\\}&\\{d,a\\}&\\{d,b\\}&\\{d,b^{\prime}\\}&\\{b^{\prime\prime},a\\}&\\{b^{\prime\prime},b\\}&\\{b^{\prime\prime},b^{\prime}\\}&\\{d,c\\}\\\
a&1&0&1&0&0&1&0&0&0\\\ b&0&1&0&1&1&-1&0&0&0\\\ c&-1&-1&0&0&0&0&0&0&1\\\
d&0&0&-1&-1&-1&0&0&0&-1\end{bmatrix}.$ (5)

The primes on some of the column labels is to allow us to distinguish distinct
copies of the same vertex in a hyperedge.

$c$$d$$b$$b^{\prime}$$b^{\prime\prime}$$a$$x_{4}$$x_{1}$$x_{2}$$x_{3}$ Figure
1: $H$ from Example 7.6 \- $b,b^{\prime}$ and $b^{\prime\prime}$ represent the
same vertex. $a$$b$$c$$d$ Figure 2: $\mathcal{SG}(H)$ \- $E(x_{1})$,
$E(x_{2})$, $E(x_{3})$, $E(x_{4})$

In [46] Whittle attributes the following theorem to Helgason [21] and gives a
deletion/contraction argument. We will give a critical theorem proof. When
$H=H(G)$ for a graph $G,$ Theorem 7.7 is the usual relationship between the
chromatic polynomial of a graph and the characteristic polynomial of its cycle
matroid. Let $\kappa(H)$ be the number of components of $\mathcal{SG}(H).$

###### Theorem 7.7

$C_{H}(\lambda)=\lambda^{\kappa(H)}{\chi}_{P(H)}(\lambda).$ (6)

Proof:

Let $A=A(H).$ So $A$ is an $m\times k$ matrix with
$k=\sum^{n}_{i=1}|x_{i}|-1.$ View elements
$\gamma=(\gamma_{1},\dots,\gamma_{m})\in\Gamma^{m}$ as row vectors. Since
$\Gamma^{m}$ is a $\mathbb{Z}$-module, it makes sense to set $\mathcal{H}$ to
be the image of $\Gamma^{m}$ under right-multiplication by $A$ in
$\mathcal{G}=\Gamma^{k}.$ Then, setting
$b=|\Gamma|,~{}P(\mathcal{H})=P(\mathcal{H},b)$ is a polymatroid with ground
set $[k]$ once we identify $[k]$ with the columns of $A.$

Claim: $P(\mathcal{H})$ is isomorphic to $M[A].$ To see this, consider $T$ a
subset of columns of $A$ and $D$ a basis of $T$ in the matroid $M[A].$ Since
$A$ is the adjacency matrix of a graph, $A$ is totally unimodular. Hence,
there is a row echelon form $A^{\prime}$ of $A,$ obtained by integral row
operations, such that the pivot columns of $A^{\prime}$ contained in $T$ are
the columns in $D.$ This implies that $\mathcal{H}_{T}$ is isomorphic to
$\Gamma^{r_{A}(T)}$ and $r_{\mathcal{H}}(T)=r_{A}(T).$

As noted above, $P(H)$ is the polymatroid constructed from $M[A]$ and the
partition $\\{E(x_{1}),\dots,E(x_{n})\\}$ of the columns of $A.$ Let
$\mathcal{G}^{\prime}=\displaystyle\prod^{n}_{i=1}\Gamma^{|x_{i}|-1}$ and
$f:\Gamma^{k}\to\displaystyle\prod^{n}_{i=1}\Gamma^{|x_{i}|-1}$ be the
isomorphism which maps the first $|x_{1}|-1$ coordinates of $\Gamma^{k}$ to
$\Gamma^{|x_{1}|-1}$, the next $|x_{2}|-1$ coordinates to
$\Gamma^{|x_{2}|-1},$ etc. This gives us a homomorphism
$\psi:\Gamma^{m}\to\mathcal{G}^{\prime}$ defined by
$\psi(\gamma)=f(\gamma\cdot A).$ Apply $\psi$ to $\Gamma^{m}$ to get a
subgroup $\mathcal{H}^{\prime}$ of $\mathcal{G}^{\prime}.$ Then
$P(\mathcal{H}^{\prime})$ is the polymatroid constructed from $P(\mathcal{H})$
and the partition $\\{E(x_{1}),\dots,E(x_{n})\\}$ of $[k],$ and hence is
isomorphic to $P(H).$

To an element $\gamma=(\gamma_{1},\dots,\gamma_{m})\in\Gamma^{m}$ we associate
a $\Gamma$-coloring $\phi_{\gamma}$ of $H$ by
$\phi_{\gamma}(v_{i})=\gamma_{i}.$ The definition of $A$ shows that
$\phi_{\gamma}$ is a proper $\Gamma$-coloring of $H$ if and only if
$I(\psi(\gamma))=\emptyset.$ By Theorem 7.2 there are
${\chi}_{P(\mathcal{H})}(b)$ distinct images $\psi(\gamma)$ such that
$I(\psi(\gamma))=\emptyset.$ Every $\psi(\gamma)$ in $\mathcal{H}^{\prime}$
has $|\ker\psi|$ preimages. Examining $A$ we see that $\gamma$ is in the
kernel of $\psi$ if and only of $\gamma_{i}=\gamma_{j}$ whenever $v_{i}$ and
$v_{j}$ are in the same component of $\mathcal{SG}(H).$ Thus
$|\ker\psi|=b^{\kappa(H)}$ and there are
$b^{\kappa(H)}{\chi}_{P(H)}(b)=|\Gamma|^{\kappa(H)}{\chi}_{P(H)}(|\Gamma|)$
proper $\Gamma$-colorings of $H.$

$\square$

##  8 Polymatroid duality

In contrast to matroid duality, there are several different notions of
polymatroid duality in the literature. See, for instance, [7],[14], [22]. One
of the most general appears to be ${\bf{a}}$-duality. Let
${\bf{a}}\in\mathbb{R}^{E}_{\geq 0}.$ Then a polymatroid $P$ is an
${\bf{a}}$-polymatroid if for all $x\in E,~{}r(\\{x\\})\leq{\bf{a}}_{x}.$ We
will use ${\bf{a}}[k]$ to represent ${\bf{a}}$ such that ${\bf{a}}_{x}=k$ for
all $x\in E.$ Hence, an integer polymatroid is a $k$-polymatroid if and only
if it is an ${\bf{a}}[k]$-polymatroid. Similarly, $P$ is subcardinal if and
only if it is an ${\bf{a}}[1]$-polymatroid.

Given ${\bf{a}}\in(\mathbb{R}_{\geq 0})^{E}$ and $S\subseteq E$ we define
$|{\bf{a}}_{S}|=\displaystyle\sum_{x\in S}{\bf{a}}_{x}.$ We will use
$|{\bf{a}}|$ for $|{\bf{a}}_{E}|.$ Let $P$ be an ${\bf{a}}$-polymatroid.
Define $r^{\ast_{\bf{a}}}:2^{E}\to\mathbb{R}_{\geq 0}$ by

$r^{\ast_{\bf{a}}}(S)=r(E-S)+|{\bf{a}}_{S}|-r(E).$ (7)

We omit the routine proof of the following.

###### Proposition 8.1

Let $P$ be an ${\bf{a}}$-polymatroid. Then
$P^{\ast_{a}}=(E,r^{\ast_{\bf{a}}})$ is a polymatroid. Furthermore,

  1. 1.

$r^{\ast_{\bf{a}}}(E)=|{\bf{a}}|-r(E).$

  2. 2.

$(P^{\ast_{\bf{a}}})^{\ast_{\bf{a}}}=P.$

  3. 3.

If $S\subseteq E,$ then $(P^{\ast_{\bf{a}}}\setminus S)^{\ast_{\bf{a}}}=P/S.$

  4. 4.

If $S\subseteq E,$ then $(P^{\ast_{\bf{a}}}/S)^{\ast_{\bf{a}}}=P\setminus S.$

###### Definition 8.2

Let $P=(E,r)$ be an ${\bf{a}}$-polymatroid. The ${\bf{a}}$-dual of $P$ is
$P^{\ast_{\bf{a}}}=(E,r^{\ast_{\bf{a}}}),$ where $r^{\ast_{\bf{a}}}$ is
defined by (7).

With respect to ${\bf{a}}[1]$-duality, (7) coincides with the usual rank
function for matroid duality. Observe that if $M$ is a matroid, $P$ is a
polymatroid constructed from a partition $\\{S_{1},\dots,S_{n}\\}$ of $E(M),$
and ${\bf{a}}_{i}=|S_{i}|,$ then $P^{\ast_{\bf{a}}}$ is constructed from
$M^{\ast}$ using the same partition. When applied to $k$-polymatroids,
${\bf{a}}[k]$-duality is usually called $k$-duality and has appeared before.
See, for instance, [48].

Until further notice, we assume that $\Gamma$ is an abelian group. For the
moment, we do not assume $\Gamma$ is finite. Let us recall the usual
definitions for nowhere-zero $\Gamma$-flows on an oriented graph. A
$\Gamma$-flow on an oriented graph $G$ is a function $\phi:E(G)\to\Gamma$ such
that the inflow equals the outflow at each vertex. A $\Gamma$-flow is nowhere-
zero if for all $x\in E(G),~{}\phi(x)\neq 0.$ In order to define
$\Gamma$-flows on a hypergraph $H,$ we use the usual bipartite graph
associated to a hypergraph.

Given a hypergraph $H$ we form a bipartite graph $\mathcal{BG}(H)$ whose
bipartition consists of the vertices of $H$ in one block and the hyperedges of
$H$ in the other block. The number of edges between vertex $v$ and hyperedge
$x$ is equal to the multiplicity of $v$ in $x.$ All edges are oriented toward
the vertices. See Figure 3 for $\mathcal{BG}(H)$ when $H$ is the hypergraph
from Example 7.6. A $\Gamma$-flow on $H$ is a $\Gamma$-flow on
$\mathcal{BG}(H).$ A nowhere-zero $\Gamma$-flow on $H$ is a $\Gamma$-flow on
$H$ such that for all hyperedges $x$ there exists at least one edge in
$\mathcal{BG}(H)$ whose head is $x$ and whose value is not zero. When $G$ is
an oriented graph, there is a bijection between nowhere-zero $\Gamma$-flows on
the graph $G$ and nowhere-zero $\Gamma$-flows on the hypergraph $H(G).$ Given
a nowhere-zero $\Gamma$-flow $\phi:E(G)\to\Gamma$ on the graph $G,$ and an
oriented edge $x=(v,w)$ of $G,$ define $\psi:E(\mathcal{BG}(H(G)))\to\Gamma$
by $\psi((v,x))=-\phi(x)$ and $\psi((w,x))=\phi(x).$ Then
$\phi\leftrightarrow\psi$ is such a bijection. Nowhere-zero $\Gamma$-flows on
hypergraphs share another property with their graphic counterparts.

$x_{1}$$a$$x_{2}$$b$$x_{3}$$c$$x_{4}$$d$ Figure 3: $\mathcal{BG}(H)$

###### Proposition 8.3

A hypergraph has a nowhere-zero $\mathbb{Z}/m\mathbb{Z}$-flow if and only if
it has a nowhere-zero $\mathbb{Z}$-flow $\phi$ with the all values of $\phi$
in $\\{-(m-1),\dots,m-1\\}.$

Proof:  Given a nowhere-zero $\mathbb{Z}/m\mathbb{Z}$-flow on $H,$ remove all
edges of $\mathcal{BG}(H)$ assigned $0$ and apply the same fact for graphs to
see that $H$ has a nowhere-zero $\mathbb{Z}$-flow all of whose values are in
$\\{-(m-1),\dots,m-1\\}$. See, for instance, [3, Proposition 6.3.7].
Conversely, given a nowhere-zero flow on $H$ with values in
$\\{-(m-1),\dots,m-1\\},$ reduce modulo $m$ to get a nowhere-zero
$\mathbb{Z}/m\mathbb{Z}$-flow on $H.$ $\square$

One way to visualize $\Gamma$-flows on $H$ is to picture the hyperedges as
hubs and the vertices as customers. For a customer $v$ and hub $x,$ the value
of $\phi(v,(v,x))$ is the value of whatever the customer is sending the hub.
In a $\Gamma$-flow the total going through the hub and the total being sent by
each customer to all of the hubs is zero. A nowhere-zero $\Gamma$-flow has
something nonzero going through every hub. From this point of view, flows
treat vertices and hyperedges in an identical fashion. The nowhere-zero
condition only applies to the hyperedges (hubs).

###### Theorem 8.4

Let $H$ be a hypergraph and $\Gamma$ a finite abelian group. Let
${\bf{a}}\in(\mathbb{R}_{\geq 0})^{E(H)}$ be defined by ${\bf{a}}_{x}=|x|-1.$
Then the number of nowhere-zero $\Gamma$-flows on $H$ is
${\chi}_{P(H)^{\ast_{\bf{a}}}}(|\Gamma|).$

If $H=H(G),$ then $P(H)$ is the cycle matroid of $G$ and
${\bf{a}}={\bf{a}}[1]$ induces standard matroid duality. Therefore, in this
case, Theorem 8.4 is the classical flow polynomial formula for nowhere-zero
$\Gamma$-flows on $G$ [3].

Proof:  We follow the notation of the proof of Theorem 7.7. So
$\mathcal{G}=\Gamma^{k}$ and
$\mathcal{G}^{\prime}=\displaystyle\prod^{n}_{i=1}\Gamma^{|x_{i}|-1}.$ This
time we think of elements $\gamma=(\gamma_{1},\dots,\gamma_{k})$ of
$\mathcal{G}$ as column vectors and define $\tau:\Gamma^{k}\to\Gamma^{m}$ by
$\tau(\gamma)=A\cdot\gamma.$ Now we let
$\mathcal{K}^{\prime}=f(\ker\tau)\subseteq\mathcal{G}^{\prime},$ where $f$ is
the same isomorphism between $\Gamma^{k}$ and $\mathcal{G}^{\prime}$ as
before. By Theorem 7.2, the number of $h\in\mathcal{K}^{\prime}$ such that
$I(h)=\emptyset$ is
${\chi}_{P(\mathcal{K}^{\prime})}(b)={\chi}_{P(\mathcal{K}^{\prime})}(|\Gamma|).$
To finish the proof we establish the following three claims:

  1. 1.

There is a bijection $\alpha$ from $\mathcal{K}^{\prime}$ to $\Gamma$-flows on
$H.$

  2. 2.

When restricted to
$\mathcal{F}=\\{h\in\mathcal{K}^{\prime}:I(h)=\emptyset\\},~{}\alpha$ is a
bijection between $\mathcal{F}$ and nowhere-zero $\Gamma$-flows on $H.$

  3. 3.

$P(\mathcal{K}^{\prime})=P(H)^{\ast_{\bf{a}}}.$

Let
$\gamma=((\gamma_{1,1},\dots,\gamma_{1,|x_{1}|-1}),\dots,(\gamma_{n,1},\dots,\gamma_{n,|x_{n}|-1}))\in\mathcal{G}^{\prime}.$
For $x_{j}\in E$ write down the vertices in
$x_{j}=(w_{1},\dots,w_{|x_{j}|-1},w_{|x_{j}|})$ in order so that
$(\\{v_{x_{j}},w_{1}\\},\\{v_{x_{j}},w_{2}\\},\dots,\\{v_{x_{j}},w_{|x_{j}|-1}\\})$
is the same ordering of the edges in $E(x_{j})$ as was used to define $A$ and
$w_{|x_{j}|}=v_{x_{j}}.$ We define a function
$\alpha(\gamma):E(\mathcal{BG}(H))\to\Gamma$ as follows.

$\alpha(\gamma)(w_{i},x_{j})=\begin{cases}\gamma_{j,i}~{},&i<|x_{j}|\\\
-\displaystyle\sum^{|x_{j}|-1}_{l=1}\gamma_{j,l}~{},&i=|x_{j}|\end{cases}.$
(8)

The definition of $\alpha$ implies that for $\alpha(\gamma)$ the sum of
outgoing edges to a hyperedge $x$ in $\mathcal{BG}$ is zero. The
$\gamma\in\mathcal{K}^{\prime}$ are precisely those such that $\alpha(\gamma)$
is a $\Gamma$-flow on $H$ establishing the first claim. The second claim
follows from the definition of $I(h).$ It remains to prove that
$P(\mathcal{K}^{\prime})=P(H)^{\ast_{\bf{a}}}.$

First consider $M[A]$. A result that goes back to Whitney [45] is that the if
$\mathcal{K}$ is the kernel of multiplication by $A$ as a linear
transformation of real vector spaces, then $M[\mathcal{K}]\cong M[A]^{\ast}.$
As in the proof of Theorem 7.7, we identify the columns of $A$ with $[k]$ and
let $T$ be a subset of the columns of $A.$ Then $r^{\ast}_{A}(T),$ the rank of
$T$ in $M[A]^{\ast},$ is the maximum number of free variables in $T$ over all
all matrices row equivalent to $A.$ Let $A^{\prime}$ be a matrix row
equivalent to $A$ which maximizes the number free variables in $T.$ We can
choose $A^{\prime}$ to be the identity matrix when restricted to the pivot
columns. Since $A$ is totally unimodular, the rows of $A^{\prime}$ are an
integral linear combination of the rows of $A.$ Therefore, the elements of
$\ker\tau$ consist of arbitrary choices in $\Gamma$ for each coordinate
corresponding to a free variable, and all coordinates associated with pivot
variables are determined by those choices. Hence,
$|\pi_{T}(\ker\tau)|=|\Gamma|^{r^{\ast}_{A}(T)}$ and $P(\mathcal{K})$ equals
$M[A]^{\ast}.$ Since $P(\mathcal{K}^{\prime})$ is constructed from
$P(\mathcal{K})$ and the partition $\\{E(x_{1}),\dots,E(x_{n})\\}$ and
$P(H)^{\ast_{\bf{a}}}$ is constructed from $M[A]^{\ast}$ with the same
partition, they are equal.

$\square$

Three special situations deserve mention. One, if $G$ is a graph and $H=H(G)$,
then Theorem 7.7 and Theorem 8.4 are the usual coloring-flow duality for
graphs. Two, if $H$ is a uniform $k$-hypergraph, then ${\bf{a}}={\bf{a}}[k]$
and $\ast_{\bf{a}}$ is $k$-polymatroid duality. Lastly, if the edges of $H$
are subsets of $V$ (as opposed to multisets), then $|x|-1=r_{P(H)}(\\{x\\}).$
Basing polymatroid duality on the rank of the singletons has been considered
before. See, for instance, [7] and [48].

##  9 Duality for polymatroids realized over a group

One of the motivations for Whitney’s original introduction of matroids [45]
was to answer the question, “What is the dual of a nonplanar graph?” He
offered two solutions. One, let $M[G]$ be the cycle matroid of the graph $G$.
Then $M[G]^{\ast}$ serves as the dual of $G.$ The primary justification for
this point of view is that for embedded planar graphs, $M[G]^{\ast}$ is
isomorphic to $M[G^{\ast}],$ where $G^{\ast}$ is the geometric planar dual of
$G.$

In order to describe Whitney’s second answer, choose an orientation for $G$
and let $A$ be the adjacency matrix for $G,$ the columns labelled by the edges
and the rows by the vertices. Now $M[A]$ is isomorphic to $M[G].$ Then
$R(A)^{\perp},$ the orthogonal complement of the row space of $A,$ serves as a
dual for $G.$ This point of view is validated by the fact that
$M[R(A)^{\perp}]$ is isomorphic to $M[A]^{\ast}$ which itself is isomorphic to
$M[G]^{\ast}.$

In this section we will closely mirror these ideas in the search for a dual of
$\mathcal{H}\leq\mathcal{G}.$ Throughout this section
$\mathcal{G}=\displaystyle\prod_{x\in E}\Gamma_{x},$ where each $\Gamma_{x}$
is a finite group (not necessarily equal), and $\mathcal{H}$ is a subgroup of
$\mathcal{G}.$ As before, we fix $b>1.$ In addition, we set
${\bf{a}}\in(\mathbb{R}_{\geq 0})^{E},~{}{\bf{a}}_{x}=\log_{b}|\Gamma_{x}|.$
We will be comparing our constructions with the special situation when for all
$x\in E,~{}\Gamma_{x}=\mathbb{Z}/p\mathbb{Z},~{}p$ a fixed prime. In this
case, $P(\mathcal{H})$ is the matroid previously denoted by $M[\mathcal{H}],$
where $\mathcal{H}$ is a subspace of the vector space
$(\mathbb{Z}/p\mathbb{Z})^{E}.$

We have already seen the analog of Whitney’s first solution. The polymatroid
$P(\mathcal{H},b)^{\ast_{\bf{a}}}$ is a polymatroid dual of
$P(\mathcal{H},b).$ When $\Gamma_{x}=\mathbb{Z}/p\mathbb{Z}$ for all
$x,~{}P(\mathcal{H},b)^{\ast_{\bf{a}}}=M[\mathcal{H}]^{\ast},$ the usual
matroid dual of $M[\mathcal{H}].$ Our analog of Whitney’s second solution to
“What is the dual of a nonplanar graph” involves the (complex) representation
theory of finite groups.

We will use the following notation to describe a candidate for a
representation-based dual to $\mathcal{H}\leq\mathcal{G}.$ For a finite set
$U,~{}\mathbb{C}[U]$ is the $\mathbb{C}$-vector space with basis
$\\{w_{u}:u\in U\\}.$ When $\Gamma$ is a finite group, $\mathbb{C}[\Gamma]$
will also stand for the left-regular representation of $\Gamma.$ Specifically,
if
$\displaystyle\sum_{\gamma\in\Gamma}c_{\gamma}~{}w_{\gamma}\in\mathbb{C}[\Gamma]$
and $\gamma^{\prime}\in\Gamma,$ then
$\gamma^{\prime}\cdot\displaystyle\sum_{\gamma\in\Gamma}c_{\gamma}~{}w_{\gamma}=\displaystyle\sum_{\gamma\in\Gamma}c_{\gamma}~{}w_{\gamma^{\prime}\cdot\gamma}.$
The set of (complex) irreducible representations of $\Gamma$ is
$\widehat{\Gamma.}$ The irreducible representations of $\widehat{\mathcal{G}}$
are the representations of the form $\rho=\displaystyle\bigotimes_{x\in
E}\rho_{x},~{}\rho_{x}\in\widehat{\Gamma_{x}}$ [37].

Depending on the circumstances, the representation-based dual of
$\mathcal{H}\leq\mathcal{G}$ is one of the following three cryptomorphic
objects.

###### Definition 9.1

  * •

${\mathcal{R}}_{1}(\mathcal{H})$: The subrepresentation of
$\mathbb{C}[\mathcal{G}]$ consisting of all elements whose coefficients are
constant on the right cosets of $\mathcal{H}.$ Equivalently,

${\mathcal{R}}_{1}(\mathcal{H})=\bigg{\\{}\displaystyle\sum_{g\in\mathcal{G}}c_{g}w_{g}\in\mathbb{C}[\mathcal{G}]:\mbox{
for all }g\in\mathcal{G},~{}h\in\mathcal{H},c_{g}=c_{g\cdot h}\bigg{\\}}.$

  * •

${\mathcal{R}}_{2}(\mathcal{H})$: The permutation representation on
$\mathbb{C}[\mathcal{G}/\mathcal{H}]$ induced from the $\mathcal{G}$-action on
right-cosets
$\mathcal{G}/\mathcal{H},~{}g^{\prime}\cdot(g\mathcal{H})=(g^{\prime}\cdot
g)\mathcal{H}.$

  * •

${\mathcal{R}}(\mathcal{H})$: The multiset of irreducible representations in
$\widehat{\mathcal{G}}$ whose direct sum is equivalent to
${\mathcal{R}}_{1}(\mathcal{H})$ and ${\mathcal{R}}_{2}(\mathcal{H}).$

In representation theory ${\mathcal{R}}_{1}(\mathcal{H})$ and
${\mathcal{R}}_{2}(\mathcal{H})$ are known as the representation of
$\mathcal{G}$ induced by the trivial representation of $\mathcal{H}.$

###### Example 9.2

Let $\mathcal{G}=S_{3}\times S_{3},\mathcal{H}=\\{(\sigma,\sigma):\sigma\in
S_{3}\\},$ the diagonal embedding of $S_{3}.$ A character computation applied
to the permutation representation ${\mathcal{R}}_{2}(\mathcal{H})$ shows that
${\mathcal{R}}(\mathcal{H})=\\{1\otimes 1,s\otimes s,t\otimes t\\},$ where
$1,s$ and $t$ are respectively the trivial, sign and two-dimensional
irreducible representations of $S_{3}.$

###### Proposition 9.3

Let $\mathcal{H}$ be a normal subgroup of $\mathcal{G}$ and
$\pi:\mathcal{G}\to\mathcal{G}/\mathcal{H}$ be the quotient map. Mapping
$\phi\in\widehat{\mathcal{G}/\mathcal{H}}$ to ${\mathcal{R}}(\mathcal{H})$ by
$\phi\to\phi\circ\pi$ is a bijection between the multisets
$\widehat{\mathcal{G}/\mathcal{H}}$ and ${\mathcal{R}}(\mathcal{H}).$
Equivalently, $\rho\in\widehat{\mathcal{G}}$ is in ${\mathcal{R}}(H)$ if and
only if $\mathcal{H}\subseteq\ker\rho$, and, if
$\rho\in{\mathcal{R}}(\mathcal{H}),\rho=\phi\circ\pi,$ then the multiplicity
of $\rho$ in ${\mathcal{R}}(\mathcal{H})$ equals the multiplicity of $\phi$ in
$\mathbb{C}[\mathcal{G}/\mathcal{H}].$

Proof:  From the point of view of ${\mathcal{R}}_{2}(\mathcal{H}),$ we see
that if $\phi\in\widehat{\mathcal{G}/\mathcal{H}},$ then $\phi\circ\pi$ is in
${\mathcal{R}}(\mathcal{H}).$ Since the
$\dim{\mathcal{R}}_{2}(\mathcal{H})=|\mathcal{G}/\mathcal{H}|$ and
$\phi\to\phi\circ\pi$ as a map from
$\widehat{\mathcal{G}/\mathcal{H}}\to{\mathcal{R}}(\mathcal{H})$ is injective,
$\phi\circ\pi$ accounts for all of ${\mathcal{R}}(\mathcal{H}).$ $\square$

###### Example 9.4

$\mathcal{G}=S_{3}\times S_{3}$ and
$\mathcal{H}=\\{(\sigma,\tau):s(\sigma)=s(\tau)\\},$ where as in Example 9.2,
$s$ is the sign representation of $S_{3}.$ Then $\mathcal{H}$ is contained in
the kernel of $1\otimes 1$ and equals the kernel of $s\otimes s.$ Since
$|\mathcal{G}/\mathcal{H}|=2,{\mathcal{R}}(\mathcal{H})=\\{1\otimes 1,s\otimes
s\\}.$

When $\Gamma_{x}$ is a fixed abelian group for all $x\in E,$ the idea that the
subgroup of representations in $\widehat{\mathcal{G}}$ whose kernels contain
$\mathcal{H}$ could be used as a dual code to $\mathcal{H}$ has been part of
the coding literature since [28]. In Section 10 we will briefly explore how
${\mathcal{R}}(\mathcal{H})$ acts as a dual code for $\mathcal{H}$ whether or
not $\mathcal{H}$ is abelian.

###### Example 9.5

Suppose $\mathcal{G}=(\mathbb{Z}/p\mathbb{Z})^{E},~{}E=[n],$ and $p$ is a
prime. As in Example 3.2, a subgroup $\mathcal{H}$ of $\mathcal{G}$ is also a
subspace of $~{}\mathcal{G}$ viewed as a vector space. How is
${\mathcal{R}}(\mathcal{H})$ related to $\mathcal{H}^{\perp}?$ The irreducible
representations of $\mathbb{Z}/p\mathbb{Z}$ are
$\\{\rho_{0},\rho_{1},\dots,\rho_{p-1}\\}$ with $\rho_{j}(\bar{k})=e^{2\pi
i(jk/p)}.$ The function
$f:\widehat{\mathbb{Z}/p\mathbb{Z}}\to\mathbb{Z}/p\mathbb{Z},~{}f(\rho_{j})=\bar{j}$
is an isomorphism of groups, the group operation on
$\widehat{\mathbb{Z}/p\mathbb{Z}}$ being tensor product. Let
$F:\widehat{\mathcal{G}}\to\mathcal{G}$ be the isomorphism induced by $f.$
Suppose $\rho\in{\mathcal{R}}(\mathcal{H}).$ Write
$F(\rho)=(\bar{m}_{1},\dots,\bar{m}_{n})$ and for $h\in\mathcal{H}$ write
$h=(\bar{h}_{1},\dots,\bar{h}_{n}).$ Then $\rho\in{\mathcal{R}}(\mathcal{H})$
if and only if $\rho(h)=1$ for all $h\in\mathcal{H}.$ This holds if and only
if $\displaystyle\prod^{n}_{k=1}e^{2\pi i(m_{k}h_{k}/p)}=1.$ Equivalently, if
and only if $\displaystyle\sum^{n}_{k=1}\bar{m}_{k}\bar{h}_{k}=0\mod p.$ This
is Whitney’s description of the subspace $\mathcal{H}^{\perp}$ of
$\mathcal{G}$ such that $M[\mathcal{H}]^{\ast}=M[\mathcal{H}^{\perp}].$

The rest of this section shows various ways ${\mathcal{R}}(\mathcal{H})$
realizes $P(\mathcal{H})^{\ast_{\bf{a}}}$ in a manner similar to the way
$W^{\perp}$ realizes $M[W]^{\ast}$ when $W$ is a subspace of
${\mathbb{F}}^{E}$ with ${\mathbb{F}}$ a field. In general, the trivial
representation in $\widehat{\mathcal{G}}$ will play the role of the
$0\in{\mathbb{F}},$ the tensor product decomposition of representations in
$\widehat{\mathcal{G}}$ substitutes for the coordinates of elements of
${\mathbb{F}}^{E},$ and dimensions of representations will replace counting
statistics. For notational brevity we will denote $P^{\ast_{a}}(\mathcal{H})$
by $P^{\ast}$ and the corresponding rank function as $r^{\ast}.$ First a few
preparatory lemmas.

A coloop of an ${\bf{a}}$-polymatroid is an element $x\in E$ such that
$r(E)=r(E-\\{x\\})+r(\\{x\\})$ and $r(\\{x\\})=a_{x}>0.$ When
${\bf{a}}={\bf{a}}[1]$ this definition of coloop is the usual one for matroids
(and subcardinal polymatroids). The law of diminishing returns implies that if
$x$ is a coloop of an ${\bf{a}}$-polymatroid and $x\notin S,$ then
$r(S\cup\\{x\\})=r(S)+r(\\{x\\}).$ We omit the routine proof of the following
characterization of the flats of $P^{\ast}.$

###### Lemma 9.6

If $S$ is a subset of an ${\bf{a}}$-polymatroid $P=(E,r),$ then $S$ is a flat
of $P^{\ast}$ if and only if $P\setminus S$ contains no coloops.

For all ${\bf{a}}$-polymatroids $P=(E,r),~{}r^{\ast}(E)=|{\bf{a}}|-r(E).$

###### Lemma 9.7

$\log_{b}\displaystyle\sum_{\rho\in{\mathcal{R}}(\mathcal{H})}\dim\rho=|{\bf{a}}|-r_{\mathcal{H}}(E).$

Proof:  By definition
$\displaystyle\sum_{\rho\in{\mathcal{R}}(\mathcal{H})}\dim\rho=\dim{\mathcal{R}}_{2}(\mathcal{H})=|\mathcal{G}/\mathcal{H}|.$
$\square$

###### Definition 9.8

Let $\rho\in\widehat{\mathcal{G}},~{}\rho=\displaystyle\bigotimes_{x\in
E}\rho_{x},$ each $\rho_{x}\in\widehat{\Gamma}_{x}.$ Then,

$\mbox{triv}\,(\rho)=\\{x\in E:\rho_{x}\mbox{ is the trivial representation of
}\Gamma_{x}\\}.$

###### Example 9.9

Suppose $\mathcal{G}=(\mathbb{Z}/p\mathbb{Z})^{n},\mathcal{H}$ is a subgroup
of $\mathcal{G},$ and $F:{\mathcal{R}}(\mathcal{H})\to\mathcal{G}$ is the
isomorphism from $\widehat{\mathcal{G}}\to\mathcal{G}$ restricted to
${\mathcal{R}}(\mathcal{H}).$ Then $\mbox{triv}\,(h)=I(F(h)).$

###### Example 9.10

Let
$E=\\{x,y\\},~{}\mathcal{G}=\Gamma_{x}\times\Gamma_{y},~{}\Gamma_{x}=\Gamma_{y}=S_{3}.$
Let

$\mathcal{H}=\\{((1),(1)),((1),(123)),((1),(132)),((12),(12)),((12),(13)),((12),(23))\\}.$

A character calculation shows that

${\mathcal{R}}(\mathcal{H})=\\{1\otimes 1,s\otimes s,t\otimes 1,t\otimes
s\\}.$

So $\mbox{triv}\,(1\otimes 1)=\\{x,y\\},\mbox{triv}\,(t\otimes
1)=\\{y\\},\mbox{triv}\,(s\otimes s)=\mbox{triv}\,(t\otimes s)=\emptyset.$

We are going to establish ${\mathcal{R}}(\mathcal{H})$-mirrors of Corollary
7.3 and Propositions 7.4, and 7.5. The next two lemmas prepare us for those
results. Let $S\subseteq
E,\rho\in\widehat{\mathcal{G}_{S}},\rho=\displaystyle\bigotimes_{x\in
S}\rho_{x}.$ The extension of $\rho$ to $\widehat{\mathcal{G}}$ is
$\bar{\rho}=\displaystyle\bigotimes_{x\in E}\bar{\rho}_{x},$ where
$\bar{\rho}_{x}=\rho_{x}$ for all $x\in S,$ and for $x\notin
S,~{}\bar{\rho}_{x}\mbox{ is the trivial representation of }\Gamma_{x}.$

###### Lemma 9.11

(Extension lemma) Let $S\subseteq E.$ Then $\rho$ is in
${\mathcal{R}}(\mathcal{H}_{S})$ if and only if $\bar{\rho}$ is in
${\mathcal{R}}(\mathcal{H}).$

Proof:  The easiest way to see this is from the point of view of
${\mathcal{R}}_{1}(\mathcal{H})$ and to observe that as a subrepresentation of
$\mathbb{C}[\mathcal{G}],~{}\rho$ is constant on the right cosets
$\mathcal{G}_{S}/\mathcal{H}_{S}$ if and only if $\bar{\rho}$ is constant on
the right cosets $\mathcal{G}/\mathcal{H}.$ $\square$

We saw previously that $S$ is a flat of $P^{\ast}$ if and only if $E-S$ has no
coloops. Hence it might be useful to understand the relationship between
${\mathcal{R}}(\mathcal{H})$ and the coloops of $P(\mathcal{H}).$

###### Lemma 9.12

An element $x\in E$ is a coloop of $P(\mathcal{H})$ if and only if
$x\in\mbox{triv}\,(\rho)$ for all $\rho\in{\mathcal{R}}(\mathcal{H}).$

Proof:  By definition, $x$ is a coloop of $P(\mathcal{H})$ if and only if

$|\mathcal{H}|=|\mathcal{H}_{E-\\{x\\}}||\Gamma_{x}|\mbox{ iff
}\frac{|\mathcal{G}|}{|\mathcal{H}|}=\frac{|\mathcal{G}_{E-\\{x\\}}|}{|\mathcal{H}_{E-\\{x\\}}|}\mbox{
iff
}\dim{\mathcal{R}}_{2}(\mathcal{H})=\dim{\mathcal{R}}_{2}(\mathcal{H}_{E-\\{x\\}}).$

The extension lemma implies that the last equality holds if and only
$x\in\mbox{triv}\,(\rho)$ for all $\rho\in{\mathcal{R}}(\mathcal{H}).$
$\square$

###### Proposition 9.13

If $\rho\in{\mathcal{R}}(\mathcal{H}),$ then $\mbox{triv}\,(\rho)$ is a flat
of $P^{\ast}.$

Proof:  Let $S=\mbox{triv}\,(\rho).$ If $x\in E-S$ is a coloop of
$P(\mathcal{H})\setminus S,$ then the previous proposition implies that
$x\in\mbox{triv}\,(\rho).$ Therefore, $E-S$ has no coloops and $S$ is a flat
of $P^{\ast}.$ $\square$

###### Proposition 9.14

If $S$ is a coatom of $\mathcal{L}_{P^{\ast}},$ then there exists
$\rho\in{\mathcal{R}}(\mathcal{H})$ suchthat $\mbox{triv}\,(\rho)=S.$

Proof:  Since $S$ is a coatom of
$\mathcal{L}_{P^{\ast}}(\mathcal{H}),~{}\dim{\mathcal{R}}_{2}(\mathcal{H}_{E-S})>0,$
so there exists $\rho\in{\mathcal{R}}(\mathcal{H}_{E-S}),~{}\rho$ not equal to
the trivial representation. If $\mbox{triv}\,(\rho)\neq\emptyset,$ then
$\mbox{triv}\,(\bar{\rho})$ is a flat of $P^{\ast}$ strictly between $S$ and
$E.$ Thus $\mbox{triv}\,(\rho)=\emptyset,\mbox{triv}\,(\bar{\rho})=S$ and
$\bar{\rho}\in{\mathcal{R}}(\mathcal{H}).$ $\square$

###### Proposition 9.15

Let $S$ be a flat of $P^{\ast}.$ Then there exist
$\\{\rho_{1},\dots,\rho_{m}\\}\subseteq{\mathcal{R}}(\mathcal{H}),~{}m\leq
n-|S|$ such that $\bigcap^{m}_{i=1}\mbox{triv}\,(\rho_{i})=S.$

Proof:  Let $y\in E-S.$ Since $y$ is not a coloop of $P\setminus S,$
Proposition 9.14 shows that there exists
$\rho^{y}\in{\mathcal{R}}(\mathcal{H}_{E-S})$ such that
$\rho^{y}=\bigotimes_{x\in
E-S}\rho^{y}_{x},~{}\rho^{y}_{x}\in\widehat{\mathcal{G}_{x}}$ and
$\rho^{y}_{y}$ is not the trivial representation of $\mathcal{G}_{y}.$
Then$\\{\overline{\rho^{y}}\\}_{y\in E-S}$ satisfies the conclusion of the
proposition. $\square$

###### Theorem 9.16

(Dual Crapo-Rota for groups)
Given $S\subseteq E,$ let
$Y(S)=\\{(\rho_{1},\dots,\rho_{k})\in({\mathcal{R}}(\mathcal{H}))^{k}:\displaystyle\bigcap^{k}_{i=1}\mbox{triv}\,(\rho_{i})=S\\}$.
For any choice of $b>1$ and positive integer $k,$

$\displaystyle\sum_{(\rho_{1},\dots,\rho_{k})\in
Y(\emptyset)}\displaystyle\prod^{k}_{i=1}\dim\rho_{i}={\chi}_{P^{\ast}}(b^{k}).$
(9)

Proof:  With Proposition 9.13 in hand we can copy the proof of Theorem 7.2. If
$x$ is a coloop of $P(\mathcal{H}),$ then by the proof of Proposition 9.13,
the left hand side of (9) is zero. In addition, $x$ is a loop of $P^{\ast},$
so ${\chi}_{P^{\ast}}$ is the zero function.

So we assume that $P(\mathcal{H})$ has no coloops and thus the empty set is a
flat of $\mathcal{L}_{P^{\ast}}.$ Since $\mbox{triv}\,(\rho)$ is always a flat
of $P^{\ast}$, and the flats of $P^{\ast}$ are closed under intersection,
$\phi:({\mathcal{R}}(\mathcal{H}))^{k}\to\mathcal{L}_{P^{\ast}}$ defined by
$\phi(\rho_{1},\dots,\rho_{k})=\mbox{triv}\,(\rho_{1})\cap\cdots\cap\mbox{triv}\,(\rho_{k})$
is a function from $({\mathcal{R}}(\mathcal{H}))^{k}$ to
$\mathcal{L}_{P^{\ast}}.$ Now let $f:\mathcal{L}_{P^{\ast}}\to\mathbb{Z}_{\geq
0}$ be defined by $f(S)=\displaystyle\sum_{(\rho_{1},\dots,\rho_{k})\in
Y(S)}\displaystyle\prod^{k}_{i=1}\dim\rho_{i}.$ When $Y(S)$ is empty, $f(S)$
is defined to be zero. Then

$\displaystyle\sum_{T\supseteq
S}f(T)=\displaystyle\sum_{\stackrel{{\scriptstyle(\rho_{1},\dots,\rho_{k})}}{{\forall
i,~{}S\subseteq\mbox{triv}\,(\rho_{i})}}}\displaystyle\prod^{k}_{i=1}\dim\rho_{i}$
$=(\dim{\mathcal{R}}_{2}(\mathcal{H}_{E-S}))^{k}=\bigg{(}\frac{|\mathcal{G}_{E-S}|}{|\mathcal{H}_{E-S}|}\bigg{)}^{k}=(b^{{\bf{a}}_{E-S}-r_{\mathcal{H}}(E-S)})^{k}=(b^{k})^{r^{\ast}(E)-r^{\ast}(S)}.$

The second equals sign follows from the extension lemma and the last equals
sign holds for any ${\bf{a}}$-polymatroid. Now apply Lemma 2.1 and Möbius
inversion. $\square$

###### Example 9.17

(Example 9.10 continued) Let $\Gamma,\mathcal{G},$ and $\mathcal{H}$ be as in
Example 9.10. Recall that $1,s,$ and $t$ are respectively, the trivial, sign
and two-dimensional irreducible representations of $S_{3}.$ So $b=|\Gamma|=6,$
and ${\bf{a}}=(1,1).$ Hence,

$r_{\mathcal{H}}(\emptyset)=0,~{}r_{\mathcal{H}}(\\{1\\})=\log_{6}2,~{}r_{\mathcal{H}}(\\{2\\})=1=r_{\mathcal{H}}(\\{1,2\\}).$

Therefore,

$r^{\ast_{\bf{a}}}(\emptyset)=0,~{}r^{\ast_{\bf{a}}}_{\mathcal{H}}(\\{1\\})=r^{\ast_{\bf{a}}}_{\mathcal{H}}(\\{1,2\\})=1,~{}r^{\ast_{\bf{a}}}_{\mathcal{H}}(\\{2\\})=\log_{6}2.$

The flats and relevant Möbius functions in $P^{\ast_{\bf{a}}}$ are

$\emptyset\leq\\{2\\}\leq\\{1,2\\},~{}\mu(\emptyset,\emptyset)=1,~{}\mu(\emptyset,\\{2\\})=-1,\mu(\emptyset,\\{1,2\\})=0.$

Hence,

${\chi}_{P^{\ast_{\bf{a}}}}(\lambda)=\lambda-\lambda^{1-\log_{6}2}=\lambda-\lambda^{\log_{6}3}.$

The intersection
$\mbox{triv}\,(\rho_{1})\cap\mbox{triv}\,(\rho_{2})=\emptyset$ for all pairs
$(\rho_{1},\rho_{2})\subseteq({\mathcal{R}}(\mathcal{H}))^{2}$ except

$(1\otimes 1,1\otimes 1),(1\otimes 1,t\otimes 1),(t\otimes 1,1\otimes
1),(t\otimes 1,t\otimes 1).$

Thus, the l.h.s. of (9) is $36-9.$ On the other side,

${\chi}_{P^{\ast_{a}}}(6^{2})=36-36^{\log_{6}3}=36-6^{2\log_{6}3}=36-9.$

As the reader may have noticed, we have not yet given a rank function on $E$
that only depends on the combinatorics of ${\mathcal{R}}(\mathcal{H}),$ equals
$r^{\ast}_{\mathcal{H}}$, and reduces to the usual definition of
$M[\mathcal{H}]^{\ast}$ when $\Gamma_{x}$ is $\mathbb{Z}/p\mathbb{Z}$ for all
$x.$ Lemma 9.7 shows that
$r_{{\mathcal{R}}(\mathcal{H})}(E)=\log_{b}\displaystyle\sum_{\rho\in{\mathcal{R}}(\mathcal{H})}\dim\rho$
gives the same answer as the usual definition of
$r^{\ast}_{\mathcal{H}^{\perp}}(E)$ for the special case of all
$\Gamma_{x}=\mathbb{Z}/p\mathbb{Z}$. However, it is not at this point clear
how to define a rank function for arbitrary $S\subseteq E$ that only depends
on the combinatorial data of ${\mathcal{R}}(\mathcal{H}).$ One ‘obvious’
choice would be to try
$r^{\ast}_{{\mathcal{R}}(\mathcal{H})}(S)=\log_{b}\displaystyle\sum_{\rho\in{\mathcal{R}}(\mathcal{H})}\displaystyle\prod_{x\in
S}\dim\rho_{x}$ where we write each $\rho\in{\mathcal{R}}(\mathcal{H})$ as
$\displaystyle\bigotimes_{x\in E}\rho_{x}.$ However, this does not always
work.

###### Example 9.18

(Example 9.2 continued.) We continue examining Example 9.2. So,
${\bf{a}}=(1,1)$ and
$r_{\mathcal{H}}(\\{1\\})=r_{\mathcal{H}}(\\{2\\})=r_{\mathcal{H}}(\\{1,2\\})=1.$
Thus,
$r^{\ast}_{\mathcal{H}}(\\{1\\})=r^{\ast}(\\{2\\})=r^{\ast}_{\mathcal{H}}(\\{1,2\\})=1.$
We saw previously that ${\mathcal{R}}(\mathcal{H})$ was equal to $\\{1\otimes
1,s\otimes s,t\otimes t\\},$ where $\\{1,s,t\\}$ are the three irreducible
representations in $\widehat{S_{3}}.$ In this case the sum of the dimensions
of the representations in each single coordinate is $4$, not the expected
total of $6$ needed to equal the corresponding rank of the polymatroid
${\bf{a}}$-dual to $r_{\mathcal{H}}.$

Our definition of a rank function based on the combinatorics of
${\mathcal{R}}(\mathcal{H})$ which is equal to $r^{\ast}_{\mathcal{H}}$ is
based on the observation that for any ${\bf{a}}$-polymatroid $P=(E,r)$ and
$S\subseteq E,~{}r^{\ast}(S)=r^{\ast}(E)-r^{\ast}_{P/S}(E-S).$ Since the
definition makes sense for any representation of $\mathcal{G},$ we state it in
that generality.

###### Definition 9.19

Let ${\mathcal{R}}$ be a representation of $\mathcal{G}.$ Write
${\mathcal{R}}=\tau_{1}\oplus\cdots\oplus\tau_{m}$ as the direct sum of
irreducible representations in $\widehat{\mathcal{G}}.$ Then
$r_{\mathcal{R}}:2^{E}\to\mathbb{R}_{\geq 0}$ is defined by

$r_{\mathcal{R}}(S)=\log_{b}\dim{\mathcal{R}}-\log_{b}\displaystyle\sum_{S\subseteq\mbox{triv}\,(\tau_{i})}\dim\tau_{i}.$

While $r_{\mathcal{R}}$ is always normalized and monotone, it may or may not
be submodular. For example, suppose $\widehat{\Gamma}$ contains a nontrivial
one-dimensional irreducible representation $\rho.$ Let $1$ be the trivial
representation of $\Gamma,~{}E=\\{1,2,3\\}$ and ${\mathcal{R}}=(1\otimes
1\otimes\rho)\oplus(1\otimes 1\otimes 1)\oplus(\rho\otimes 1\otimes 1).$ Then

$r_{\mathcal{R}}(\\{1,2\\})+r_{\mathcal{R}}(\\{2,3\\})=\log_{b}\frac{9}{4}<\log_{b}\frac{9}{3}=r_{\mathcal{R}}(\\{1,2,3\\})+r_{\mathcal{R}}(\\{2\\}).$

Nevertheless, $r_{{\mathcal{R}}(\mathcal{H})}$ does provide a formula for a
rank function based on the combinatorics of ${\mathcal{R}}(\mathcal{H})$ which
is equal to $r^{\ast}_{\mathcal{H}}.$

###### Proposition 9.20

Let $S\subseteq E.$ Then

$r^{\ast}_{\mathcal{H}}(S)=r_{{\mathcal{R}}(\mathcal{H})}(S).$

Proof:  We start with the definition,
$r^{\ast}_{\mathcal{H}}(S)=r_{\mathcal{H}}(E-S)+|{\bf{a}}_{S}|-r(E).$
Substituting $|{\bf{a}}_{S}|=|{\bf{a}}|-|{\bf{a}}_{E-S}|$ and reorganizing,

$r^{\ast}_{\mathcal{H}}(S)=(|{\bf{a}}|-r(E))-(|{\bf{a}}_{E-S}|-r_{\mathcal{H}}(E-S))=\log_{b}\bigg{(}\frac{|\mathcal{G}|}{|\mathcal{H}|}\bigg{)}-\log_{b}\bigg{(}\frac{|\mathcal{G}_{E-S}|}{|\mathcal{H}_{E-S}|}\bigg{)}.$

The dimension of ${\mathcal{R}}(\mathcal{H})$
is$\log_{b}\left(\frac{|\mathcal{G}|}{|\mathcal{H}|}\right).$ Now write
${\mathcal{R}}_{2}(\mathcal{H})=\tau_{1}\oplus\cdots\oplus\tau_{m}$ as the
direct sum of the irreducible representations in ${\mathcal{R}}(\mathcal{H})$.
The extension lemma implies that

$\log_{b}\bigg{(}\frac{|\mathcal{G}_{E-S}|}{|\mathcal{H}_{E-S}|}\bigg{)}=\log_{b}\displaystyle\sum_{S\subseteq\mbox{triv}\,(\tau_{i})}\dim\tau_{i}.$

$\square$

Once one accepts Whitney’s suggestion that the dual of a graph may or may not
be another graph, it is natural to ask for which graphs $G$ is there a graph
$G^{\prime}$ such that $M[G]^{\ast}=M[G^{\prime}].$ This question is answered
by Whitney’s previous work, [44, Theorem 29]. It says that if $G$ is a graph,
then there exists a graph $G^{\prime}$ such that $M[G]^{\ast}=M[G^{\prime}]$
if and only if $G$ is a planar graph. With a concrete definition of
$r_{{\mathcal{R}}(\mathcal{H})}$ in hand we can ask which groups, if any, play
a role similar to the role planar graphs play with graphs and matroids. For
the remainder of this section $\mathcal{G}=\Gamma^{E},~{}b=|\Gamma|$ and
${\bf{a}}={\bf{a}}[1].$

###### Definition 9.21

A finite group $\Gamma$ is closed under polymatroid duality if for all $n$ and
subgroups $\mathcal{H}$ of $\mathcal{G}=\Gamma^{n},$ there exists
$\mathcal{H}^{\prime}$ a subgroup of $\mathcal{G}$ such that
$P^{\ast}(\mathcal{H})=P(\mathcal{H}^{\prime})$

###### Theorem 9.22

A finite group $\Gamma$ is closed under polymatroid duality if and only if
$\Gamma$ is abelian.

Proof:  Suppose $\Gamma$ is not abelian. Let $\mathcal{H}$ be the diagonal
embedding of $\Gamma$ into $\Gamma^{E},~{}E=\\{x,y,z\\}.$ Then
$P(\mathcal{H})$ is isomorphic to the matroid $U_{1,3}.$ Hence $P^{\ast}$ is
isomorphic to $U_{2,3}.$ However, $U_{2,3}$ is an excluded minor for $\Gamma,$
hence there is no $\mathcal{H}^{\prime}$ such that
$P(\mathcal{H}^{\prime})=P^{\ast}(\mathcal{H}).$

Conversely, assume that $\Gamma$ is abelian. So all irreducible
representations under consideration are one-dimensional and we can choose an
isomorphism $\phi:\widehat{\Gamma}\to\Gamma$ and extend it in the obvious way
to $\bar{\phi}:\widehat{\mathcal{G}}\to\mathcal{G}.$ By Lemma 9.3,
$\rho\in\widehat{\mathcal{G}}$ is in $\mathcal{H}$ if and only if
$\mathcal{H}\subseteq\ker\rho.$ Therefore,
$\mathcal{H}^{\prime}=\bar{\phi}({\mathcal{R}}(\mathcal{H}))$ is a subgroup of
$\Gamma.$ It remains to show that
$r_{\mathcal{H}^{\prime}}=r^{\ast}_{\mathcal{H}}.$

Let $S\subseteq E.$ The surjectivity of
$\pi_{S}:\mathcal{H}^{\prime}\to\mathcal{H}^{\prime}_{S}$ and the fact that
$\mbox{triv}\,(\rho)=I(\bar{\phi}(\rho))$ imply that

$|\mathcal{H}^{\prime}_{S}|=\frac{|\mathcal{H}^{\prime}|}{|\ker\pi_{S}:\mathcal{H}^{\prime}\to\mathcal{H}^{\prime}_{S}|}=\frac{|\mathcal{G}|/|\mathcal{H}|}{|h^{\prime}\in\mathcal{H}^{\prime}:S\subseteq
I(h^{\prime})|}=\frac{|\mathcal{G}|/|\mathcal{H}|}{|\rho\in{\mathcal{R}}(\mathcal{H}):S\subseteq\mbox{triv}\,(\rho)|}$
$=\frac{|\Gamma|^{|E|}/|\mathcal{H}|}{|\mathcal{G}_{E-S}|/|\mathcal{H}_{E-S}|}$

The last equal sign follows from the extension lemma. Applying
$\log_{b}=\log_{|\Gamma|}$ to both sides results in

$r_{\mathcal{H}^{\prime}}(S)=|E|-|E-S|-r_{\mathcal{H}}(E)+r_{\mathcal{H}}(E-S)=r^{\ast}_{\mathcal{H}}(S).$

$\square$

##  10 Group codes and the Tutte polynomial

In this section we give a introduction to group codes and the Tutte polynomial
of a polymatroid. We also give a glimpse at how ${\mathcal{R}}(\mathcal{H})$
acts as a dual code for a group code $\mathcal{H}$ through the MacWilliams
identity for the weight enumerator of a code. For a close look at how
${\mathcal{R}}(\mathcal{H})$ gives one possible answer for Dougherty, Kim and
Sole’s open problem, “Is there a duality and MacWilliams formula for codes
over non-Abelian group?” [9, Open Question 4.3], which includes MacWiliams
identity for the complete weight enumerator, see [42]. Throughout this section
$\mathcal{G}=\Gamma^{n}$ where $\Gamma$ is a finite group.

A code of length $n$ consists of a finite alphabet $\mathcal{A}$ and a subset
$\mathcal{C}\subseteq\mathcal{A}^{n}.$ The elements of $\mathcal{C}$ are
called code words. When $\mathcal{A}$ is a finite field ${\mathbb{F}}$ and
$\mathcal{C}$ a subspace of the ${\mathbb{F}}$-vector space
${\mathbb{F}}^{n}$, the code is called an ${\mathbb{F}}$-linear code. One of
the most important invariants of an ${\mathbb{F}}$-linear code is its weight
enumerator.

Let $\mathcal{C}$ be an ${\mathbb{F}}$-linear code. Given $c\in\mathcal{C}$
the weight of $c$ is $w(c)=|\\{i:c_{i}\neq 0\\}|.$ The weight enumerator of
$\mathcal{C}$ is

$W_{\mathcal{C}}(t)=\displaystyle\sum_{c\in\mathcal{C}}t^{w(c)}.$

The Crapo-Rota critical theorem makes it clear that for an
${\mathbb{F}}$-linear code $\mathcal{C},$ its matroid $M[\mathcal{C}]$
determines $W_{\mathcal{C}}.$ This was made precise by Greene via the Tutte
polynomial of $M[\mathcal{C}]$ [20].

The Tutte polynomial of a matroid $M$ is a two-variable integer polynomial
invariant $T_{M}(u,v),$ defined by

$T_{M}(u,v)=\displaystyle\sum_{S\subseteq
E}(u-1)^{r(E)-r(S)}(v-1)^{|S|-r(S)}.$

The applications of the Tutte polynomial are far too numerous to cover
adequately here. For a sampling of applications, history and theory of the
Tutte polynomial see [15]. An alternative definition of the Tutte polynomial
is through deletion/contraction and induction.

###### Proposition 10.1

  * •

If $M$ is the empty matroid, then $T_{M}(u,v)=1.$

  * •

If $x$ is a coloop of $M,$ then $T_{M}(u,v)=u~{}T_{M\setminus x}(u,v).$

  * •

If $x$ is a loop of $M,$ then $T_{M}(u,v)=v~{}T_{M/x}(u,v).$

  * •

If $x$ is neither a loop nor a coloop, then $T_{M}(u,v)=T_{M\setminus
x}(u,v)+T_{M/x}(u,v).$

The proof of this proposition is to split the sum over all subsets $S$ of $E$
into those which do not contain $x$ and those which do contain $x.$ Then first
sum can be written in terms of $T_{M\setminus x}(u,v)$ and the latter can be
written in terms of $T_{M/x}(u,v).$ The exact same idea allows one to sum up
the last three cases into a single equation which can be applied to any $x\in
E.$

$T_{M}(u,v)=(u-1)^{r(E)-r(E-x)}T_{M\setminus
x}(u,v)+(v-1)^{1-r(\\{x\\})}T_{M/x}(u,v).$ (10)

We will use this recursive formula for the Tutte polynomial in the proof of
Theorem 10.3 below.

###### Theorem 10.2

(Greene’s theorem) [20] Let $\mathcal{C}$ be an ${\mathbb{F}}$-linear code,
$q=|{\mathbb{F}}|,$ and $d=\dim_{\mathbb{F}}\mathcal{C}.$ Then

$W_{\mathcal{C}}(t)=(1-t)^{d}~{}t^{n-d}~{}T_{M[\mathcal{C}]}\bigg{(}\frac{1+(q-1)t}{1-t},\frac{1}{t}\bigg{)}.$

There have been several suggested extensions of the Tutte polynomial to
integer polymatroids [2], [7], [32]. For subcardinal polymatroids, the
simplest way to extend the Tutte polynomial is to use exactly the same
definition. Of course, if $P$ is not an integer polymatroid, then $T_{P}(u,v)$
will not be a polynomial. In addition, it is not clear how to define
$T_{P}(u,v)$ when $x<1$ or $y<1.$ Nonetheless, Greene’s theorem holds without
change for group codes.

A $\Gamma$-code of length $n$ is a code whose alphabet is a finite group
$\Gamma$ and whose set of codewords is a subgroup $\mathcal{H}$ of
$\mathcal{G}=\Gamma^{n}.$ The weight of a codeword
$\gamma=\\{\gamma_{1},\dots,\gamma_{n}\\}$ is $w(\gamma)=|\\{i:\gamma_{i}\neq
1_{\Gamma}\\}|.$ The weight enumerator of a $\Gamma$-code $\mathcal{H}$ is
$W_{\mathcal{H}}(t)=\displaystyle\sum_{h\in\mathcal{H}}t^{w(h)}.$ When
$\Gamma$ is the additive group of a finite field ${\mathbb{F}}$ and
$\mathcal{H}$ is a subspace of the vector space ${\mathbb{F}}^{n},$ then this
definition of the weight of a codeword and of the weight enumerator of the
code are the same as for ${\mathbb{F}}$-linear codes.

###### Theorem 10.3

(Greene’s theorem for group codes) Let $\Gamma$ be a finite group,
$q=|\Gamma|,$ and $\mathcal{H}$ a $\Gamma$-code of length $n\geq 1.$ In
addition, set $P(\mathcal{H})$ to be the polymatroid $(E,r_{\mathcal{H}}),$
where $E=[n].$ Then,

$W_{\mathcal{H}}(t)=(1-t)^{r(E)}t^{n-r(E)}~{}T_{P(\mathcal{H})}\bigg{(}\frac{1+(q-1)t}{1-t},\frac{1}{t}\bigg{)}$
(11)

The first proof of this theorem was by the third author in [49]. That proof
involved interpreting $t$ as a probability. Since (11) is not clearly defined
for $t\leq 0$ or $t\geq 1$ such a proof seems highly appropriate. Here we give
a deletion/contraction proof using (10).

Proof:  The induction starts with $n=1$ where the definitions show that both
sides of (11) are equal to $|\mathcal{H}|-1.$ For notational convenience we
suppress all references to $\mathcal{H}$ when discussing $P(\mathcal{H})$ and
$r_{\mathcal{H}}.$ We start by determining a deletion/contraction formula for
$W_{\mathcal{H}}(t).$

Let $x\in E$ and $h\in\mathcal{H}.$ If $h_{x}=1_{\Gamma},$ then
$w(h)=w(\pi_{E-\\{x\\}}(h)).$ Otherwise, $w(h)=w(\pi_{E-\\{x\\}}(h))+1.$ Since
$\pi_{E-\\{x\\}}$ is surjective, the cardinality of the preimage of every
$h^{\prime}\in\mathcal{H}_{E-\\{x\\}}$ is

$\frac{|\mathcal{H}|}{|\mathcal{H}_{E-\\{x\\}}|}=|\Gamma|^{r(E)-r(E-\\{x\\})}=q^{(r(E)-r(E-\\{x\\})}.$

Now, $K=\\{h\in\mathcal{H}:h_{x}=1_{\Gamma}\\}$ represents the contraction
$P/x.$ For every $h\in K,~{}w(h)=w(\pi_{E-\\{x\\}}(h)).$ We conclude that

$W_{\mathcal{H}}(t)=q^{r_{\mathcal{H}}(E)-r_{\mathcal{H}}(E-\\{x\\})}\cdot
t\cdot W_{\mathcal{H}_{E-\\{x\\}}}(t)+(1-t)W_{\mathcal{H}/x}(t).$ (12)

The induction hypothesis, some algebra, and (10) imply,

$W_{\mathcal{H}}(t)=q^{r_{\mathcal{H}}(E)-r_{\mathcal{H}}(E-\\{x\\})}\cdot
t\cdot t^{n-1-r(E-\\{x\\})}\cdot(1-t)^{r(E-\\{x\\})}T_{P(\mathcal{H})\setminus
x}\bigg{(}\frac{1+(q-1)t}{1-t},\frac{1}{t}\bigg{)}$ $+$
$\bigg{(}1-t\bigg{)}\bigg{(}t^{n-1-(r(E)-r(\\{x\\})}(1-t)^{r(E)-r(\\{x\\})}\bigg{)}T_{P(\mathcal{H})/x}\bigg{(}\frac{1+(q-1)t}{1-t},\frac{1}{t}\bigg{)}$
$=t^{n-r(E)}(1-t)^{r(E)}\bigg{[}(\frac{qt}{1-t})^{r(E)-r(E-\\{x\\})}T_{P(\mathcal{H})\setminus
x}\bigg{(}\frac{1+(q-1)t}{1-t},\frac{1}{t}\bigg{)}\bigg{]}$ $+$
$t^{n-r(E)}(1-t)^{r(E)}\bigg{[}(\frac{1-t}{t})^{1-r(\\{x\\})}T_{P(\mathcal{H})/x}\bigg{(}\frac{1+(q-1)t}{1-t},\frac{1}{t}\bigg{)}\bigg{]}$
$=t^{n-r(E)}(1-t)^{r(E)}T_{P(\mathcal{H})}\bigg{(}\frac{1+(q-1)t}{1-t},\frac{1}{t}\bigg{)}$

$\square$

In order to understand the dual relationship between $\mathcal{H}$ and
${\mathcal{R}}(\mathcal{H})$ we need to establish in what sense
${\mathcal{R}}(\mathcal{H})$ can be thought of as a code, and what the analog
of $W_{\mathcal{H}}$ is for ${\mathcal{R}}(\mathcal{H}).$ We leave the
discussion of how one can view ${\mathcal{R}}(\mathcal{H})$ as a code, the
proof of Theorem 10.5 below, and an explanation of how
${\mathcal{R}}(\mathcal{H})$ also satisfies a MacWilliams identity for the
complete weight enumerator for [42].

In looking for an interpretation of the weight enumerator of
${\mathcal{R}}(\mathcal{H})$ the same principle as in Section 7 applies here.
The trivial representation replaces the identity of the group and dimension
stands in for counting.

###### Definition 10.4

Let $\rho\in\widehat{\mathcal{G}}.$ The weight of $\rho$ is
$w(\rho)=n-|\mbox{triv}\,(\rho)|.$ The weight enumerator of
${\mathcal{R}}(\mathcal{H})$ is

$W_{{\mathcal{R}}(\mathcal{H})}(t)=\displaystyle\sum_{\rho\in{\mathcal{R}}(\mathcal{H})}(\dim\rho)~{}t^{w(\rho)}.$

###### Theorem 10.5

[42] (Greene’s theorem for ${\mathcal{R}}(\mathcal{H})$) Let $(E,r)$ be the
polymatroid $P(\mathcal{H})$ and $q=|\Gamma|.$ Then

$W_{{\mathcal{R}}(\mathcal{H})}(t)=t^{r(E)}\cdot(1-t)^{n-r(E)}T_{P(\mathcal{H})}\bigg{(}\frac{1}{t},\frac{1+(q-1)t}{1-t}\bigg{)}.$

Proof:  See [42]. $\square$

###### Theorem 10.6

(MacWilliams identity for groups) Let $(E,r)$ be the polymatroid
$P(\mathcal{H})$ and $q=|\Gamma|.$ Then

$W_{{\mathcal{R}}(\mathcal{H})}(t)=\frac{(1+(q-1)t)^{n}}{q^{r(E)}}W_{\mathcal{H}}\bigg{(}\frac{1-t}{1+(q-1)t}\bigg{)}.$

Proof:  The proof is identical to Greene’s proof of the MacWilliams identity
for linear codes [20]. $\square$

##  11 Combinatorial Laplacian

In this last section we examine the connection between
${\mathcal{R}}(\mathcal{H})$ and the combinatorial Laplacian. Throughout this
section $E=[n].$ If a polymatroid $(E,r_{\mathcal{H}})$ has no elements $x$
such that $r_{\mathcal{H}}(E)>r_{\mathcal{H}}(E-x),$ then
${\mathcal{R}}(\mathcal{H})$ has a concrete realization as the eigenspaces of
the combinatorial Laplacian of an associated quotient space described below.
This will lead us to relate the eigenvalues of the combinatorial Laplacian of
the top dimension of these quotient spaces to the code weight enumerator of
$\mathcal{H}$ viewed as a code with alphabet $\Gamma.$ This result was
originally proved for binary matroids by the third author, and provides
another example of how ${\mathcal{R}}(\mathcal{H})$ behaves like Whitney’s
subspace realization of the dual of a nonplanar graph [49]. We finish the
section by using the combinatorial Laplacian to establish a topological
interpretation of the Crapo-Rota critical theorem for finite groups.

The combinatorial Laplacian can be defined for any (locally finite) regular CW
complex. We will work with regular CW complexes all of whose closed cells are
simplices. Since Stanley’s paper, [38], these types of complexes are usually
called simplicial posets in the combinatorics literature. The name is derived
from the fact that in the face poset of the complex every lower interval is
isomorphic to the face poset of a simplex. Other names for simplicial posets
include Boolean cell complexes and semi-simplicial complexes. Independent of
the name, the reader will not go wrong in thinking of them as simplicial
complexes where there may be several faces with the same vertex set. A bigon,
two vertices with two parallel edges, is the smallest possible example of a
simplicial poset which is not a simplicial complex.

Let $X$ be a finite simplicial poset. We use $C_{j}(X)$ for the simplicial
$j$-chains of $X$ with complex coefficients. Equivalently, we denote the
$j$-dimensional faces of $X$ by $F_{j}(X)$ and
$C_{j}(X)=\mathbb{C}[F_{j}(X)].$ When a specific identification
$u\leftrightarrow u^{\ast}$ between $C_{j}(X)$ and its dual $C_{j}(X)^{\ast}$
is needed, we use the one implied by declaring the preferred basis
$\\{w_{\sigma}:\sigma\in F_{j}(X)\\}$ an orthonormal basis of $C_{j}(X).$ As
usual, $\partial_{j}(X):C_{j}(X)\to C_{j-1}(X)$ denotes the boundary map. The
empty set is a face of dimension minus one, so
$C_{-1}(X)=\mathbb{C}[\emptyset]$ and $C_{j}=\\{0\\}$ for all $j<-1$ and
$j>\dim X.$ For all $j$ we define $\Delta_{j}(X):C_{j}(X)\to C_{j}(X)$ by

$\Delta_{j}(X)=\partial^{t}_{j}(X)\circ\partial_{j}(X)+\partial_{j+1}(X)\circ\partial^{t}_{j+1}(X),$

where $t$ indicates the transpose.

The $\Delta_{j}(X)$ are collectively known as the combinatorial Laplacian of
$X.$ The combinatorial Laplacian has several properties. Among them:

  * •

Each $\Delta_{j}(X)$ is diagonalizable with nonnegative real eigenvalues.

  * •

$\ker\Delta_{j}(X)\cong H^{j}(X;\mathbb{C})\cong H_{j}(X;\mathbb{C}).$ (Hodge
theorem)

  * •

It is possible to approximate the usual Laplacian on a compact Riemannian
manifold by using the combinatorial Laplacian on an appropriate sequence of
triangulations of the maniold [10].

Several authors have studied situations in which the eigenvalues of the
combinatorial Laplacian are integers. These include, chessboard complexes
[16], matroid independence complexes [24], matching complexes [12], shifted
complexes [11]. Representation theory has figured in some of these results
([12], [16]).

In order to describe the quotient spaces associated to
$\mathcal{H}\leq\mathcal{G}=\displaystyle\sum^{n}_{i=1}\Gamma_{i},$ we begin
by viewing every $\Gamma_{i}$ as a zero-dimensional simplicial complex with
$|\Gamma_{i}|$ vertices. Let $X$ be the simplicial join,

$X=\Gamma_{1}\star\cdots\star\Gamma_{n}.$

The facets of $X$ are easily identified with the elements of $\mathcal{G}$ and
the vertices of $X$ are equal to the disjoint union of all of the
$\Gamma_{i},$ where all of the $\Gamma_{i}$ are disjoint sets even if they are
isomorphic as groups. In general, the faces of $X$ can be identified with the
union of all of the $\mathcal{G}_{S}$ as $S$ runs over all of the subsets of
$[n].$ In particular
$|F_{j}(X)|=\displaystyle\sum_{|S|=j+1}|\mathcal{G}_{S}|.$

Let $\mathcal{G}$ act on the vertices of $X$ so that
$(\gamma_{1},\dots,\gamma_{n})\cdot
v_{i}=v_{i}\cdot\gamma_{i}^{-1},~{}v_{i}\in\Gamma_{i}.$ Extend this action to
all the faces of $X.$ For instance, if
$\gamma=(\gamma_{1},\dots,\gamma_{n})\in\mathcal{G}$ and
$F=v_{1}\star\cdots\star v_{n}$ is a facet of $X,$ then $\gamma\cdot F$ is
$v_{1}\cdot\gamma^{-1}_{1}\star\cdots\star v_{n}\gamma^{-1}_{n}.$ Restricting
the $\mathcal{G}$-action to $\mathcal{H}$ gives us a quotient space
$X/\mathcal{H}$ which is a simplicial poset. The faces of $X/\mathcal{H}$ can
be identified with the right cosets of $\mathcal{G}_{S}/\mathcal{H}_{S}$ where
$S$ runs over all subsets of $[n].$ When $\Gamma_{i}=\mathbb{Z}/2\mathbb{Z}$
for all $i,$ such quotient spaces were studied under the name binary spherical
quotients by the first author in [39] and [40]. The first determination of the
eigenvalues and eigenvectors of the top dimension of the combinatorial
Laplacian for binary spherical quotients was by the third author in [49]. In
this case, $M[\mathcal{H}]$ is a binary matroid with $\mathcal{H}$ a subspace
of $(\mathbb{Z}/2\mathbb{Z})^{n}$ and $M[\mathcal{H}]^{\ast}$ is represented
by the subspace $\mathcal{H}^{\perp}$ of vectors in
$(\mathbb{Z}/2\mathbb{Z})^{n}$ orthogonal to $\mathcal{H}.$

###### Theorem 11.1

[49, Theorem 6] Suppose $M[\mathcal{H}]$ is a binary matroid with no coloops.
Then each $h\in\mathcal{H}^{\perp}$ contributes an eigenvalue of $2|Z(h)|$ to
the eigenvalues of $\Delta_{n-1}(X/\mathcal{H}).$

For $h\in\mathcal{H}^{\perp},$ its code weight enumerator, $w(h),$ equals
$n-Z(h).$ Hence, for (binary) linear codes $\mathcal{H},$ the eigenvalues of
$\Delta_{n-1}(X/\mathcal{H})$ carry the same information as the code weight
enumerator of $\mathcal{H}.$ The top dimensional eigenvalues of the
combinatorial Laplacian of a matroid independence complex determine the
homotopy type of the complex [24]. In contrast, the top dimensional
eigenvalues of the combinatorial Laplacian of $X/\mathcal{H}$ do not determine
the homotopy type of $X/\mathcal{H}.$

###### Example 11.2

Consider the following two binary matrices,

$A=\begin{bmatrix}1&1&0&0&0&0\\\ 0&0&1&1&0&0\\\ 0&0&0&0&1&1\\\ \end{bmatrix},\
\ B=\begin{bmatrix}1&0&0&1&1&1\\\ 0&1&0&1&0&0\\\ 0&0&1&1&0&0\end{bmatrix}.$

Set $\mathcal{H}(A)$ and $\mathcal{H}(B)$ to be their corresponding row spaces
in $(\mathbb{Z}/2\mathbb{Z})^{6}.$ Let $X$ be the join of
$\mathbb{Z}/2\mathbb{Z}$ with itself six times. Equivalently, $X$ is the
boundary of the $5$-dimensional cross polytope. Theorem 11.1 tells us that
$\Delta_{5}(X/\mathcal{H}(A))$ and $\Delta_{5}(X/\mathcal{H}(B))$ have the
same spectrum. On the other hand, $X/\mathcal{H}(A)$ is homeomorphic to
$S^{5}$ [40, Theorem 4], and $X/\mathcal{H}(B)$ is homeomorphic to the double
suspension of $\mathbb{R}P^{3}$ [39, Theorem 6.3.1].

What if the binary matroid represented by $\mathcal{H}$ has a coloop? Suppose
$x\in E$ is a coloop of the binary matroid $M[\mathcal{H}].$ Let
$\mathcal{G}^{\prime}=\mathcal{G}_{E-\\{x\\}},\mathcal{H}^{\prime}=\mathcal{H}_{E-\\{x\\}}$
and set $X^{\prime}/\mathcal{H}^{\prime}$ to be the quotient space coming from
$\mathcal{G}^{\prime}$ and $\mathcal{H}^{\prime}.$ Then $X/\mathcal{H}$ is a
cone over $X^{\prime}/\mathcal{H}^{\prime}$ [40, Proposition 3] and $\lambda$
is an eigenvalue with multiplicity $m$ for $\Delta_{n-1}(X/\mathcal{H})$ if
and only if $\lambda-1$ is an eigenvalue for
$\Delta_{n-2}(X^{\prime}/\mathcal{H}^{\prime})$ with multiplicity $m$ [11,
Corollary 4.11]. In particular, all of the eigenvalues of
$\Delta_{n-1}(X/\mathcal{H})$ are integers. This is true in much greater
generality.

Let $\mathcal{J}$ be a finite group and $U$ a $\mathcal{J}$-set. We say that
the action of $\mathcal{J}$ is effectively free if the action of $\mathcal{J}$
on $U$ modulo its kernel is free. For instance, for all $x\in
E,~{}\mathcal{H}$ acts effectively freely on $\Gamma_{x}$ by restricting the
action to the $x$-coordinate of $h\in\mathcal{H}.$ Let $Y_{1},\dots,Y_{n}$ be
finite disjoint $\mathcal{J}$-sets on which $\mathcal{J}$ acts effectively
freely. Think of each $Y_{i}$ as a discrete subset of vertices and set
$Y=Y_{1}\star\cdots\star Y_{n}$ to be the join of all of the $Y_{i}$ as a
simplicial complex. Again, since $\mathcal{J}$ acts on the vertices of $Y$ it
also acts on all of the faces of $Y$ and the quotient space $Y/\mathcal{J}$ is
a simplicial poset.

###### Theorem 11.3

The eigenvalues of $\Delta_{n-1}(Y/\mathcal{J})$ are integers.

Proof:  We proceed by induction on $|\mathcal{J}|.$ For the base case, assume
that $\mathcal{J}$ is the trivial group. When $n=1,~{}Y$ is a finite set of
vertices, $C_{0}(Y)=\mathbb{C}[Y]$ and $C_{-1}(Y)=\mathbb{C}[\emptyset].$ By
definition, $\Delta_{0}(Y)$ is multiplication by a $|Y|\times|Y|$ matrix of
all ones. Therefore, the eigenvalues of $\Delta_{0}(Y)$ are $|Y|,$ with
multiplicity one, and $0$ with multiplicity $|Y|-1.$ Let $\\{w_{y}\\}_{y\in
Y}$ be the preferred basis for $\mathbb{C}_{0}[Y]=\mathbb{C}[Y].$ An
eigenvector for the $|Y|$-eigenspace is $\displaystyle\sum_{y\in Y}w_{y}.$ The
eigenvectors for the $0$-eigenspace are all vectors of the form

$\displaystyle\sum_{y\in Y}c_{y}w_{y},~{}\displaystyle\sum_{y\in Y}c_{y}=0.$

For $n>1,$ we first observe that $C_{n-1}(Y)=C_{0}(Y_{1})\otimes\cdots\otimes
C_{0}(Y_{n})$ and apply [11, Theorem 4.10] to see that that if
$\\{v_{i}\\}^{n}_{i=1}$ are eigenvectors of $\Delta_{0}(Y_{i})$ with
corresponding eigenvalues $\lambda_{i},$ then $v_{1}\otimes\cdots\otimes
v_{n}$ is an eigenvector of $\Delta_{n-1}(Y)$ with eigenvalue
$\lambda_{1}+\cdots+\lambda_{n}.$ There are enough eigenvectors of this form
to produce a basis of $C_{n-1}(Y).$ Therefore $\Delta_{n-1}(Y)$ has integral
eigenvalues.

Now suppose $\mathcal{J}$ is not trivial. Let $\mathcal{J}_{i}$ be the kernel
of the $\mathcal{J}$-action on $Y_{i}.$ All of the $\mathcal{J}_{i}$ are
normal subgroups of $\mathcal{J}.$ The kernel of the $\mathcal{J}$ action on
$F_{n-1}(Y)$ is $\displaystyle\cap^{n}_{i=1}\mathcal{J}_{i}.$ Since we are
only concerned with the quotient space $Y/\mathcal{J}$, we might as well
assume that this kernel is trivial and hence $\mathcal{J}$ acts freely on
$F_{n-1}(Y).$ We consider two cases.

One, the $\mathcal{J}$-action on $F_{n-2}(Y)$ is also free. We can
characterize this case by looking at the subgroups
$\mathcal{K}_{j}=\displaystyle\cap_{i\neq j}\mathcal{J}_{i}.$ The
$\mathcal{J}$-action on $F_{n-2}(Y)$ is free if and only if for all
$j,~{}\mathcal{K}_{j}=\\{1_{\mathcal{J}}\\}.$ In this case, let
$\pi:F_{n-1}(Y)\to F_{n-1}(Y/\mathcal{J})$ be the quotient map and extend
$\pi$ linearly to $p:C_{n-1}(Y)\to C_{n-1}(Y/\mathcal{J}).$ Suppose $\sigma$
and $\tau$ are facets of $Y$ and
$\sigma^{\prime}=p(\sigma),\tau^{\prime}=p(\tau).$ As usual, we let
$C^{\ast}_{n-1}(Y),C^{\ast}_{n-1}(Y/\mathcal{J}),p^{\ast}$ and
$\Delta^{\ast}_{n-1}$ denote the various dual spaces and maps. Since
$\Delta_{n-1}$ is symmetric, the matrices representing $\Delta_{n-1}$ and
$\Delta^{\ast}_{n-1}$ are the same. What is the entry of $\Delta_{n-1}(Y)$
corresponding to row $\sigma$ and column $\tau?$ Along the diagonal every
entry is $n.$ If $\sigma\neq\tau,$ then the entry is the number of
codimension-one faces $\sigma$ and $\tau$ have in common. When the action of
$\mathcal{H}$ on $F_{n-2}$ is free, the exact same statement holds for the
entry corresponding to $\sigma^{\prime}$ and $\tau^{\prime}$ in
$\Delta_{n-1}(Y/\mathcal{J}).$ This is enough to see that if $u$ is an
eigenvector of $\Delta_{n-1}(Y/\mathcal{J})$ with eigenvalue $\lambda,$ then
$p^{\ast}(u^{\ast})$ is an eigenvector of $\Delta^{\ast}_{n-1}(Y)$ with
eigenvalue $\lambda$ which we already know is an integer.

Two, the $\mathcal{J}$-action on $F_{n-2}(Y)$ is not free. So we can choose
$j$ such that $|\mathcal{K}_{j}|>1.$ For notational convenience we assume
$j=n.$ Let $Y^{\prime}=Y/\mathcal{K}_{n}=Y_{1}\star\cdots\star
Y_{n-1}\star(Y_{n}/\mathcal{K}_{n}).$ Then
$Y/\mathcal{J}=Y^{\prime}/(\mathcal{J}/\mathcal{K}_{n})$ and the induction
hypothesis applied to $\mathcal{J}/\mathcal{K}_{n}$ finishes the proof.

$\square$

###### Corollary 11.4

The eigenvalues of $\Delta_{n-1}(X/\mathcal{H})$ are all integers.

It is tempting to conjecture that the eigenvalues of
$\Delta_{i}(Y/\mathcal{J})$ are integers for all $0\leq i\leq n-1.$ The
following example due to A. Chen shows that even if $Y=X/\mathcal{H}$ this
might be already false in codimension one and $\Delta_{0}.$

###### Example 11.5

[6] Let $\Gamma=\mathbb{Z}/6\mathbb{Z},~{}n=3$ and $\mathcal{H}$ be the
subgroup generated by $(\bar{1},\bar{2},\bar{3})$ and
$(\bar{2},\bar{1},\bar{4}).$ Then $X$ has three vertices $v_{1},v_{2},$ and
$v_{3}.$ There are two edges between $v_{1}$ and $v_{2},$ one edge between
$v_{1}$ and $v_{3}$ and three edges between $v_{2}$ and $v_{3}.$ The
eigenvalues of $\Delta_{0}(X/\mathcal{H})$ are $0,6+\sqrt{3}$ and
$6-\sqrt{3}.$

While the eigenvalues of $\Delta_{i}$ may not be integers for general
$X/\mathcal{H},$ P. Mao proved that the eigenvalues of all of the $\Delta_{i}$
are integers if $X/\mathcal{H}$ is a binary spherical quotient [26]. This has
been extended by Chen to any $\mathcal{H}\leq\mathcal{G}$ when
$P(\mathcal{H})$ is matroid [6].

Looking at Theorem 11.1 we are led to ask “For general $\mathcal{G}$ and
$\mathcal{H}$ what is the analog of no coloops for a binary matroid?” A binary
matroid realized by $\mathcal{H}\leq(\mathbb{Z}/2\mathbb{Z})^{n}$ has no
coloops if and only if there is no element $h\in\mathcal{H}$ which is all
$0$’s except for a single $1.$ An essentially identical statement applies to
any matroid represented over a field. In terms of the additive group of the
vector space $(\mathbb{Z}/2\mathbb{Z})^{n}$ this is the same as saying that
there is no element $h\in\mathcal{H}$ all of whose coordinates except exactly
one are the identity. A third way of saying the same thing is to observe that
these two conditions are equivalent to the action of $\mathcal{H}$ on
$F_{n-2}(X)$ being free. By (2) all of these conditions are the same as
$r_{\mathcal{H}}(E-\\{x\\})=r_{\mathcal{H}}(E).$

In contrast to matroids represented over a field,
$r_{\mathcal{H}}(E-\\{x\\})<r_{\mathcal{H}}(E)$ does not imply that
$r_{\mathcal{H}}(E)=r_{\mathcal{H}}(E-\\{x\\})+r_{\mathcal{H}}(\\{x\\}).$ For
instance, if $\alpha:\Gamma\to\Gamma$ is any nontrivial homomorphism which is
not an automorphism, then
$\mathcal{H}=\\{(\gamma,\alpha(\gamma)):\gamma\in\Gamma\\}\subseteq\Gamma^{2}$
has $0<r_{\mathcal{H}}(\\{2\\})<r_{\mathcal{H}}(\\{1,2\\}),$ but
$r_{\mathcal{H}}(\\{1,2\\})=r_{\mathcal{H}}(\\{1\\}),$ so
$r_{H}(\\{1,2\\})<r_{\mathcal{H}}(\\{1\\})+r_{\mathcal{H}}(\\{2\\}).$ In order
to get a more detailed understanding of the the combinatorial Laplacian on
$X/\mathcal{H}$ along the lines of Theorem 11.1 we first write down the
eigenvalues and eigenspaces of $X$ in terms of the irreducible representations
of $\Gamma$ and $\mathcal{G}.$ Identify $\mathbb{C}[\mathcal{G}]$ with
$C_{n-1}(X)$ using their usual isomorphisms with
$\mathbb{C}[\Gamma_{1}]\otimes\cdots\otimes\mathbb{C}[\Gamma_{n}].$

###### Proposition 11.6

Let $W$ be a $\mathcal{G}$-invariant subspace of $\mathbb{C}[\mathcal{G}]$
equivalent to an irreducible representation
$\rho=\rho_{1}\otimes\cdots\otimes\rho_{n}$ of $\mathcal{G}.$ Then $W$
consists of eigenvectors of $\Delta_{n-1}(X)$ all of which have eigenvalue
equal to $\displaystyle\sum_{x\in\mbox{triv}\,(\rho)}|\Gamma_{x}|.$ Since
$C_{n-1}(X)$ is the direct sum of such $W$, this describes all of the
eigenvalues and eigenvectors of $\Delta_{n-1}(X).$

Proof:  First consider $n=1.$ As in the proof of Theorem 11.3, $\Delta_{0}(X)$
is a $|\Gamma|\times|\Gamma|$ matrix all of whose entries are $1.$ So it has
two eigenvalues, $|\Gamma|$ and $0.$ The $|\Gamma|$-eigenspace is one-
dimensional and has eigenvector
$\displaystyle\sum_{\gamma\in\Gamma}v_{\gamma}.$ The zero-eigenspace is
$(n-1)$-dimensional and consists of all vectors in $C_{0}(X)$ of the form

$\displaystyle\sum_{\gamma\in\Gamma}a_{\gamma}v_{\gamma},~{}\displaystyle\sum_{\gamma\in\Gamma}a_{\gamma}=0.$

From this we see that $|\Gamma|$-eigenspace is the invariant subspace of
$C_{0}(X)=\mathbb{C}[\Gamma]$ corresponding to the trivial representation and
that the zero-eigenspace is the direct sum of all other irreducible invariant
subspaces of the regular representation of $\Gamma.$ For $n>0$ apply this to
[11, Proposition 4.9]. $\square$

As in the proof of Theorem 11.3, we let $p:C_{n-1}(X)\to
C_{n-1}(X/\mathcal{H})$ be the map induced by the quotient map. We also let
$\ast$ denote the various duals of vector spaces, maps, and elements.

###### Theorem 11.7

Suppose $r_{\mathcal{H}}(E-x)=r_{\mathcal{H}}(E)$ for all $x\in E.$ Let $u$ be
an eigenvector of $\Delta_{n-1}(X/\mathcal{H})$. Then
$\rho=p^{\ast}(u^{\ast})$ is in ${\mathcal{R}}(\mathcal{H})_{1}.$ The
eigenvalue associated to $u$ is
$\displaystyle\sum_{x\in\mbox{triv}\,(\rho)}|\Gamma_{x}|.$

When $\Gamma_{x}=\mathbb{Z}/2\mathbb{Z}$ for all $x\in E$ this is equivalent
to Theorem 11.1.

Proof:  Since $r_{\mathcal{H}}(E-x)=r_{\mathcal{H}}(E)$ for all $x\in
E,~{}\mathcal{H}$ acts freely on $F_{n-1}(X)$ and $F_{n-2}(X).$ Now, with
$\mathcal{H}$ playing the role of $\mathcal{J}$ and every $Y_{i}=\Gamma_{i},$
we follow the proof of Theorem 11.3 to the point that we know that if $u$ is
an eigenvector of $\Delta_{n-1}(X/\mathcal{H})$ with eigenvalue $\lambda,$
then $p^{\ast}(u^{\ast})$ is an eigenvector of $\Delta_{n-1}(X)$ with
eigenvalue $\lambda.$ By definition, the coefficients of $p^{\ast}(u^{\ast})$
are constant on cosets of $\mathcal{H}$ and hence $p^{\ast}(u^{\ast})$ is in
${\mathcal{R}}(\mathcal{H})_{1}.$ $\square$

###### Corollary 11.8

Suppose $r_{\mathcal{H}}(E-x)=r_{\mathcal{H}}(E)$ for all $x\in E.$ Then
$\lambda$ is an eigenvalue of $\Delta_{n-1}(X/\mathcal{H})$ if and only if
there exists $\rho\in{\mathcal{R}}(\mathcal{H})$ such that
$\lambda=\displaystyle\sum_{x\in\mbox{triv}\,(\rho)}|\Gamma_{x}|.$ The
multiplicity of $\lambda$ is

$\displaystyle\sum_{\rho\in{\mathcal{R}}(\mathcal{H})}\dim\rho,$

where the sum is taken over all $\rho\in{\mathcal{R}}(\mathcal{H})$ such that
$\displaystyle\sum_{x\in\mbox{triv}\,(\rho)}|\Gamma_{x}|=\lambda.$

Proof:  Since $p:C_{n-1}(X)\to C_{n-1}(X/\mathcal{H})$ is surjective,
$p^{\ast}$ is injective. The dimension of
$C_{n-1}(X/\mathcal{H})=|F_{n-1}(X/\mathcal{H})|=|\mathcal{G}/\mathcal{H}|=\dim{\mathcal{R}}(\mathcal{H}).$

$\square$

###### Remark 11.9

If $r_{\mathcal{H}}(A\cup\\{x\\})=r_{\mathcal{H}}(A)$ for all $A\subseteq
E,~{}|A|\geq n-i,x\in E,$ then similar arguments determine all the eigenvalues
and eigenspaces of $\Delta_{n-i}(X/\mathcal{H})$ in representation theoretic
terms. Thus, under the same conditions, the spectrum of
$\Delta_{n-i}(X/\mathcal{H})$ only depends on $P(\mathcal{H}).$

We end by using $\Delta_{n-1}(X/\mathcal{H})$ to interpret the dual Crapo-Rota
critical theorem for finite groups as a statement about the topology of
$X/\mathcal{H}.$

###### Theorem 11.10

The dimension of $H_{n-1}(X/\mathcal{H};\mathbb{C})$ is

$\displaystyle\sum_{\stackrel{{\scriptstyle\rho\in{\mathcal{R}}(\mathcal{H})}}{{\mbox{triv}\,\rho=\emptyset}}}\dim\rho={\chi}_{P(\mathcal{H})^{\ast}}(|\Gamma|).$
(13)

Proof:  The equality in (13) is the dual Crapo-Rota critical theorem for
finite groups with $k=1.$ Here we give an independent topological proof.

The known formulas for the homology of the join of simplicial complexes show
that the only nontrivial reduced homology group of $X$ is
$\tilde{H}_{n-1}(X).$ Since $\mathbb{C}$ has characteristic zero,
$H_{i}(X/\mathcal{H};\mathbb{C})$ equals the elements of $H_{i}(X;\mathbb{C})$
left fixed by the action of $\mathcal{H}$ on $H_{i}(X;\mathbb{C})$ [1, Theorem
2.4, pg. 120]. By the Hodge theorem, $H_{n-1}(X;\mathbb{C})$ is the kernel of
$\Delta_{n-1}(X).$ Proposition 11.6 tells us that this kernel is the direct
sum of all of the irreducible representations $\rho$ in the regular
representation of $\mathcal{G}$ with $\mbox{triv}\,\rho=\emptyset.$ By
definition, ${\mathcal{R}}(\mathcal{H})$ are those $\rho$ left fixed by the
$\mathcal{H}$-action. Hence the dimension of $H_{n-1}(X/\mathcal{H})$ equals
the L.H.S. of (13).

To see the last equality we consider the reduced Euler characteristic of
$X/\mathcal{H}.$ As the only nontrivial reduced homology group of
$X/\mathcal{H}$ is $\tilde{H}_{n-1}(X/\mathcal{H}),$ the reduced Euler
characteristic of $X/\mathcal{H}$ is $(-1)^{n-1}\dim
H_{n-1}(X/\mathcal{H};\mathbb{C}).$ On the other hand, we can compute the
reduced Euler characteristic by counting faces. Let $S\subseteq E.$ Define
$F_{S}$ to be the number of faces of $X/\mathcal{H}$ corresponding to cosets
of the form $\mathcal{G}_{S}/\mathcal{H}_{S}.$ Then

$|F_{S}|=\left|\frac{\mathcal{G}_{S}}{\mathcal{H}_{S}}\right|=\frac{|\Gamma|^{|S|}}{|\mathcal{H}_{S}|}=|\Gamma|^{|S|-r_{\mathcal{H}}(S)}=|\Gamma|^{r^{\ast}_{\mathcal{H}}(E)-r^{\ast}_{\mathcal{H}}(E-S)}.$

Thus the reduced Euler characteristic of $X/\mathcal{H}$ is

$\displaystyle\sum_{S\subseteq
E}(-1)^{|S|-1}|F_{S}|=\displaystyle\sum_{S\subseteq
E}(-1)^{|S|-1}|\Gamma|^{r^{\ast}_{\mathcal{H}}(E)-r^{\ast}_{\mathcal{H}}(E-S)}$
$=(-1)^{n-1}\displaystyle\sum_{S\subseteq
E}(-1)^{|E-S|}|\Gamma|^{r^{\ast}_{\mathcal{H}}(E)-r^{\ast}_{\mathcal{H}}(E-S)}=(-1)^{n-1}{\chi}_{r^{\ast}_{\mathcal{H}}}(|\Gamma|).$

$\square$

## References

  * [1] G. Bredon,  Introduction to compact transformation groups,  vol. 46, Pure and Applied Mathematics,  Academic Press, New York and London, 1972.
  * [2] O. Bernardi, T. Kálmán and A. Postnikov,  Universal Tutte polynomial,  Adv. in Math., 402 (2022), 108355.
  * [3] T. Brylawski and J. Oxley,  The Tutte polynomial and its applications,  in Matroid Applications, Encycl. Math. Appl. 40,  Cambridge Univ. Press, Cambridge, 1992, 123—225.
  * [4] K. Bauer, D. Sen and P. Zvengrowski,  A generalized Goursat lemma,  Tatra Mt. Math. Publ., 64 (2015), 1–19.
  * [5] F. Castillo, Y. Cid-Ruiz, B. Li, J. Montaño, and N. Zhang,  When are multidegrees postive?,  Adv. in Math., 374 (2020), 107382 (34 pp.).
  * [6] A. Chen,  Personal communication.
  * [7] L. Chávez-Lomelí, C. Merino, G. R. Sánchez and G. Whittle,  A new polynomial for polymatroids,  Australasian J. of Comb., 80(3) (2021), 342—360.
  * [8] H. Crapo and G-C. Rota,  On the foundations of combinatorial theory: Combinatorial geometries,  Preliminary edition, M.I.T. press, Cambridge Mass., 1970.
  * [9] S. Dougherty, J. Kim and P. Solé,  Open problems in coding theory  in, Noncommutative rings and their applications,  Contemp. Math. 634, 2015, 79–99.
  * [10] J. Doziuk and V. Patodi,  Riemannian structures and triangulations of manifolds,  J. Indian Math. Soc. (N.S.), 40: 1 —52, 1976.
  * [11] A. Duval and V. Reiner,  Shifted simplicial complexes are Laplacian integral,  Trans. Amer. Math. Soc., 354: 4313—4344, 2002.
  * [12] X. Dong and M. Wachs,  Combinatorial Laplacian of the matching complex,  Elect. J. Comb., 9: R17, 2002.
  * [13] J. Edmonds,  Submodular functions, matroids and certain polyhedra,  in Combinatorial structures and their applications. Proc. Calgary Inter. Conf 1969,  pp. 69—87.  Gordon and Breach, NY, 1970.
  * [14] C. Eur and M. Larson,  Intersection theory of polymatroids,  Int. Math. Res. Notices, https://doi.org/10.1093/imrn/rnad213.
  * [15] Eds. J. Ellis-Monaghan and I. Moffatt,  Handbook of a the Tutte polynomial and related topics,  CRC Press, Boca Raton, New York, London, 2022.
  * [16] J. Friedman and P. Hanlon,  On the Betti numbers of chessboard complexes,  J. of Alg. Comb., 8: 193–203, 1998.
  * [17] I. Gelfand, M. Goresky, R. MacPherson, and V. Serganova,  Combinatorial geometries, convex polyhedra, and Schubert cells,  Adv. in Math., 63 (1987), 301–316.
  * [18] J. Geelen, B. Gerards and G. Whittle,  Solving Rota’s Conjecture,  Notices of the AMS, 61 (7), 2014: 736—743.
  * [19] E. Goursat,  Sur les substitutions orthogonales et les divisions réguliéres de l’espace,  Ann. Sciu. École Norm. Sup., 6 (1889), 9 — 102.
  * [20] C. Greene,  Weight enumeration and the geometry of linear codes,  Stud. Appl. Math., 55 (1976): 119–126.
  * [21] T.Helgason,  Aspects of the theory of hypermatroids,  in Hypergraph seminar,  (eds. C. Berge and D. Chaudhuri)  LNM 411, Springer, Berlin-New York, 1974,  pp. 191—214.
  * [22] S. Jowett, S. Mo and G. Whittle,  Connectivity functions and polymatroids,  Adv. in Appl. Math., 81 (2016), 1—12.
  * [23] J. Kung, G.-C. Rota and M. Murty,  On the Rédei Zeta Function,  J. of Numb. Theory, 12, 1980, 421—436.
  * [24] W. Kook and V. Reiner and D. Stanton,  Combinatorial Laplacians of matroid complexes,  J. Amer. Math. Soc., 13 (1):129 — 148, 1999.
  * [25] J. Kung,  A source book in matroid theory,  Birkhauser, Boston, 1986.
  * [26] P. Mao,  Cyclic flats in spectrum of combinatorial Laplacian of binary spherical quotients,  Senior thesis, Cornell University, 2022.
  * [27] C. McDiarmid,  Rado’s theorem for polymatroids,  Math. Proc. Camb. Phil. Soc., 78 (1975), 263—281.
  * [28] F. J. MacWilliams,  A theorem on the distribution of weights in a systematic code,  Bell System Tech. J., 42 (1963), 79–94.
  * [29] T. Nakasawa,  Zur Axiomatik der linearen Abhängigkeit I,  Sci. Rep. Toyko Bunrika Daigaku, 2 (1935), 235–255.
  * [30] T. Nakasawa,  Zur Axiomatik der linearen Abhängigkeit II,  Sci. Rep. Toyko Bunrika Daigaku, 3 (1936), 123—136.
  * [31] T. Nakasawa,  Zur Axiomatik der linearen Abhängigkeit III,  Sci. Rep. Toyko Bunrika Daigaku, 3 (1936), 45—69.
  * [32] J. Oxley and G. Whittle,  A characterization of Tutte invariants of $2$-polymatroids,  J. of Comb. Theory, Series B,  59 (1993), 210–244.
  * [33] J. Oxley, C. Semple and G. Whittle,  A wheels and whirls theorem for $3$-connected $2$-polymatroids,  SIAM J. Disc. Math., 30 (1): 493–524, 2016.
  * [34] J. Oxley,  Matroid Theory, 2nd ed.,  Oxford Grad. Text. Math. 21,  Oxford Univ. Press, Oxford, 2011.
  * [35] A. Postnikov,  Permutohedra, Associahedra, and Beyond,  Int. Math. Res. Not., (2009), No. 6, 1026 — 1106.
  * [36] I. Rival and M. Stanford,  Algebraic aspects of partition lattices,  in Matroid Applications, 106—122,  Cambridge University Press, Cambridge, 1992.
  * [37] J. P. Serre,  Linear representations of finite groups,  Springer-Verlag, New York, 1977.
  * [38] R.P. Stanley,  $f$-vectors and $h$-vectors of simplicial posets,  J. of Pure and Applied Algebra, 71:319 - 331, 1991.
  * [39] E. Swartz,  Matroids and quotients of spheres,  Ph.D. thesis, U. Maryland, 1999.
  * [40] E. Swartz,  Matroids and quotients of spheres,  Math. Z., 241: 247 - 269, 2002.
  * [41] W. Tutte,  A homotopy theorem for matroids, II,  Trans. Amer. Math. Soc., 88 (1958), 161—174.
  * [42] P. Wentworth-Nice,  A duality for nonabelian group codes,  in preparation.
  * [43] P. Wentworth-Nice,  Representability of polymatroids over finite groups,  in preparation.
  * [44] H. Whitney,  Non-separable and planar graphs,  Trans. Amer. Math. Soc., 34 (1932), 339—362.
  * [45] H. Whitney,  On the abstract properties of linear dependence,  Amer. J. Math., 57 (3):509–533, 1936.
  * [46] G. Whittle,  A geometric theory of hypergraph coloring,  Aequationes Math., 43: 45—58, 1992.
  * [47] G. Whittle,  On matroids representable over $GF(3)$ and other fields,  Trans. Amer. Math. Soc., 349 (2): 579—603, 1997.
  * [48] G. Whittle,  Duality in polymatroids and set functions,  Comb., Prob. and Comp., 1 (1992), 275—280.
  * [49] A. Xue,  Combinatorial Laplacian on binary spherical quotients,  Senior thesis, Cornell University, 2021.
  * [50] T. Zaslavsky,  The Möbius function and the characteristic polynomial,  in N.L. White, editor, Combinatorial geometries, Cambridge Universtiy Press, 1987.