A Matroid-Friendly Basis for the Quasisymmetric
Functions
Kurt W. Luoto
Department of Mathematics, University of Washington,
Box 354350, Seattle, WA 98195, USA
kwluoto@math.washington.edu
October 26, 2018
Abstract
A new Z-basis for the space of quasisymmetric functions (QSym, for
short) is presented. It is shown to have nonnegative structure constants,
and several interesting properties relative to the quasisymmetric functions
associated to matroids by the Hopf algebra morphism F of Billera, Jia,
and Reiner [3]. In particular, for loopless matroids, this basis reflects the
grading by matroid rank, as well as by the size of the ground set. It is
shown that the morphism F distinguishes isomorphism classes of rank two
matroids, and that decomposability of the quasisymmetric function of a
rank two matroid mirrors the decomposability of its base polytope. An
affirmative answer to the Hilbert basis question raised in [3] is given.
1 Introduction
In this paper we construct a new Z-basis for the space of quasisymmetric
functions, QSym and study its properties. For instance, we show that it has
nonnegative structure constants, and that it behaves well with respect to the
quasisymmetric functions associated to matroids by the Hopf algebra morphism
Mat → QSym described by Billera, Jia, and Reiner [3]. We also answer in the
affirmative a question regarding rank two matroids posed in [3, Question 7.10],
and give an affirmative answer to [3, Question 7.12] in the case of rank two
matroids.
In [3], Billera, Jia, and Reiner describe an invariant for matroids in the form
of a quasisymmetric function. They show that the mapping F : Mat → QSym
is in fact a morphism of combinatorial Hopf algebras (given a suitable choice of
character on Mat; see [1]), where Mat is the Hopf algebra of matroids introduced
by Schmitt [15], and studied by Crapo and Schmitt [4], [5], [6], [7]. Billera,
Jia, and Reiner show that, while the mapping F is not surjective over integer
coefficients, it is surjective over rational coefficients.
http://arxiv.org/abs/0704.0836v2
Our new basis for QSym is “matroid-friendly” in that it reflects the rank of
loopless matroids as well as the size of the ground sets: for every 1 ≤ r ≤ n,
there is a set Nnr of
basis vectors such that for every loopless matroid
M of rank r on an n-element ground set, F (M) ∈ span Nnr ; moreover, QSym
decomposes as the direct sum of these subspaces. This provides us with a new
product grading of QSym, according to matroid rank r. (The usual grading of
QSym by degree corresponds to the size n of the matroid ground set.) Also,
as with the monomial and fundamental bases of QSym, for every matroid M ,
F (M) has nonnegative coefficients in our basis.
The paper has two main parts. The first part (Sections 2–4) presents the new
basis and relevant background material. In Section 2, we recount background
material from the literature regarding posets and quasisymmetric functions. In
Section 3, we present a definition for our new basis for QSym by means of a
construction, and highlight several of its important features. There we also
prove that it is a Z-basis for QSym. In Section 4, we build necessary machinery
regarding computing the quasisymmetric function associated to a labeled poset,
in the form of alternative decompositions, and apply these tools to prove that
the structure constants of the new basis are nonnegative.
The second part, (Sections 5–7) discusses matroids and their quasisymmetric
functions. In Section 5, we recall some of the concepts, terminology, and results
from the paper [3], and prove our claims regarding the quasisymmetric functions
of matroids vis-a-vis our new basis. In Section 6, we recall the context of [3,
Section 7] regarding the relationship between decompositions of the quasisym-
metric function associated to a matroid and decompositions of its matroid base
polytope, and recall the statement of [3, Question 7.10] regarding the functions
associated to rank two matroids. We develop a formula for the quasisymmetric
function of a loopless rank two matroid in terms of the new basis, and apply
it to show (1) that the morphism F : Mat → QSym distinguishes isomorphism
classes of rank two matroids, (2) that the two types of decompositions mirror
each other, i.e. an affirmative answer to [3, Question 7.12] for the case of rank
two matroids, and (3) to give an affirmative answer to [3, Question 7.10]. In
Section 7, we make additional observations regarding matroid functions and the
new basis. We also compare the new basis with the other QSym bases discussed
in Section 10 of [3], and sketch an alternate proof of the surjectivity of the map
Mat → QSym over rational coefficients.
2 Preliminaries
In this section we quote certain concepts, terminology, and facts from the litera-
ture, as well as establish certain conventions which will be used in the remainder
of the paper.
2.1 Compositions
A composition α is a finite sequence of positive integers, i.e. α ∈ Pm for some
m ∈ N. The number of parts of α, m, is the length of α, and denoted by ℓ(α).
The weight of α = (α1, . . . , αm) is |α| = α1+ · · ·+αm. Included in our definition
is the composition having no parts, which we denote by the (bold font) symbol
0. We have ℓ(0) = |0| = 0, the only composition with these properties.
Note, for small examples where individual parts are less than 10, we will
often write a composition as a sequence of digits, with no separating commas.
For example, we may write (1, 5, 6, 3, 2, 3) as 156323 when the context is clear.
We adopt a similar convention for the one-line notation of permutations in Sn
when n < 10.
There is a natural bijection between compositions of weight |α| = n and
susbets of [n− 1] (where [n] = {1, 2, 3, . . . , n}), given by
(α1, . . . , αm) ↔ {α1, α1 + α2, α1 + α2 + α3, . . . , α1 + · · ·+ αm−1}.
We say that β is a refinement of α, or that β refines α (denoted β 4 α)
if |α| = |β| and A ⊂ B, where A and B are the sets associated to α and β
respectively.
To any permutation π ∈ Sn there is an associated composition of weight n
which we denote C(π) and whose parts give the lengths of successive increasing
runs in the one-line notation of π. For example, for π = 934756218 ∈ S9, we have
C(π) = 13212. In this paper, we mildly generalize the notion of a permutation
to be any sequence of distinct positive integers. Given a set of positive integers
X , we let S(X) denote the set of all permuations of all the elements of X . The
run length operator C(π) extends to these general permutations in the obvious
way. If X and Y are two sets of positive integers of the same cardinality n,
then every bijection f : X → Y induces a mapping f : S(X) → S(Y ) given by
f(x1, . . . , xn) = (f(x1), . . . , f(xn)). If f is an increasing function, then we have
C(f(π)) = C(π) for every π ∈ S(X).
2.2 Well-known QSym bases
The algebra of quasisymmetric functions QSym (or QSym(x) when we want
to emphasize the variable set) forms a subring of the power series ring R[[x]]
where x = (x1, x2, x3, ...) is a linearly ordered set of variables indexed by the
positive integers, and R is a (fixed) commutative ring. In this paper we only
deal with the cases where R is either Z or Q, assuming coefficients in Q unless
otherwise stated. We often suppress the variables in our notation, writing simply
f ∈ QSym rather than f(x) ∈ QSym(x).
There are a number of well-known bases for QSym, all indexed by compo-
sitions. (For the two considered here, see [10].) The best-known is the basis
of monomial quasisymmetric functions, which here we denote {xα}. Given a
composition α with ℓ(α) = k, xα is defined by
xα :=
1≤i1<i2<···<ik
xα1i1 x
· · ·xαkik .
Another frequently used basis is the set {Lα} of fundamental quasisymmetric
functions, defined by
Lα :=
For example, L1 = x
1 is simply the degree one elementary symmetric function.
We note that QSym as an algebra under the usual multiplication is graded by
degree. For each of the bases described above, the set of basis elements indexed
by all the compositions of a fixed weight n forms a basis for the homogeneous
component of degree n, QSymn. Accordingly, dimQSymn = 2
2.3 Posets and P -partitions
One of the early references to quasisymmetric functions is the paper of Ges-
sel [10] (who built on the work of Stanley [17]), where they are related to P -
partitions of labeled posets. Most of this material can also be found in Stanley
[18]. In the following, we let ≤ denote the usual ordering on integers, and ≤P
denote the partial order of a poset P . All posets we consider here are finite.
We adopt a mild generalization of Gessel’s convention. We say that a labeled
poset on n elements is a partial order on a set of n positive integers. These
integers are referred to as the labels of the poset. Usually the set of labels is
[n] = {1, 2, . . . , n}, but sometimes we make use of other labels. We often use the
same symbol to refer to both the poset and its set of labels when the meaning
is clear from context.
Note. This convention differs from that used in [3]. There, a labeled poset
consists of a pair (P, γ), where P is a poset on an arbitrary set of n elements,
and γ is a labeling of P , that is a bijection between the elements of P and the
set [n]. The notion is equivalent to Gessel’s. For our generalization, the labeling
would be an injective function from the set of elements of the poset into the set
P of positive integers. At times we find it convenient to write (P, γ) when we
wish to discuss various labelings on the same underlying unlabeled poset.
The following is not the actual definition used in [10] and [17], but rather is
a formula developed by Stanley in [17]. We take it as our definition here.
Definition 2.1. Let P be a labeled poset. Let L(P ) denote the Jordan-Hölder
set of P, that is, the set of all permutations in S(P ) that are linear extensions
of P . Then the quasisymmetric function of P is
F (P ) :=
π∈L(P )
LC(π). (1)
Remark 2.1. The function F (P ) depends only on the relative partial order of
the labels at each covering relation of the poset and not on the absolute values
of the labels themselves. Given labeled posets P defined on the set of labels
A, and P ′ defined on the set of labels B, and a function f : A → B which is
an isomorphism of their underlying unlabeled posets, then F (P ) = F (P ′) if for
every covering relation (y covers x) in P we have x < y ⇐⇒ f(x) < f(y).
3 The new basis
The main goal of this section is to define our new basis (see Definition 3.1
below) and to prove that it is in fact a Z-basis of QSym, that is to say, every
quasisymmetric function that can be written in terms of either the standard
monomial or fundamental basis using only integer coefficients can also be written
in terms of the new basis using only integer coefficients. In Section 4.3, we prove
the positivity of the structure constants for this new basis and the grading of
QSym by composition rank.
Following the notation of [3], given unlabelled posets P and Q, we denote
by P ⊕Q their ordinal sum. The set of elements of P ⊕Q is the disjoint union
of the elements of P and Q. All of the order relations of P and Q are retained,
and in addition, x <P⊕Q y for all x ∈ P and y ∈ Q.
As with all the well-known bases for QSym, the elements of the new basis
are indexed by compositions. We denote the basis by {Nα}, where α ranges
over all compositions.
Definition 3.1. For a given composition α 6= 0, let Pα = A1 ⊕ · · · ⊕ Am be
the graded poset on |α| elements, where m = ℓ(α) and Ai is an antichain on αi
elements. Make Pα into a labeled poset by numbering the ranks in alternating
fashion: first number the odd-ranked elements A2, A4, . . ., followed by the even-
ranked elements A1, A3, . . .. We define N0 := 1, and for each α 6= 0, we define
Nα := F (Pα) (see Equation (1)).
Example 3.2. Let α = (1, 2, 2). Then
P122 = {3} ⊕ {1, 2} ⊕ {4, 5},
L(P122) = {(31245), (31254), (32145), (32154)}, and
N122 = L14 + L131 + L113 + L1121.
Definition 3.3. Given a composition α = (α1, . . . , αk), the rank of α, denoted
by r(α), is the sum of the odd-indexed parts of the composition. That is,
r(α) :=
odd i
αi = α1 + α3 + α5 + · · · . (2)
We define N 00 := {N0} = {1}, and for 1 ≤ r ≤ n,
Nnr := {Nα : |α| = n and r(α) = r}. (3)
We also define the subspace V nr := span N
r ⊂ QSymn. If we are working over a
field of coefficients for QSym, then V nr may be viewed as a vector space, whereas
if we are working over integer coefficients then we refer to the Z-span of Nnr and
V nr is a Z-module.
Theorem 3.4. The set of quasisymmetric functions {Nα}, as α ranges over
all compositions, forms a Z-basis for QSym.
Proof. We show that {Nα}|α|=n forms a basis for the homogeneous component
QSymn for each nonnegative integer n. This is trivial for n = 0. For the general
case, we prove the existence of a unitriangular transition matrix from {Nα}|α|=n
of QSymn to the fundamental basis {Lα}|α|=n.
Consider the following construction. Given a permutation ω ∈ Sn, let b(ω) ∈
1{0, 1}n−1 be the n-digit binary word where the digits are given by
1 if i = 1 or ω(i− 1) < ω(i),
0 otherwise.
Then define ρ(ω) to be the composition which gives the lengths of succes-
sive runs of 1’s and 0’s in b(ω). For example, if ω = 184356729 ∈ S9 then
b(ω) = 110011101, and ρ(ω) = 22311. Clearly one can determine the run-length
composition C(ω) from ρ(ω) and vice versa.
Given a composition α, let Pα be the labeled poset in Definition 3.1, and
L(Pα) its set of linear extensions. Recall that by definition
Nα :=
π∈L(Pα)
LC(π).
By the nature of the labeling on Pα, ρ(π) 4 α for all π ∈ L(Pα). Furthermore,
there is a unique element π ∈ L(Pα) such that ρ(π) = α, namely the one in
which all the labels of Ai are in ascending order if i is odd, and in descending
order if i is even. Thus if we order the rows of the transition matrix (labeled
by compositions α) and columns (labeled by compositions ρ(π)) in an arbitrary
way that extends the partial refinement order 4, then the resulting matrix is
unitriangular, and hence {Nα} is indeed a Z-basis for QSym.
4 Additional facts regarding F (P )
In this section we develop several additional facts regarding the quasisymmetric
function F (P ) for labeled posets P , including an alternative way to decompose
F (P ) for posets, the main idea being to partition L(P ). These facts, especially
Lemmas 4.1 through 4.4, are key tools for the results in following sections.
4.1 Ordered partitions
Consider a permutation π = (π1, . . . , πn) ∈ S(X), where |X | = n, and a compo-
sition τ = (τ1, . . . , τk) with |τ | = n. We can “chop up”, or segment the one-line
notation of π from left to right into k segments, where each respective segment
si is a subsequence of consecutive elements of the one-line notation of length τi.
We call the sequence of these segments s = (s1, . . . , sk) a segmentation of π of
type τ (or induced by τ). Letting t0 = 0 and tj =
i=1 τi be the j-th partial
sum of the parts of τ , every permutation π ∈ S(X) has a unique segmentation
sτ (π), whose segments, for 1 ≤ j ≤ k, are given by
sj = (πtj−1+1, πtj−1+2, . . . , πtj ).
An ordered partition K = (K1, . . . ,Kk) of a set X ⊂ P is a partitioning of X
into non-empty, pairwise disjoint subsets called blocks, i.e. X = ⊔ki=1Ki, where
the order of the blocks matters. Let τi = |Ki| for all i, and refer to the resulting
composition τ(K) = (τ1, . . . , τk) as the type of K.
Let K(X) denote the set of all ordered partitions of X . Every composition
τ of weight n induces a mapping Kτ : S(X) → K(X) as follows. For every
π ∈ S(X) there is a unique ordered partition Kτ (π), each of whose blocks Kj is
the set of elements in the corresponding segment sj of the segmentation sτ (π).
We abbreviate the inverse image K−1τ (K) as K
−1(K) since, for a given or-
dered partition K, the type τ , the set of elements X , and thus the permutation
group S(X), can all be determined from K. Thus for an ordered partition K,
we have
K−1(K) := {π ∈ S(X) : Kτ(K)(π) = K}. (4)
For example, K−1(({2, 7}, {5}, {1, 8})) = {27518, 27581, 72518, 72581}.
The following lemma is simply an exercise in notation, so we omit its proof.
Lemma 4.1. Let K be an ordered partition with k blocks. Let PK be the labeled
poset PK = K1 ⊕ · · · ⊕Kk, where each Ki is regarded as an antichain. Then
F (PK) =
π∈K−1(K)
LC(π).
We say that an ordered partitionK = (K1, . . . ,Kk) is alternating if for every
1 ≤ i < k and for all x ∈ Ki and y ∈ Ki+1 we have x < y if i is even and x > y
if i is odd.
Lemma 4.2. Let K be an alternating ordered partition of type τ . Then
F (PK) = Nτ .
Proof. Each rank Ki of PK = K1 ⊕ · · · ⊕Kk (where ℓ(τ) = k) is an antichain.
Hence F (PK) depends only on the relative ordering of the elements between
adjacent ranks Ki and Ki+1 (see Remark 2.1). Since K is alternating, we can
relabel its elements in each rank as we do in the construction of Pτ (as in
Definition 3.1) and still maintain the same relative ordering between elements
in adjacent ranks. Thus F (PK) = F (Pτ ) = Nτ .
4.2 Unordered partitions of X ⊂ P
Let T = {T1, . . . , Tm} be an unordered partition of the set X ⊂ P. We say that
an ordered partition K is a refinement of T if K, considered as an unordered
partition, is a refinement of T . For every permutation π ∈ S(X), T induces a
unique segmentation of π where each segment is contained in a block of T and
this segmentation is least (coarsest), with respect to refinement, among all such
segmentations. Corresponding to this segmentation there is a unique ordered
partition KT (π), which clearly is is a refinement of T . We say that T induces
the ordered partition KT (π) on π.
Example 4.3. Let X = [9], T = { {1, 4}, {2, 6, 8, 9}, {3, 5, 7} }, π = 965412378.
Then KT (π) = ({6, 9}, {5}, {1, 4}, {2}, {3, 7}, {8}).
Let P be a labeled poset, and T an unordered partition of P . Define KP,T
to be the set of induced ordered partitions KP,T := {KT (π) | π ∈ L(P )}. We
say that T is antichain-inducing if for every ordered partition K ∈ KP,T , every
block Ki of K is an antichain in P .
Lemma 4.4. Let T be an antichain-inducing unordered partition of a labeled
poset P . Then
F (P ) =
K∈KP,T
F (PK). (5)
We call this the decomposition of F (P ) with respect to T .
Proof. By Lemma 4.1 it suffices to show that
L(P ) =
K∈KP,T
K−1(K).
The “⊂”-direction is trivial. Indeed, T induces some ordered partition on every
permutation, and by definition KP,T includes all such partitions as permutations
range over L(P ). Also, clearly K−1(K) ∩ K−1(J) = ∅ if K 6= J since KT is a
well-defined map on L(P ), and so the union on the right is indeed a disjoint
union.
For the “⊃”-direction, let K ∈ KP,T . By definition of KP,T , there exists
π ∈ L(P ) ∩ K−1(K). Let s = sτ(K)(π). Since T is antichain-inducing, the
unordered set of elements Ki of each segment si is an antichain. It follows that
if we form a new permutation π̂ by permuting the elements of si arbitrarily
within si (and thus within π), we must also have that π̂ ∈ L(P ). Since this
holds true for each segment of s, we have K−1(K) ⊂ L(P ).
Remark. In the extreme case where T consists of all singleton sets, KT (π) is the
list of singleton sets in the order specified by π, and K−1(KT (π)) = {π}. We
can identify KT (π) with π itself, and similarly KP,T with L(P ), and the lemma
is then equivalent to the formula (1).
4.3 Structure constants for the new basis
Following the notation of [3] and [17], given labeled posets P and Q on sets
X and Y respectively, we denote by P + Q any disjoint sum of the posets,
constructed as follows. We first form the poset whose set of elements is the
disjoint union of the sets of elements of P and Q, retaining all partial order
relations of the two posets but adding no new relations. In order to ensure that
all labels are distinct, we then relabel the elements in any fashion subject to
the restriction that the resulting labels are all distinct and preserve the relative
order of labels at all covering relations (see Remark 2.1). While the disjoint sum
of the labeled posets is not uniquely defined, all disjoint sums so constructed
will have the same quasisymmetric function. It is well-known and is easy to
prove (see, for example, [10]) that
F (P +Q) = F (P ) · F (Q). (6)
We are now in a position to prove the nonnegativity of the structure constants
for our new basis.
Theorem 4.5. The quasisymmetric function algebra QSym is graded by the
rank of the compositions indexing the basis {Nα}. Furthermore, the structure
constants for {Nα} are nonnegative. That is, in the expansion
NαNβ =
cνα,βNν ,
all the constants cνα,β are nonnegative integers.
Proof. We first prove the statement regarding structure constants. Since N0 =
1, the claim holds trivially if α = 0 or β = 0. Thus we assume α = (α1, . . . , αs) 6=
0 and β = (β1, . . . , βt) 6= 0. By (6) we have that
NαNβ = F (Pα)F (Pβ) = F (Pα + Pβ). (7)
We write Pα = A1 ⊕ · · · ⊕As and Pβ = B1 ⊕ · · · ⊕Bt, and identify the Ai and
Bj subsets with their canonical inclusions in Pα + Pβ .
We form a new poset Q by relabeling the elements of the Ai and Bj subsets
while maintaining their ordering relations: first label the even-indexed Ai and
Bj in order, with the numbers from [m], where m = |α|+ |β| − r(α)− r(β) and
r(α) is the rank function from Definition 3.3, then label the odd-indexed Ai and
Bj in order, with the numbers from {m + 1, . . . , |α| + |β|}. Since F (Pα + Pβ)
depends only on the relative ordering of elements between adjacent ranks Ai
and Ai+1 for 1 ≤ i < s and between adjacent ranks Bj and Bj+1 for 1 ≤ j < t,
we have
F (Pα + Pβ) = F (Q). (8)
We consider the unordered partition T = {T1, T2} of Q given by
odd i
odd i
, and T2 =
even i
even i
Note that T is antichain-inducing, so we may apply Lemma 4.4:
F (Q) =
K∈KQ,T
F (PK). (9)
On the other hand, the labeling of Q implies that every ordered partition K ∈
KQ,T is alternating, so applying Lemma 4.2, we have
F (Q) =
K∈KQ,T
Nτ(K). (10)
Combining Equations (7) – (10) yields the positivity claim. In particular,
cνα,β = |{K ∈ KQ,T : τ(K) = ν}|.
To prove the statement regarding the grading of QSym by composition rank,
we simply note that for every K ∈ KQ,T , we have
r(τ(K)) = |T1| = r(α) + r(β).
5 Matroids
This section begins the second part of the paper. Here we review some of
the concepts, terminology, and results from [3], and prove our claims regarding
the quasisymmetric functions of matroids vis-a-vis our new basis. For general
background in matroid theory we refer the reader to standard texts such as
Oxley’s [14]. We review several of the terms here.
The direct sum of matroids M1 and M2, denoted M1⊕M2, has as its ground
set the disjoint union E(M1 ⊕M2) = E(M1) ⊔ E(M2), and as its bases
B(M1 ⊕M2) = {B1 ⊔B2 : B1 ∈ B(M1), B2 ∈ B(M2)}.
A circuit is a minimal dependent set. If we declare two elements of a matroid
to be equivalent if and only if they are both contained in some circuit, then
the equivalence classes of elements are the components of the matroid. We say
that the matroid is connected if it has only one component, and disconnected
otherwise. A matroid is the direct sum of its components.
5.1 The quasisymmetric function of a matroid
Billera, Jia, and Reiner [3] describe an invariant for isomorphism classes of
matroids in the form of a quasisymmetric function. Rather than give the defi-
nition from [3], we describe it in terms of a formula which is shown in [3] to be
equivalent to the definition.
Fix a matroid M , one of its bases B ∈ B(M), and let Bc = E(M)−B (the
cobase of B). Define the poset PB on the ground set E(M) where e <PB e
and only if e ∈ B, e′ ∈ Bc, and (B − e)∪ {e′} ∈ B(M). That is, e <PB e
′ if and
only if swapping e′ for e in B yields another base in M . Thus the Hasse diagram
of PB is a bipartite graph in which the elements of B are minimal elements of
the poset and the elements of Bc are maximal elements. Note that if M has no
loops, then in the Hasse diagram of PB , every element in B
c has positive vertex
degree. We say that a labeled poset is strictly labeled if for all x, y ∈ P we have
that x <P y implies x > y. Similarly, a labeled poset is naturally labeled if for
all x, y ∈ P , x <P y implies x < y. We apply a strict labeling to PB (any will
do). The quasisymmetric function F (M) associated with M can be written as
F (M) =
B∈B(M)
F (PB), (11)
where F (PB) is the quasisymmetric function of the strictly labeled poset PB as
defined in Definition 2.1.
It was shown in [3] that the mapping F : Mat → QSym is in fact a morphism
of combinatorial Hopf algebras, with a suitable choice of character on the algebra
Mat. Here Mat is the Hopf algebra of matroids introduced by Schmitt [15] and
studied by Crapo and Schmitt [4], [5], [6], [7]. The matroid algebra Mat has as
its basis elements isomorphism classes of matroids. The product of two basis
elements [M1] and [M2] in the algebra is given by [M1] · [M2] := [M1 ⊕ M2],
where M1 ⊕M2 denotes the direct sum of matroids. Comultiplication in Mat is
given by ∆([M ]) :=
A⊂E(M)[M |A]⊗ [M \A], where M |A is the restriction of
M to A, and M \ A is the contraction of M by A. Under the morphism F we
have that
F (M1 ⊕M2) = F (M1) · F (M2).
Billera, Jia, and Reiner also show that the mapping F , while not surjective over
integer coefficients, is surjective over rational coefficients.
The mapping F : Mat → QSym does not distinguish between loops and
coloops. Indeed, let M ′ extend the matroid M by adding a loop ℓ, i.e. M ′ =
M ⊕ {ℓ}, and let M ′′ extend the matroid M by adding a coloop c, i.e. M ′′ =
M ⊕ {c}. Then
F (M ′) = F (M ′′) = F (M) · L1. (12)
Here L1 is the fundamental basis function indexed by the composition (1), which
is the elementary symmetric function e1(x). Define an equivalence relation ∼
on isomorphism classes of matroids by [M1] ∼ [M2] if and only if one can obtain
M1 from M2 by changing some number of loops to coloops or vice versa. Then
by Equation (12) the mapping Mat → QSym factors through the quotient
Mat → Mat/∼ → QSym.
Accordingly, throughout most of our paper, we assume that, unless otherwise
specified, our matroids have no loops; that is, out of each equivalence class in
Mat/∼ we select the representative that has no loops when considering their
images in QSym.
5.2 Expanding F (M) in the {N
} basis
Recall from Definition 3.3 that Nnr = {Nα : |α| = n, r(α) = r} and V
spanNnr . In this subsection we may take our coefficient ring to be Z if we wish.
Lemma 5.1. Let P be a strictly labeled poset on n elements of rank at most
one and with r minimal elements. Then F (P ) ∈ V nr . Moreover the expan-
sion of F (P ) in terms of the basis elements Nnr has only nonnegative integer
coefficients.
Proof. If P has rank 0, then P is an antichain and so r = n. Thus by labelling
P with the elements of [n] and taking α = (n), we have
F (P ) = F (Pα) = Nα = N(n) ∈ V
Otherwise P has rank 1 and is not an antichain. Let T = {T1, T2} be the
unordered partition of P in which T1 comprises the r minimal elements of P ,
and T2 the remaining elements. Note that some elements may be both minimal
and maximal, and these will be placed in T1. Thus every element in T2 in
the Hasse diagram of P has positive vertex degree. Since we are interested in
computing F (P ), we may assume without loss of generality that P has a strict
labeling which labels the elements of T1 = {n, n− 1, . . . , n− r+ 1} in arbitrary
fashion, and the elements of T2 = {1, 2, . . . , n − r} in arbitrary fashion. Since
T1 and T2 are themselves antichains, T is antichain-inducing, so by Lemma 4.4:
F (P ) =
K∈KP,T
F (PK).
Moreover, by the choice of labeling and the fact that every element in T2 has
positive vertex degree, we have that every K ∈ KP,T is alternating. Lemma 4.2
then implies
F (P ) =
K∈KP,T
Nτ(K).
We also have that |τ(K)| = n and r(τ(K)) =
odd i τi = |T1| = r, thus Nτ(K) ∈
V nr for every K ∈ KP,T . Hence F (P ) ∈ V
r as claimed.
Theorem 5.2. Let M be a loopless matroid of rank r on n elements. Then
F (M) ∈ V nr . Moreover the expansion of F (M) in terms of the basis elements
Nnr has only nonnegative integer coefficients.
Proof. For a loopless matroid M , for every base B ∈ B(M), the base poset PB
has r minimal elements out of a total of n elements, and rank at most one. The
assertion then follows by Lemma 5.1, and the formula in Equation (11).
We make a few observations here about the coefficients in the expansion of
the quasisymmetric function F (M) of a matroid M in terms of our new basis.
Given a quasisymmetric function q, define
supp(q) =
α : mα 6= 0 in the expansion q =
We first note that for a (loopless) matroid M of rank r on n elements, the
coefficient m(r,n−r) of Nα, where α = (r, n− r), is equal to the number of bases
of M .
Example 5.3. Let M = Ur,n be the uniform matroid of rank r on n elements.
By definition, its bases are all the r-subsets of the ground set E(M), i.e. B(M) =(
. Then every PB has a complete bipartite Kr,n−r graph for its Hasse
diagram. Therefore F (Ur,n) =
Nr,n−r, and supp(F (M)) = {(r, n− r)}.
Thus the values of m(r,n−r) (how small) and |supp(F (M))| (how large) are,
to some extent, measures of the degree to which M fails to be uniform.
The coefficient mα where α = (r− 1, 1, 1, n− r− 1) also has a combinatorial
interpretation. There is such an Nα term for every edge “missing” from the
Hasse diagram of a base poset PB as compared to the complete bipartite graph
Kr,n−r. In terms of matroid base polytopes, which are discussed in 6.1, the
polytope Q(Ur,n−r) contains all possible vertices, namely
, while the base
polytope for a different matroid M of same rank and ground set size has only a
subset of them, namely B(M). The coefficient mα is the number of edges in the
1-skeleton of Q(Ur,n−r) between the set of vertices B(M) and its complement(
− B(M).
Lemma 5.4. Let M be a matroid, possibly containing loops. Then the total
number c of loops and coloops is given by
c = max
α∈supp(F (M)),
ℓ(α) odd
α̇, (13)
where α̇ denotes the last part of the composition α.
Proof. Since the morphism F : Mat → QSym factors through loop-coloop equiv-
alence, F (M) = F (M ′) where M ′ is obtained from M by replacing all loops of
M with coloops. Since M and M ′ both have the same total number of loops
and coloops, without loss of generality, we assume that M has no loops.
Consider a typical strictly labeled base poset PB of M, and antichain inducing
partition {B,Bc} as in the proof of Lemma 5.1. We have α ∈ supp(F (M)) if
and only if there is an induced ordered partition K of PB of type α. Now ℓ(α)
is odd if and only if the last block of K is a subset of B, and in this case the
elements in this block must be coloops. Thus c ≥ α̇. Conversely, there always
exists an induced ordered partition of the poset, say of type α, which has all of
the coloops of M in the last block, i.e. c = α̇, and this ordered partition will
have odd length. The result follows.
6 Matroid base polytopes
In this section we recall the context of [3, Section 7] regarding the relationship
between decompositions of the quasisymmetric function associated to a matroid
and decompositions of its matroid base polytope. In Subsection 6.2 we develop a
formula for the quasisymmetric function of a loopless rank two matroid in terms
of the new basis, and apply it to address [3, Question 7.12] and [3, Question
7.10].
6.1 Matroid base polytopes and their decompositions
The motivating context is to study the decompositions of the matroid base
polytope Q(M) of a matroid M . This topic arises in the work of Lafforgue [12],
[13], Kapranov [11, §1.2 – 1.4], and can be found in the work of Speyer [16].
If M is a matroid with |E(M)| = n, we define the matroid base polytope
Q(M) by identifying E(M) with the set of standard basis vectors {ei}
i=1 of R
and declaring
Q(M) := conv
ei : B ∈ B(M)
where B(M) is the set of bases of M . Useful facts about matroid base polytopes
(see [9]), which we quote without proof, are:
1. If M has rank r, then Q(M) lies in the hyperplane {x ∈ Rn :
i xi = r}.
2. There is an edge in Q(M) between vertices (bases) B1 and B2 if and
only if there exist a pair of elements ei ∈ B1 and ej ∈ B2 such that
B2 = (B1 − {ei}) ∪ {ej}.
3. Each face of a matroid base polytope is in turn the base polytope of some
matroid.
4. The dimension of Q(M) is |E(M)| − s(M), where s(M) is the number of
connected components of M .
Billera, Jia, and Reiner define a matroid base polytope decomposition of Q(M)
to be a decomposition
Q(M) =
Q(Mi), (14)
where each Q(Mi) is also a matroid base polytope for some matroid, and for
each i 6= j, the intersection Q(Mi) ∩ Q(Mj) = Q(Mi ∩ Mj) is a face of both
Q(Mi) and Q(Mj). They call such a decomposition a split if t = 2.
Billera, Jia, and Reiner show that the mapping F : Mat → QSym behaves as
a valuation on matroid base polytopes. (See [2] for a discussion of valuations.)
This implies that, given a matroid base polytope decomposition as in Equation
(14), F (M) can be expressed in terms of the set of F (Mj) in an inclusion-
exclusion fashion, where the Mj are the matroids of the faces of the constituent
polytopes in the decomposition. For example, given a split Q(M) = Q(M1) ∪
Q(M2), we have F (M) = F (M1) + F (M2) − F (M1 ∩M2), where Q(M1 ∩M2)
is necessarily a lower-dimensional face. Hence by Fact 4 above, the matroid
M1 ∩M2 is disconnected, and so F (M1 ∩M2) can be expressed as a product.
If we let m :=
d≥1 QSymd be the maximal ideal in the ring QSym, then
F (M1∩M2) ∈ m
2. Therefore in the quotient space QSym/m2, we have F (M) =
F (M1) + F (M2). In general, given a matroid base polytope decomposition as
in Equation (14), there is an algebraic decomposition modulo m2
F (M) =
F (Mi). (15)
One of the open questions raised by Billera, Jia, and Reiner [3] is under what
conditions the converse may hold; given a collection of matroids satisfying (15),
what additional conditions are sufficient to conclude (14)?
Note. So far we have ignored the distinction between the isomorphism class of a
matroid on the one hand and a specific instance of that class on a given ground
set on the other, since the quasisymmetric function of a matroid is invariant
on the elements of the same isomorphism class. When discussing the existence
of matroid base polytope decompositions, it is sometimes necessary to draw a
distinction between the notions, as is done in the statement of Theorem 6.2
below. When this precision is necessary, we use the usual bracket notation [M ]
to denote the isomorphism class of the matroid M .
Given a ground set size n, the converse question is trivial for rank 0 and 1,
and by matroid duality, for rank n and n − 1. One necessary condition they
point out is that a specific set of matroids on a common ground set satisfying
(14) must at least satisfy the condition B(Mi) ⊂ B(M) for all i, in which case
they say that (15) is a weak image decomposition and that F (M) is weak image
decomposable. They specifically ask,
[3, Question 7.12] Does F (M) being weak image decomposable in
QSym/m2 imply that Q(M) is decomposable?
So far, general sufficient conditions are not known beyond the trivial ranks listed
above. We claim that the converse ((15) ⇒ (14)) holds quite generally for rank
two matroids, as shown in Section 6.2. By matroid duality, the converse also
holds for matroids of corank two.
As discussed in [3], the loopless rank two matroids are indexed, up to iso-
morphism, by partitions having two or more parts, where there are as many
parts as there are parellelism classes of elements in the matroid and the parts of
the partition give the respective cardinalities of these classes. For this section
we write Mλ to denote the loopless rank two matroid indexed by the partition
λ. More generally, given a composition α, define Mα = Mλ where λ is the
decreasing rearrangement of the parts of α.
Kapranov [11, §1.3] gives a description of all decompositions of rank two
matroid base polytopes. He shows [11, Lemma 1.3.14] that in rank two, all
matroid base polytope decompositions arise from hyperplane splits. We provide
some description here of the geometric situation, in our own words. Given the
composition λ = (λ1, . . . , λm), with |λ| = n, set t0 = 0 and for 0 ≤ k ≤ m set
i=1 λi be the k-th partial sum. Then the vertices of Q(Mλ) are precisely
those 0/1-lattice points v lying in the hyperplane H = {x ∈ Rn :
i xi = 2}
subject to the restriction that
tk+1∑
i=tk+1
vi ≤ 1
for all 0 ≤ k < m. If ℓ(λ) = 2, then
Mλ = M(λ1,λ2) = U1,λ1 ⊕ U1,λ2 ,
where U1,n is the uniform matroid of rank 1 on n elements. It follows that if
ℓ(λ) = 2, then dimQ(Mλ) = n− 2 and F (Mλ) ∈ m
Supposing that ℓ(λ) = m > 3, choose index j such that 1 < j < m− 1. Let
a = tj and b = n− tj , and define compositions µ = (a, b), α = (a, λj+1, . . . , λm),
and β = (λ1, . . . , λj , b), all of which have weight n. Consider the hyperplane
H ′ = {x ∈ Rn :
i=1 xi = 1}. Then H
′ ∩ Q(Mλ) = Q(Mµ), giving us a
hyperplane split Q(Mλ) = Q(Mα) ∪ Q(Mβ). It follows from the above that
F (Mλ) = F (Mα) + F (Mβ) − F (Mµ), and F (Mλ) = F (Mα) + F (Mβ). We
can summarize this in the following proposition. The relations given in the
proposition remain true even if λ has only two or three parts, but in that case
the resulting relations are trivial.
Proposition 6.1. Let λ = (λ1, . . . , λt) be a composition with at least two parts.
Let 1 ≤ s < t, a =
i=1 λi, and b =
i=s+1 λi. Consider compositions
α = (a, λs+1, . . . , λt), β = (λ1, . . . , λs, b), and µ = (a, b). We then have
F (Mλ) = F (Mα) + F (Mβ)− F (Mµ),
and modulo m2,
F (Mλ) = F (Mα) + F (Mβ).
Moreover there is a split of matroid base polytopes
Q(Mλ) = Q(Mα) ∪Q(Mβ).
The splitting process can be repeated on the constituent matroid base polytopes
until we have decomposed Q(Mλ) into the union of matroid base polytopes of
type Q(Mα) where ℓ(α) = 3. Consequently, modulo m
2, F (Mλ) can be written
as a positive sum
F (Mλ) =
F (Mi),
where each Mi is a loopless rank 2 matroid indexed by a partition of length 3.
In this setting, Billera, Jia, and Reiner , pose the following question:
[3, Question 7.10] Fix n and consider the semigroup generated by
F (M) within QSymn/m
2 as one ranges over all matroids M of rank
2 on n elements. Is the Hilbert basis for this semigroup indexed by
those M for which λ(M) has exactly 3 parts?
By repeated application of Proposition 6.1, the set {F (Mλ) : ℓ(λ) = 3}
generates the semigroup in question, so the point of the question is whether this
generating set is minimal, and whether distinct indices yield distinct functions.
We prove that this is the case as a corollary of Theorem 6.2.
6.2 Results for rank two matroids
In this section, we prove that the morphism F : Mat → QSym distinguishes
isomorphism classes of rank two matroids and that decomposability of F (M)
for a rank two matroid M implies decomposability of Q(M), as stated in the
following theorem.
Theorem 6.2. Let λ ⊢ n with ℓ(λ) ≥ 3, and let J be a multiset of partitions of
n, all of length three or more, such that
F ([Mλ]) =
F ([Mµ]), (16)
where [Mτ ] denotes the isomorphism class of (loopless) rank two matroids on n
elements indexed by the partition τ . Then, taking the set of standard basis vec-
tors of Rn as the common ground set, there exists a collection of representative
matroids on this ground set, Mλ ∈ [Mλ] and Mµ ∈ [Mµ] for all µ ∈ J which
form a decomposition of matroid base polytopes
Q(Mλ) =
Q(Mµ). (17)
Before the main proof of this theorem, we establish some preliminary results.
We begin by developing a formula for F (Mλ) in terms of the new basis {Nα}.
We define the following quasisymmetric functions in
V n2 = span{Nα : |α| = n, r(α) = 2}.
For all 1 ≤ k ≤ n− 1 let
T nk :=
N(2,n−2) +
k − 1
N(1,j,1,n−2−j), (18)
where we understand N(1,j,1,n−2−j) to be N(1,n−2,1) when j = n − 2. We also
define quasisymmetric functions
Unk := k(n− k)T
Note that each of the sets {T nk } and {U
k } forms a basis for the subspace V
where we consider QSym to have rational coefficients.
Lemma 6.3. Let Mλ be the rank two matroid on n elements indexed by the
partition λ = (λ1, . . . , λm). Then
F (Mλ) =
Unλi . (19)
Proof. We write c(λi) to denote the parallelism class of elements in Mλ cor-
responding to the part λi. A typical base B ∈ B(Mλ) is B = {ei, ej}, where
ei ∈ c(λi) and ej ∈ c(λj) are in distinct parallelism classes. The Hasse diagram
of PB has two minimal elements, ei and ej. There are edges from ei to all
elements of the cobase Bc = E(Mλ) − B except for the λj − 1 elements which
are in the same parallelism class c(λj) as ej. Similarly, there are edges from ej
to all elements of the cobase except for the λi − 1 elements which are in the
same parallelism class c(λi) as ei.
We can analyze F (PB) as in the proof of Lemma 5.1 by applying a strict
labeling γ : E(Mλ) → [n] such that γ(ei) = n, γ(ej) = n − 1, and the cobase
elements are arbitrarily labeled with {1, 2, . . . , n − 2}. We take T = {B,Bc}
to be our antichain-inducing partition of (PB , γ). There is one induced ordered
partition (of [n]) of type (2, n − 2), namely K = (B,Bc), classifying one set
of permutations in L(PB , γ), and thus contributing one N(2,n−2) term to the
expansion of F (PB). For each 1 ≤ k < λj , and for each k-set A ⊂ B
c(λj), there is an induced ordered partition K = ({ej}, A, {ei}, B
c −A) of type
(1, k, 1, n − 2 − k) contributing a term N(1,k,1,n−2−k) to the expansion. Thus
there are
such terms N(1,k,1,n−2−k) corresponding to ordered partitions
K of type (1, k, 1, n−2−k) withK1 = {ej}. Likewise there are
such terms
N(1,k,1,n−2−k) corresponding to ordered partitions K of type (1, k, 1, n− 2− k)
with K1 = {ei}. All the Nα ∈ N
2 are of one of these types, and we know that
the terms of F (PB) must lie in V
2 , so these are the only types appearing in the
expansion for F (PB). There can be no other terms than these due to the order
relations in PB. Thus
F (PB) = N(2,n−2) +
λi − 1
λj − 1
N(1,k,1,n−2−k). (20)
Using Equation (18), we can rewrite this as
F (PB) = T
+ T nλj .
Finally, there are λiλj such bases B ∈ c(λi)× c(λj). Summing over all pairs of
parallelism classes of the matroid yields the formula
F (Mλ) =
λi(n− λi)T
Unλi .
Next we develop a similar formula for F (Mλ) in QSymn/m
2. Our starting
point is the following corollary.
Corollary 6.4. Let a and b be positive integers such that a+ b = n. Then
ab ·N(1,a−1) ·N(1,b−1) = U
a + U
Proof. Let λ = (a, b). ThenMλ = U1,a⊕U1,b, where U1,m is the uniform matroid
of rank one onm elements. As discussed in Example 5.3, F (U1,m) = mN(1,m−1).
Therefore by the Hopf algebra morphism, we have
F (Mλ) = F (U1,a) · F (U1,b) = aN(1,a−1) · bN(1,b−1).
On the other hand, by Lemma 6.3 we have F (Mλ) = U
a + U
b . Equating right
hand sides yields the desired formula.
Since QSym with respect to its product structure is graded by composition
rank as well as degree, the vector subspace V n2 ∩m
2 is spanned by the vectors
{N(1,a−1) ·N(1,b−1) : a+ b = n}.
Thus a basis for V n2 ∩ m
2 is {Unk + U
n−k : 1 ≤ k ≤
}. For expressing our
formula for F (Mλ), we find it convenient to define vectors U
k as follows:
Unk =
Unk if k <
0 if k = n
−Unn−k if k >
Thus the set {Unk : 1 ≤ k <
} forms a basis (over rational coefficients) for
V n2 /m
2. We have the immediate corollary of Lemma 6.3:
Corollary 6.5. Let Mλ be the rank two matroid on n elements indexed by the
partition λ = (λ1, . . . , λm). Then
F (Mλ) =
Unλi . (22)
The next proposition provides a necessary step for the main result, but may be
of interest in its own right.
Proposition 6.6. Let M2 be the set of matroid isomorphism classes (including
those with loops) of rank two matroids. Let Matc be the vector subspace of Mat
spanned by the isomorphism classes of connected matroids, and let M2c be the
set of matroid isomorphism classes of connected rank two matroids. Then the
algebra morphism F : Mat → QSym is injective when restricted to M2, and the
induced quotient map of vector spaces F : Matc → QSym/m
2 is injective when
restricted to M2c.
Proof. We show that we can recover the isomorphism class of the matroid from
its respective function. Suppose we are given F (M) for a rank two matroid M .
We know that F (M) is a non-zero homogeneous function of degree n = |E(M)|,
and so we recover the size of the ground set. Clearly, n ≥ 2.
It is possible that M may have loops or coloops. By Lemma 5.4 we can
recover the total number s of loops and coloops of M from F (M) by Equation
(13). If s = n, then M consists of two coloops and n − 2 loops. Otherwise
s ≤ n− 2, and we may factor F (M) as
F (M) = N(s) · F (M
where (s) is the one-part composition of s, and M ′ is the matroid obtained
from M by removing all loops and coloops. If now F (M ′) ∈ V n−s1 , we have
M ′ ∼= U1,n−s and M has one coloop and s− 1 loops. Otherwise M has s loops,
no coloops, F (M ′) ∈ V n−s2 , and M
′ is a loopless rank two matroid on n − s
elements.
So now without loss of generality, we assume that M has no loops or coloops
and thus is isomorphic to Mλ for some λ ⊢ n. We expand F (M) as
F (M) =
k . (23)
This expansion can be determined since the set of {Unk } form a basis of V
2 . Per
Lemma 6.3, for each k, the coefficient tk is the number of parts of λ that are
equal to k, and so we recover λ from F (Mλ).
The argument for recoveringM from F (M) for a connected rank two matroid
M is similar. Since M is connected, it has no loops or coloops, and so again
M is isomorphic to Mλ for some λ ⊢ n with ℓ(λ) ≥ 3, where n is the degree of
F (M). We expand
F (M) =
⌊(n−1)/2⌋∑
k . (24)
This expansion can be determined since the set {Unk : 1 ≤ k <
} forms a basis
for the subspace V n2 /m
2. Note that λ cannot have a pair of parts with values
k and n − k. Using this fact together with Corollary 6.5, we see that if the
coefficient tk is nonnegative, then λ has exactly tk parts with value k. From
this we can determine all the parts of λ which are < n
. Since λ cannot have
more than one part ≥ n
, this allows us to determine the remaining part of λ, if
Proof of Theorem 6.2. We write A⊔B to denote the disjoint union of multisets
A and B. Note that a partition may be considered to be a multiset of integers.
We fix n > 2 and λ ⊢ n with ℓ(λ) ≥ 3, and proceed by induction on |J |. The
base case |J | = 1 follows from Proposition 6.6. So we assume that the statement
holds for |J | < m for some fixed m > 1. Suppose now that
F ([Mλ]) =
F ([Mµ]), (25)
where |J | = m. Say that a pair of elements µ, ν ∈ J are matching if for some
value 1 < k < n − 1 we have k ∈ µ and n − k ∈ ν. If µ, ν are a matching
pair, then we can apply Proposition 6.1 to form a new relation of type (25) by
replacing J with J ′ = (J − {µ, ν}) ⊔ {τ}, where τ = (µ ⊔ ν) − {k, n − k}. At
the same time, Proposition 6.1 tells us that we also have a decomposition of
base polytopes Q(Mτ ) = Q(Mµ) ∪ Q(Mν). Since |J
′| < m, we can apply our
induction hypothesis, and we are done. It remains to show that there exists a
matching pair in J .
For a partition τ ⊢ n, define the multiset g(τ) = {τi : τi > 1, τi 6=
Define multisets L = g(λ) and R =
µ∈J g(µ). Per Corollary 6.5 we expand
F (Mλ) =
ℓ(λ)∑
Unλi ,
and we similarly expand each F (Mµ) on the right hand side of (25). Since the
set {Unk : 1 ≤ k <
} forms a basis for V n2 /m
2, with Unk = −U
n−k, we conclude
that L ⊆ R and that the parts in R − L can be matched into complementary
pairs of the form (k, n− k). Since no partition in J can contain both parts of a
complementary pair, there exists a matching pair in J if R− L 6= ∅.
We are assuming that |J | ≥ 2, and that R and L contain all the parts not
equal to n
or 1 on the respective sides of (25). The parts equal to 1 on both sides
must match since all of the partitions have at least three parts and hence no
part equal to (n− 1). The only way to have R−L = ∅ is if there exist µ, ν ∈ J
each of which contains a part equal to n
, in which case they are matching.
Thus in all cases, there exists a matching pair µ, ν ∈ J , and the result follows
by induction.
Now we can give an affirmative answer to [3, Question 7.10].
Corollary 6.7. For a fixed n, the Hilbert basis for the semigroup in QSym/m2
generated by the set S = {F (Mλ) : λ ⊢ n, ℓ(λ) ≥ 3} is indexed by those Mλ for
which ℓ(λ) = 3.
Proof. Let T = {F (Mλ) : λ ⊢ n, ℓ(λ) = 3}. It follows from Proposition 6.1
that for ℓ(λ) > 3, F (Mλ) is decomposable into a sum
µ F (Mµ), where for all
µ, ℓ(µ) < ℓ(λ). Hence T generates the same semigroup as S. As noted in [3,
Section 7], if ℓ(λ) = 3, then Q(Mλ) is indecomposable. Theorem 6.2 then implies
that F (Mλ) must also be indecomposable, so T is the minimal generating set,
i.e. the Hilbert basis of the semigroup. By Proposition 6.6, distinct indexing
partitions yield distinct images, establishing the claim.
7 Additional observations
In this section we discuss additional aspects of our new basis, especially regard-
ing the expansion of F (M) for a matroid M .
7.1 Matroid duality, loops, and coloops
Although we describe the basis {Nα} as ‘matroid-friendly’, things are slightly
less friendly when considering matroid duality in the presence of coloops. This
is due to the fact, mentioned in Section 5.1, that the mapping F : Mat → QSym
factors through the quotient Mat → Mat/∼ → QSym, where ∼ denotes loop-
coloop equivalence.
For example, a fact proved in [3] is that, for any matroid M , in terms of the
monomial basis for QSym the following relationship holds:
F (M) =
α =⇒ F (M∗) =
α∗ . (26)
where α∗ is the reversal of α, obtained by writing the parts of α in reverse order.
If M be is a matroid of rank r on n elements having no loops or coloops, then
we have the analogous relationship
F (M) =
mαNα =⇒ F (M
mαNα∗ . (27)
However this relationship breaks down if M has loops or coloops.
We showed in Theorem 5.2 that if M is a loopless matroid of rank r on n
elements, then F (M) ∈ V nr . More generally, if M is of rank r on n elements
and has exactly ℓ loops, then F (M) ∈ V nr+ℓ. Thus if M has exactly c coloops,
then we have the duality relationship
F (M) ∈ V nr =⇒ F (M
∗) ∈ V nn−r+c.
7.2 Comultiplication
The matroid Hopf algebra is graded by matroid rank as well as ground set size.
Let Wnr be the subspace of Mat spanned by the classes of matroids of rank r
on n elements. Then Wnr ·W
s ⊂ W
r+s . For any matroid M and A ⊆ E(M),
r(M) = r(M |A) + r(M/A). So comultiplication in Mat also respects these
gradings. (For general background on Hopf algebras, see [8].) That is,
∆Wnr ⊆
a+b=n,
s+t=r
W as ⊗W
. (28)
One might wonder whether the standard comultiplication of the Hopf algebra
QSym respects the grading by the rank function for our new basis, that is,
whether
∆V nr ⊆
a+b=n,
s+t=r
V as ⊗ V
. (29)
This is not the case. For the simplest example, consider n = 2 and r = 1. We
have N 00 = {N0} = {1} and N
1 = {N11} = {x
11}. Note that there is no Nm0
(or rather, Nm0 = ∅) for m > 0. The basis vectors corresponding to the right
hand side of (29) are
N11 ⊗N0 = x
11 ⊗ 1, and N0 ⊗N11 = 1⊗ x
However,
∆N11 = ∆x
11 = x11 ⊗ 1 + x1 ⊗ x1 + 1⊗ x11,
which clearly does not lie in the span of the above vectors.
The failure of the comultiplication to respect the rank grading can be viewed
as another artifact of loop-coloop equivalence under the morphism F , as evi-
denced by the fact that the rank grading is respected by comultiplication in the
quotient space corresponding to matroids with neither loops nor coloops. Let
J ⊂ QSym be the ideal generated by degree one elements, i.e. by {N1} = {x
Similarly, let I ⊂ Mat be the ideal generated by degree one elements, i.e. by
{[U0,1], [U1,1]}. Both I and J are Hopf ideals in their respective Hopf algebras,
hence Mat/I and QSym/J (with their naturally induced comultiplications) are
Hopf algebras. Moreover, I = F−1(J), so F : Mat → QSym induces a sur-
jective Hopf algebra morphism Mat/I → QSym/J . Note that a natural basis
for Mat/I is the set of all matroid isomorphism classes that have neither loops
nor coloops, while a natural basis for QSym/J is {Nα : ℓ(α) is even}. Taking
appropriate images under the quotient map, the relation (29) holds in QSym/J .
The duality formula (27) also holds in QSym/J .
7.3 Comparison with other QSym bases
In the course of their proof in Section 10 of [3], the authors introduce two new
Z-bases for QSym. They also compare their bases to another Z-basis due to
Stanley [19].
Our new basis is different from these three, as evidenced by the report by
those authors that all three of these bases have some negative structure con-
stants, whereas our new basis does not. However, of the three, ours most closely
resembles that of Stanley. Stanley’s basis element indexed by a composition
α = (α1, . . . , αm) is F (P ) where, as with our basis, P = A1 ⊕ · · · ⊕ Am, is
the ordered sum of antichains A1, · · · , Am on α1, . . . , αm elements respectively.
However, Stanley applies a natural labeling to P , whereas we apply an alter-
nating labeling to the ranks in the poset for our basis.
7.4 Surjectivity of the Hopf algebra morphism
Billera, Jia, and Reiner devote [3, Section 10] to showing that the morphism
F : Mat → QSym is surjective over rational coefficients. In this subsection we
sketch one way to shorten their proof somewhat using our new basis. The reader
will need to consult [3] to have the full context.
Define an ordering on compositions as follows. To each composition α we
assign the binary word b(α) that begins with α1 zeros followed by α2 ones, then
α3 zeros, then α4 ones, etc. We then linearly order compositions according to
their binary words: α < β if b(α) <lex b(β).
In their proof, Billera, Jia, and Reiner make use of a novel basis for the
quasisymmetric functions based on a family of posets {Rσ} of maximum rank
one, indexed by binary words σ ∈ 0{0, 1}n−1, where n is the number of elements
of the poset. We may equivalently index them using compositions of weight n,
declaring Rα = Rb(α). We refer the reader to [3, Section 10] for the definition of
this basis. Billera, Jia, and Reiner show, through a series of theorems that the
set of {F (Rα)}, where the posets are strictly labeled, forms a Z-basis for QSym.
Using our basis, one can show this more directly. We know from Lemma 5.1
that all β ∈ supp(F (Rα)) are of rank r(α) and weight |α|. It is not too hard
to show that the largest β ∈ supp(F (Rα)) with respect to the above ordering
is precisely α, and that the coefficient of Nα in the expansion of F (Rα) is one.
Thus an array giving the expansion of all the {F (Rα)} of a fixed set size |α| = n
in terms of {Nα} with rows and columns suitably ordered is unitriangular.
Acknowledgments
I wish to thank the referees for their helpful comments. I extend many thanks
to Isabella Novik and Sara Billey for their encouragement and their many hours
of proofreading and advice through several drafts of this manuscript. Thanks
also go to Vic Reiner and Lou Billera for their clarification of parts of their
paper and their helpful comments on this work. Special thanks go to Isabella
Novik for bringing the paper of Billera, Jia, and Reiner to my attention, and
to Vic Reiner for pointing me specifically to [3, Question 7.10], which was the
starting point for my investigation.
While working on this project the author was partially supported by a gradu-
ate fellowship from VIGRE NSF Grant DMS-0354131. The seeds of this project
were planted at the ICM in Madrid, 2006. The trip there was made possible by
funds from NSF Grant DMS-9983797.
References
[1] M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf al-
gebras and generalized Dehn-Sommerville relations., Compos. Math., 142
(2006), pp. 1–30.
[2] A. Barvinok, A Course in Convexity., Graduate Studies in Mathematics.
54. Providence, RI: American Mathematical Society., 2002.
[3] L. J. Billera, N. Jia, and V. Reiner, A quasisymmetric function for
matroids, arXiv:math.CO/0606646.
[4] H. Crapo and W. Schmitt, Primitive elements in the matroid-minor
Hopf algebra, arXiv:math.CO/0511033.
[5] H. Crapo and W. Schmitt, A free subalgebra of the algebra of matroids.,
Eur. J. Comb., 26 (2005), pp. 1066–1085.
[6] , A unique factorization theorem for matroids., J. Comb. Theory, Ser.
A, 112 (2005), pp. 222–249.
[7] , The free product of matroids., Eur. J. Comb., 26 (2005), pp. 1060–
1065.
[8] S. Dăscălescu, C. Năstăsescu, and c. Raianu, Hopf Algebras. An
Introduction., Pure and Applied Mathematics, Marcel Dekker. 235. New
York, NY: Marcel Dekker., 2001.
[9] I. Gel’fand and V. Serganova, Combinatorial geometries and torus
strata on homogeneous compact manifolds., Russ. Math. Surv., 42 (1987),
pp. 133–168.
[10] I. M. Gessel, Multipartite P-partitions and inner products of skew Schur
functions. Combinatorics and algebra, Proc. Conf., Boulder/Colo. 1983,
Contemp. Math. 34, 289-301, 1984.
[11] M. Kapranov, Chow quotients of Grassmannians. I. Gelfand, Sergej (ed.)
et al., I. M. Gelfand Seminar. Providence, RI: American Mathematical
Society. Adv. Sov. Math. 16(2), 29-110, 1993.
[12] L. Lafforgue, Pavages des simplexes, schémas de graphes recollés et com-
pactification des PGLn+1r /PGLr., Invent. Math., 136 (1999), pp. 233–271.
[13] , Chirurgie des grassmanniennes., CRM Monograph Series. 19. Prov-
idence, RI: American Mathematical Society., 2003.
[14] J. G. Oxley, Matroid Theory., Oxford Graduate Texts in Mathematics 3.
Oxford: Oxford University Press., 2006.
[15] W. R. Schmitt, Incidence Hopf algebras., J. Pure Appl. Algebra, 96
(1994), pp. 299–330.
[16] D. E. Speyer, A matroid invariant via the K-theory of the Grassmannian,
arXiv:math.AG/0603551.
[17] R. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math.
Soc., (1972). American Mathematical Society, Providence, RI.
[18] , Enumerative Combinatorics, vol. 2, Cambridge University Press,
Cambridge, MA, 1999.
[19] R. P. Stanley, The descent set and connectivity set of a permutation., J.
Integer Sequences, (2005).
	Introduction
	Preliminaries
	Compositions
	Well-known QSym bases
	Posets and P-partitions
	The new basis
	Additional facts regarding F(P)
	Ordered partitions
	Unordered partitions of X P
	Structure constants for the new basis
	Matroids
	The quasisymmetric function of a matroid
	Expanding F(M) in the {N} basis
	Matroid base polytopes
	Matroid base polytopes and their decompositions
	Results for rank two matroids
	Additional observations
	Matroid duality, loops, and coloops
	Comultiplication
	Comparison with other QSym bases
	Surjectivity of the Hopf algebra morphism

  A new Z-basis for the space of quasisymmetric functions (QSym, for short) is
presented. It is shown to have nonnegative structure constants, and several
interesting properties relative to the space of quasisymmetric functions
associated to matroids by the Hopf algebra morphism (F) of Billera, Jia, and
Reiner. In particular, for loopless matroids, this basis reflects the grading
by matroid rank, as well as by the size of the ground set. It is shown that the
morphism F is injective on the set of rank two matroids, and that
decomposability of the quasisymmetric function of a rank two matroid mirrors
the decomposability of its base polytope. An affirmative answer is given to the
Hilbert basis question raised by Billera, Jia, and Reiner.

Introduction
In this paper we construct a new Z-basis for the space of quasisymmetric
functions, QSym and study its properties. For instance, we show that it has
nonnegative structure constants, and that it behaves well with respect to the
quasisymmetric functions associated to matroids by the Hopf algebra morphism
Mat → QSym described by Billera, Jia, and Reiner [3]. We also answer in the
affirmative a question regarding rank two matroids posed in [3, Question 7.10],
and give an affirmative answer to [3, Question 7.12] in the case of rank two
matroids.
In [3], Billera, Jia, and Reiner describe an invariant for matroids in the form
of a quasisymmetric function. They show that the mapping F : Mat → QSym
is in fact a morphism of combinatorial Hopf algebras (given a suitable choice of
character on Mat; see [1]), where Mat is the Hopf algebra of matroids introduced
by Schmitt [15], and studied by Crapo and Schmitt [4], [5], [6], [7]. Billera,
Jia, and Reiner show that, while the mapping F is not surjective over integer
coefficients, it is surjective over rational coefficients.
http://arxiv.org/abs/0704.0836v2
Our new basis for QSym is “matroid-friendly” in that it reflects the rank of
loopless matroids as well as the size of the ground sets: for every 1 ≤ r ≤ n,
there is a set Nnr of
basis vectors such that for every loopless matroid
M of rank r on an n-element ground set, F (M) ∈ span Nnr ; moreover, QSym
decomposes as the direct sum of these subspaces. This provides us with a new
product grading of QSym, according to matroid rank r. (The usual grading of
QSym by degree corresponds to the size n of the matroid ground set.) Also,
as with the monomial and fundamental bases of QSym, for every matroid M ,
F (M) has nonnegative coefficients in our basis.
The paper has two main parts. The first part (Sections 2–4) presents the new
basis and relevant background material. In Section 2, we recount background
material from the literature regarding posets and quasisymmetric functions. In
Section 3, we present a definition for our new basis for QSym by means of a
construction, and highlight several of its important features. There we also
prove that it is a Z-basis for QSym. In Section 4, we build necessary machinery
regarding computing the quasisymmetric function associated to a labeled poset,
in the form of alternative decompositions, and apply these tools to prove that
the structure constants of the new basis are nonnegative.
The second part, (Sections 5–7) discusses matroids and their quasisymmetric
functions. In Section 5, we recall some of the concepts, terminology, and results
from the paper [3], and prove our claims regarding the quasisymmetric functions
of matroids vis-a-vis our new basis. In Section 6, we recall the context of [3,
Section 7] regarding the relationship between decompositions of the quasisym-
metric function associated to a matroid and decompositions of its matroid base
polytope, and recall the statement of [3, Question 7.10] regarding the functions
associated to rank two matroids. We develop a formula for the quasisymmetric
function of a loopless rank two matroid in terms of the new basis, and apply
it to show (1) that the morphism F : Mat → QSym distinguishes isomorphism
classes of rank two matroids, (2) that the two types of decompositions mirror
each other, i.e. an affirmative answer to [3, Question 7.12] for the case of rank
two matroids, and (3) to give an affirmative answer to [3, Question 7.10]. In
Section 7, we make additional observations regarding matroid functions and the
new basis. We also compare the new basis with the other QSym bases discussed
in Section 10 of [3], and sketch an alternate proof of the surjectivity of the map
Mat → QSym over rational coefficients.
2 Preliminaries
In this section we quote certain concepts, terminology, and facts from the litera-
ture, as well as establish certain conventions which will be used in the remainder
of the paper.
2.1 Compositions
A composition α is a finite sequence of positive integers, i.e. α ∈ Pm for some
m ∈ N. The number of parts of α, m, is the length of α, and denoted by ℓ(α).
The weight of α = (α1, . . . , αm) is |α| = α1+ · · ·+αm. Included in our definition
is the composition having no parts, which we denote by the (bold font) symbol
0. We have ℓ(0) = |0| = 0, the only composition with these properties.
Note, for small examples where individual parts are less than 10, we will
often write a composition as a sequence of digits, with no separating commas.
For example, we may write (1, 5, 6, 3, 2, 3) as 156323 when the context is clear.
We adopt a similar convention for the one-line notation of permutations in Sn
when n < 10.
There is a natural bijection between compositions of weight |α| = n and
susbets of [n− 1] (where [n] = {1, 2, 3, . . . , n}), given by
(α1, . . . , αm) ↔ {α1, α1 + α2, α1 + α2 + α3, . . . , α1 + · · ·+ αm−1}.
We say that β is a refinement of α, or that β refines α (denoted β 4 α)
if |α| = |β| and A ⊂ B, where A and B are the sets associated to α and β
respectively.
To any permutation π ∈ Sn there is an associated composition of weight n
which we denote C(π) and whose parts give the lengths of successive increasing
runs in the one-line notation of π. For example, for π = 934756218 ∈ S9, we have
C(π) = 13212. In this paper, we mildly generalize the notion of a permutation
to be any sequence of distinct positive integers. Given a set of positive integers
X , we let S(X) denote the set of all permuations of all the elements of X . The
run length operator C(π) extends to these general permutations in the obvious
way. If X and Y are two sets of positive integers of the same cardinality n,
then every bijection f : X → Y induces a mapping f : S(X) → S(Y ) given by
f(x1, . . . , xn) = (f(x1), . . . , f(xn)). If f is an increasing function, then we have
C(f(π)) = C(π) for every π ∈ S(X).
2.2 Well-known QSym bases
The algebra of quasisymmetric functions QSym (or QSym(x) when we want
to emphasize the variable set) forms a subring of the power series ring R[[x]]
where x = (x1, x2, x3, ...) is a linearly ordered set of variables indexed by the
positive integers, and R is a (fixed) commutative ring. In this paper we only
deal with the cases where R is either Z or Q, assuming coefficients in Q unless
otherwise stated. We often suppress the variables in our notation, writing simply
f ∈ QSym rather than f(x) ∈ QSym(x).
There are a number of well-known bases for QSym, all indexed by compo-
sitions. (For the two considered here, see [10].) The best-known is the basis
of monomial quasisymmetric functions, which here we denote {xα}. Given a
composition α with ℓ(α) = k, xα is defined by
xα :=
1≤i1<i2<···<ik
xα1i1 x
· · ·xαkik .
Another frequently used basis is the set {Lα} of fundamental quasisymmetric
functions, defined by
Lα :=
For example, L1 = x
1 is simply the degree one elementary symmetric function.
We note that QSym as an algebra under the usual multiplication is graded by
degree. For each of the bases described above, the set of basis elements indexed
by all the compositions of a fixed weight n forms a basis for the homogeneous
component of degree n, QSymn. Accordingly, dimQSymn = 2
2.3 Posets and P -partitions
One of the early references to quasisymmetric functions is the paper of Ges-
sel [10] (who built on the work of Stanley [17]), where they are related to P -
partitions of labeled posets. Most of this material can also be found in Stanley
[18]. In the following, we let ≤ denote the usual ordering on integers, and ≤P
denote the partial order of a poset P . All posets we consider here are finite.
We adopt a mild generalization of Gessel’s convention. We say that a labeled
poset on n elements is a partial order on a set of n positive integers. These
integers are referred to as the labels of the poset. Usually the set of labels is
[n] = {1, 2, . . . , n}, but sometimes we make use of other labels. We often use the
same symbol to refer to both the poset and its set of labels when the meaning
is clear from context.
Note. This convention differs from that used in [3]. There, a labeled poset
consists of a pair (P, γ), where P is a poset on an arbitrary set of n elements,
and γ is a labeling of P , that is a bijection between the elements of P and the
set [n]. The notion is equivalent to Gessel’s. For our generalization, the labeling
would be an injective function from the set of elements of the poset into the set
P of positive integers. At times we find it convenient to write (P, γ) when we
wish to discuss various labelings on the same underlying unlabeled poset.
The following is not the actual definition used in [10] and [17], but rather is
a formula developed by Stanley in [17]. We take it as our definition here.
Definition 2.1. Let P be a labeled poset. Let L(P ) denote the Jordan-Hölder
set of P, that is, the set of all permutations in S(P ) that are linear extensions
of P . Then the quasisymmetric function of P is
F (P ) :=
π∈L(P )
LC(π). (1)
Remark 2.1. The function F (P ) depends only on the relative partial order of
the labels at each covering relation of the poset and not on the absolute values
of the labels themselves. Given labeled posets P defined on the set of labels
A, and P ′ defined on the set of labels B, and a function f : A → B which is
an isomorphism of their underlying unlabeled posets, then F (P ) = F (P ′) if for
every covering relation (y covers x) in P we have x < y ⇐⇒ f(x) < f(y).
3 The new basis
The main goal of this section is to define our new basis (see Definition 3.1
below) and to prove that it is in fact a Z-basis of QSym, that is to say, every
quasisymmetric function that can be written in terms of either the standard
monomial or fundamental basis using only integer coefficients can also be written
in terms of the new basis using only integer coefficients. In Section 4.3, we prove
the positivity of the structure constants for this new basis and the grading of
QSym by composition rank.
Following the notation of [3], given unlabelled posets P and Q, we denote
by P ⊕Q their ordinal sum. The set of elements of P ⊕Q is the disjoint union
of the elements of P and Q. All of the order relations of P and Q are retained,
and in addition, x <P⊕Q y for all x ∈ P and y ∈ Q.
As with all the well-known bases for QSym, the elements of the new basis
are indexed by compositions. We denote the basis by {Nα}, where α ranges
over all compositions.
Definition 3.1. For a given composition α 6= 0, let Pα = A1 ⊕ · · · ⊕ Am be
the graded poset on |α| elements, where m = ℓ(α) and Ai is an antichain on αi
elements. Make Pα into a labeled poset by numbering the ranks in alternating
fashion: first number the odd-ranked elements A2, A4, . . ., followed by the even-
ranked elements A1, A3, . . .. We define N0 := 1, and for each α 6= 0, we define
Nα := F (Pα) (see Equation (1)).
Example 3.2. Let α = (1, 2, 2). Then
P122 = {3} ⊕ {1, 2} ⊕ {4, 5},
L(P122) = {(31245), (31254), (32145), (32154)}, and
N122 = L14 + L131 + L113 + L1121.
Definition 3.3. Given a composition α = (α1, . . . , αk), the rank of α, denoted
by r(α), is the sum of the odd-indexed parts of the composition. That is,
r(α) :=
odd i
αi = α1 + α3 + α5 + · · · . (2)
We define N 00 := {N0} = {1}, and for 1 ≤ r ≤ n,
Nnr := {Nα : |α| = n and r(α) = r}. (3)
We also define the subspace V nr := span N
r ⊂ QSymn. If we are working over a
field of coefficients for QSym, then V nr may be viewed as a vector space, whereas
if we are working over integer coefficients then we refer to the Z-span of Nnr and
V nr is a Z-module.
Theorem 3.4. The set of quasisymmetric functions {Nα}, as α ranges over
all compositions, forms a Z-basis for QSym.
Proof. We show that {Nα}|α|=n forms a basis for the homogeneous component
QSymn for each nonnegative integer n. This is trivial for n = 0. For the general
case, we prove the existence of a unitriangular transition matrix from {Nα}|α|=n
of QSymn to the fundamental basis {Lα}|α|=n.
Consider the following construction. Given a permutation ω ∈ Sn, let b(ω) ∈
1{0, 1}n−1 be the n-digit binary word where the digits are given by
1 if i = 1 or ω(i− 1) < ω(i),
0 otherwise.
Then define ρ(ω) to be the composition which gives the lengths of succes-
sive runs of 1’s and 0’s in b(ω). For example, if ω = 184356729 ∈ S9 then
b(ω) = 110011101, and ρ(ω) = 22311. Clearly one can determine the run-length
composition C(ω) from ρ(ω) and vice versa.
Given a composition α, let Pα be the labeled poset in Definition 3.1, and
L(Pα) its set of linear extensions. Recall that by definition
Nα :=
π∈L(Pα)
LC(π).
By the nature of the labeling on Pα, ρ(π) 4 α for all π ∈ L(Pα). Furthermore,
there is a unique element π ∈ L(Pα) such that ρ(π) = α, namely the one in
which all the labels of Ai are in ascending order if i is odd, and in descending
order if i is even. Thus if we order the rows of the transition matrix (labeled
by compositions α) and columns (labeled by compositions ρ(π)) in an arbitrary
way that extends the partial refinement order 4, then the resulting matrix is
unitriangular, and hence {Nα} is indeed a Z-basis for QSym.
4 Additional facts regarding F (P )
In this section we develop several additional facts regarding the quasisymmetric
function F (P ) for labeled posets P , including an alternative way to decompose
F (P ) for posets, the main idea being to partition L(P ). These facts, especially
Lemmas 4.1 through 4.4, are key tools for the results in following sections.
4.1 Ordered partitions
Consider a permutation π = (π1, . . . , πn) ∈ S(X), where |X | = n, and a compo-
sition τ = (τ1, . . . , τk) with |τ | = n. We can “chop up”, or segment the one-line
notation of π from left to right into k segments, where each respective segment
si is a subsequence of consecutive elements of the one-line notation of length τi.
We call the sequence of these segments s = (s1, . . . , sk) a segmentation of π of
type τ (or induced by τ). Letting t0 = 0 and tj =
i=1 τi be the j-th partial
sum of the parts of τ , every permutation π ∈ S(X) has a unique segmentation
sτ (π), whose segments, for 1 ≤ j ≤ k, are given by
sj = (πtj−1+1, πtj−1+2, . . . , πtj ).
An ordered partition K = (K1, . . . ,Kk) of a set X ⊂ P is a partitioning of X
into non-empty, pairwise disjoint subsets called blocks, i.e. X = ⊔ki=1Ki, where
the order of the blocks matters. Let τi = |Ki| for all i, and refer to the resulting
composition τ(K) = (τ1, . . . , τk) as the type of K.
Let K(X) denote the set of all ordered partitions of X . Every composition
τ of weight n induces a mapping Kτ : S(X) → K(X) as follows. For every
π ∈ S(X) there is a unique ordered partition Kτ (π), each of whose blocks Kj is
the set of elements in the corresponding segment sj of the segmentation sτ (π).
We abbreviate the inverse image K−1τ (K) as K
−1(K) since, for a given or-
dered partition K, the type τ , the set of elements X , and thus the permutation
group S(X), can all be determined from K. Thus for an ordered partition K,
we have
K−1(K) := {π ∈ S(X) : Kτ(K)(π) = K}. (4)
For example, K−1(({2, 7}, {5}, {1, 8})) = {27518, 27581, 72518, 72581}.
The following lemma is simply an exercise in notation, so we omit its proof.
Lemma 4.1. Let K be an ordered partition with k blocks. Let PK be the labeled
poset PK = K1 ⊕ · · · ⊕Kk, where each Ki is regarded as an antichain. Then
F (PK) =
π∈K−1(K)
LC(π).
We say that an ordered partitionK = (K1, . . . ,Kk) is alternating if for every
1 ≤ i < k and for all x ∈ Ki and y ∈ Ki+1 we have x < y if i is even and x > y
if i is odd.
Lemma 4.2. Let K be an alternating ordered partition of type τ . Then
F (PK) = Nτ .
Proof. Each rank Ki of PK = K1 ⊕ · · · ⊕Kk (where ℓ(τ) = k) is an antichain.
Hence F (PK) depends only on the relative ordering of the elements between
adjacent ranks Ki and Ki+1 (see Remark 2.1). Since K is alternating, we can
relabel its elements in each rank as we do in the construction of Pτ (as in
Definition 3.1) and still maintain the same relative ordering between elements
in adjacent ranks. Thus F (PK) = F (Pτ ) = Nτ .
4.2 Unordered partitions of X ⊂ P
Let T = {T1, . . . , Tm} be an unordered partition of the set X ⊂ P. We say that
an ordered partition K is a refinement of T if K, considered as an unordered
partition, is a refinement of T . For every permutation π ∈ S(X), T induces a
unique segmentation of π where each segment is contained in a block of T and
this segmentation is least (coarsest), with respect to refinement, among all such
segmentations. Corresponding to this segmentation there is a unique ordered
partition KT (π), which clearly is is a refinement of T . We say that T induces
the ordered partition KT (π) on π.
Example 4.3. Let X = [9], T = { {1, 4}, {2, 6, 8, 9}, {3, 5, 7} }, π = 965412378.
Then KT (π) = ({6, 9}, {5}, {1, 4}, {2}, {3, 7}, {8}).
Let P be a labeled poset, and T an unordered partition of P . Define KP,T
to be the set of induced ordered partitions KP,T := {KT (π) | π ∈ L(P )}. We
say that T is antichain-inducing if for every ordered partition K ∈ KP,T , every
block Ki of K is an antichain in P .
Lemma 4.4. Let T be an antichain-inducing unordered partition of a labeled
poset P . Then
F (P ) =
K∈KP,T
F (PK). (5)
We call this the decomposition of F (P ) with respect to T .
Proof. By Lemma 4.1 it suffices to show that
L(P ) =
K∈KP,T
K−1(K).
The “⊂”-direction is trivial. Indeed, T induces some ordered partition on every
permutation, and by definition KP,T includes all such partitions as permutations
range over L(P ). Also, clearly K−1(K) ∩ K−1(J) = ∅ if K 6= J since KT is a
well-defined map on L(P ), and so the union on the right is indeed a disjoint
union.
For the “⊃”-direction, let K ∈ KP,T . By definition of KP,T , there exists
π ∈ L(P ) ∩ K−1(K). Let s = sτ(K)(π). Since T is antichain-inducing, the
unordered set of elements Ki of each segment si is an antichain. It follows that
if we form a new permutation π̂ by permuting the elements of si arbitrarily
within si (and thus within π), we must also have that π̂ ∈ L(P ). Since this
holds true for each segment of s, we have K−1(K) ⊂ L(P ).
Remark. In the extreme case where T consists of all singleton sets, KT (π) is the
list of singleton sets in the order specified by π, and K−1(KT (π)) = {π}. We
can identify KT (π) with π itself, and similarly KP,T with L(P ), and the lemma
is then equivalent to the formula (1).
4.3 Structure constants for the new basis
Following the notation of [3] and [17], given labeled posets P and Q on sets
X and Y respectively, we denote by P + Q any disjoint sum of the posets,
constructed as follows. We first form the poset whose set of elements is the
disjoint union of the sets of elements of P and Q, retaining all partial order
relations of the two posets but adding no new relations. In order to ensure that
all labels are distinct, we then relabel the elements in any fashion subject to
the restriction that the resulting labels are all distinct and preserve the relative
order of labels at all covering relations (see Remark 2.1). While the disjoint sum
of the labeled posets is not uniquely defined, all disjoint sums so constructed
will have the same quasisymmetric function. It is well-known and is easy to
prove (see, for example, [10]) that
F (P +Q) = F (P ) · F (Q). (6)
We are now in a position to prove the nonnegativity of the structure constants
for our new basis.
Theorem 4.5. The quasisymmetric function algebra QSym is graded by the
rank of the compositions indexing the basis {Nα}. Furthermore, the structure
constants for {Nα} are nonnegative. That is, in the expansion
NαNβ =
cνα,βNν ,
all the constants cνα,β are nonnegative integers.
Proof. We first prove the statement regarding structure constants. Since N0 =
1, the claim holds trivially if α = 0 or β = 0. Thus we assume α = (α1, . . . , αs) 6=
0 and β = (β1, . . . , βt) 6= 0. By (6) we have that
NαNβ = F (Pα)F (Pβ) = F (Pα + Pβ). (7)
We write Pα = A1 ⊕ · · · ⊕As and Pβ = B1 ⊕ · · · ⊕Bt, and identify the Ai and
Bj subsets with their canonical inclusions in Pα + Pβ .
We form a new poset Q by relabeling the elements of the Ai and Bj subsets
while maintaining their ordering relations: first label the even-indexed Ai and
Bj in order, with the numbers from [m], where m = |α|+ |β| − r(α)− r(β) and
r(α) is the rank function from Definition 3.3, then label the odd-indexed Ai and
Bj in order, with the numbers from {m + 1, . . . , |α| + |β|}. Since F (Pα + Pβ)
depends only on the relative ordering of elements between adjacent ranks Ai
and Ai+1 for 1 ≤ i < s and between adjacent ranks Bj and Bj+1 for 1 ≤ j < t,
we have
F (Pα + Pβ) = F (Q). (8)
We consider the unordered partition T = {T1, T2} of Q given by
odd i
odd i
, and T2 =
even i
even i
Note that T is antichain-inducing, so we may apply Lemma 4.4:
F (Q) =
K∈KQ,T
F (PK). (9)
On the other hand, the labeling of Q implies that every ordered partition K ∈
KQ,T is alternating, so applying Lemma 4.2, we have
F (Q) =
K∈KQ,T
Nτ(K). (10)
Combining Equations (7) – (10) yields the positivity claim. In particular,
cνα,β = |{K ∈ KQ,T : τ(K) = ν}|.
To prove the statement regarding the grading of QSym by composition rank,
we simply note that for every K ∈ KQ,T , we have
r(τ(K)) = |T1| = r(α) + r(β).
5 Matroids
This section begins the second part of the paper. Here we review some of
the concepts, terminology, and results from [3], and prove our claims regarding
the quasisymmetric functions of matroids vis-a-vis our new basis. For general
background in matroid theory we refer the reader to standard texts such as
Oxley’s [14]. We review several of the terms here.
The direct sum of matroids M1 and M2, denoted M1⊕M2, has as its ground
set the disjoint union E(M1 ⊕M2) = E(M1) ⊔ E(M2), and as its bases
B(M1 ⊕M2) = {B1 ⊔B2 : B1 ∈ B(M1), B2 ∈ B(M2)}.
A circuit is a minimal dependent set. If we declare two elements of a matroid
to be equivalent if and only if they are both contained in some circuit, then
the equivalence classes of elements are the components of the matroid. We say
that the matroid is connected if it has only one component, and disconnected
otherwise. A matroid is the direct sum of its components.
5.1 The quasisymmetric function of a matroid
Billera, Jia, and Reiner [3] describe an invariant for isomorphism classes of
matroids in the form of a quasisymmetric function. Rather than give the defi-
nition from [3], we describe it in terms of a formula which is shown in [3] to be
equivalent to the definition.
Fix a matroid M , one of its bases B ∈ B(M), and let Bc = E(M)−B (the
cobase of B). Define the poset PB on the ground set E(M) where e <PB e
and only if e ∈ B, e′ ∈ Bc, and (B − e)∪ {e′} ∈ B(M). That is, e <PB e
′ if and
only if swapping e′ for e in B yields another base in M . Thus the Hasse diagram
of PB is a bipartite graph in which the elements of B are minimal elements of
the poset and the elements of Bc are maximal elements. Note that if M has no
loops, then in the Hasse diagram of PB , every element in B
c has positive vertex
degree. We say that a labeled poset is strictly labeled if for all x, y ∈ P we have
that x <P y implies x > y. Similarly, a labeled poset is naturally labeled if for
all x, y ∈ P , x <P y implies x < y. We apply a strict labeling to PB (any will
do). The quasisymmetric function F (M) associated with M can be written as
F (M) =
B∈B(M)
F (PB), (11)
where F (PB) is the quasisymmetric function of the strictly labeled poset PB as
defined in Definition 2.1.
It was shown in [3] that the mapping F : Mat → QSym is in fact a morphism
of combinatorial Hopf algebras, with a suitable choice of character on the algebra
Mat. Here Mat is the Hopf algebra of matroids introduced by Schmitt [15] and
studied by Crapo and Schmitt [4], [5], [6], [7]. The matroid algebra Mat has as
its basis elements isomorphism classes of matroids. The product of two basis
elements [M1] and [M2] in the algebra is given by [M1] · [M2] := [M1 ⊕ M2],
where M1 ⊕M2 denotes the direct sum of matroids. Comultiplication in Mat is
given by ∆([M ]) :=
A⊂E(M)[M |A]⊗ [M \A], where M |A is the restriction of
M to A, and M \ A is the contraction of M by A. Under the morphism F we
have that
F (M1 ⊕M2) = F (M1) · F (M2).
Billera, Jia, and Reiner also show that the mapping F , while not surjective over
integer coefficients, is surjective over rational coefficients.
The mapping F : Mat → QSym does not distinguish between loops and
coloops. Indeed, let M ′ extend the matroid M by adding a loop ℓ, i.e. M ′ =
M ⊕ {ℓ}, and let M ′′ extend the matroid M by adding a coloop c, i.e. M ′′ =
M ⊕ {c}. Then
F (M ′) = F (M ′′) = F (M) · L1. (12)
Here L1 is the fundamental basis function indexed by the composition (1), which
is the elementary symmetric function e1(x). Define an equivalence relation ∼
on isomorphism classes of matroids by [M1] ∼ [M2] if and only if one can obtain
M1 from M2 by changing some number of loops to coloops or vice versa. Then
by Equation (12) the mapping Mat → QSym factors through the quotient
Mat → Mat/∼ → QSym.
Accordingly, throughout most of our paper, we assume that, unless otherwise
specified, our matroids have no loops; that is, out of each equivalence class in
Mat/∼ we select the representative that has no loops when considering their
images in QSym.
5.2 Expanding F (M) in the {N
} basis
Recall from Definition 3.3 that Nnr = {Nα : |α| = n, r(α) = r} and V
spanNnr . In this subsection we may take our coefficient ring to be Z if we wish.
Lemma 5.1. Let P be a strictly labeled poset on n elements of rank at most
one and with r minimal elements. Then F (P ) ∈ V nr . Moreover the expan-
sion of F (P ) in terms of the basis elements Nnr has only nonnegative integer
coefficients.
Proof. If P has rank 0, then P is an antichain and so r = n. Thus by labelling
P with the elements of [n] and taking α = (n), we have
F (P ) = F (Pα) = Nα = N(n) ∈ V
Otherwise P has rank 1 and is not an antichain. Let T = {T1, T2} be the
unordered partition of P in which T1 comprises the r minimal elements of P ,
and T2 the remaining elements. Note that some elements may be both minimal
and maximal, and these will be placed in T1. Thus every element in T2 in
the Hasse diagram of P has positive vertex degree. Since we are interested in
computing F (P ), we may assume without loss of generality that P has a strict
labeling which labels the elements of T1 = {n, n− 1, . . . , n− r+ 1} in arbitrary
fashion, and the elements of T2 = {1, 2, . . . , n − r} in arbitrary fashion. Since
T1 and T2 are themselves antichains, T is antichain-inducing, so by Lemma 4.4:
F (P ) =
K∈KP,T
F (PK).
Moreover, by the choice of labeling and the fact that every element in T2 has
positive vertex degree, we have that every K ∈ KP,T is alternating. Lemma 4.2
then implies
F (P ) =
K∈KP,T
Nτ(K).
We also have that |τ(K)| = n and r(τ(K)) =
odd i τi = |T1| = r, thus Nτ(K) ∈
V nr for every K ∈ KP,T . Hence F (P ) ∈ V
r as claimed.
Theorem 5.2. Let M be a loopless matroid of rank r on n elements. Then
F (M) ∈ V nr . Moreover the expansion of F (M) in terms of the basis elements
Nnr has only nonnegative integer coefficients.
Proof. For a loopless matroid M , for every base B ∈ B(M), the base poset PB
has r minimal elements out of a total of n elements, and rank at most one. The
assertion then follows by Lemma 5.1, and the formula in Equation (11).
We make a few observations here about the coefficients in the expansion of
the quasisymmetric function F (M) of a matroid M in terms of our new basis.
Given a quasisymmetric function q, define
supp(q) =
α : mα 6= 0 in the expansion q =
We first note that for a (loopless) matroid M of rank r on n elements, the
coefficient m(r,n−r) of Nα, where α = (r, n− r), is equal to the number of bases
of M .
Example 5.3. Let M = Ur,n be the uniform matroid of rank r on n elements.
By definition, its bases are all the r-subsets of the ground set E(M), i.e. B(M) =(
. Then every PB has a complete bipartite Kr,n−r graph for its Hasse
diagram. Therefore F (Ur,n) =
Nr,n−r, and supp(F (M)) = {(r, n− r)}.
Thus the values of m(r,n−r) (how small) and |supp(F (M))| (how large) are,
to some extent, measures of the degree to which M fails to be uniform.
The coefficient mα where α = (r− 1, 1, 1, n− r− 1) also has a combinatorial
interpretation. There is such an Nα term for every edge “missing” from the
Hasse diagram of a base poset PB as compared to the complete bipartite graph
Kr,n−r. In terms of matroid base polytopes, which are discussed in 6.1, the
polytope Q(Ur,n−r) contains all possible vertices, namely
, while the base
polytope for a different matroid M of same rank and ground set size has only a
subset of them, namely B(M). The coefficient mα is the number of edges in the
1-skeleton of Q(Ur,n−r) between the set of vertices B(M) and its complement(
− B(M).
Lemma 5.4. Let M be a matroid, possibly containing loops. Then the total
number c of loops and coloops is given by
c = max
α∈supp(F (M)),
ℓ(α) odd
α̇, (13)
where α̇ denotes the last part of the composition α.
Proof. Since the morphism F : Mat → QSym factors through loop-coloop equiv-
alence, F (M) = F (M ′) where M ′ is obtained from M by replacing all loops of
M with coloops. Since M and M ′ both have the same total number of loops
and coloops, without loss of generality, we assume that M has no loops.
Consider a typical strictly labeled base poset PB of M, and antichain inducing
partition {B,Bc} as in the proof of Lemma 5.1. We have α ∈ supp(F (M)) if
and only if there is an induced ordered partition K of PB of type α. Now ℓ(α)
is odd if and only if the last block of K is a subset of B, and in this case the
elements in this block must be coloops. Thus c ≥ α̇. Conversely, there always
exists an induced ordered partition of the poset, say of type α, which has all of
the coloops of M in the last block, i.e. c = α̇, and this ordered partition will
have odd length. The result follows.
6 Matroid base polytopes
In this section we recall the context of [3, Section 7] regarding the relationship
between decompositions of the quasisymmetric function associated to a matroid
and decompositions of its matroid base polytope. In Subsection 6.2 we develop a
formula for the quasisymmetric function of a loopless rank two matroid in terms
of the new basis, and apply it to address [3, Question 7.12] and [3, Question
7.10].
6.1 Matroid base polytopes and their decompositions
The motivating context is to study the decompositions of the matroid base
polytope Q(M) of a matroid M . This topic arises in the work of Lafforgue [12],
[13], Kapranov [11, §1.2 – 1.4], and can be found in the work of Speyer [16].
If M is a matroid with |E(M)| = n, we define the matroid base polytope
Q(M) by identifying E(M) with the set of standard basis vectors {ei}
i=1 of R
and declaring
Q(M) := conv
ei : B ∈ B(M)
where B(M) is the set of bases of M . Useful facts about matroid base polytopes
(see [9]), which we quote without proof, are:
1. If M has rank r, then Q(M) lies in the hyperplane {x ∈ Rn :
i xi = r}.
2. There is an edge in Q(M) between vertices (bases) B1 and B2 if and
only if there exist a pair of elements ei ∈ B1 and ej ∈ B2 such that
B2 = (B1 − {ei}) ∪ {ej}.
3. Each face of a matroid base polytope is in turn the base polytope of some
matroid.
4. The dimension of Q(M) is |E(M)| − s(M), where s(M) is the number of
connected components of M .
Billera, Jia, and Reiner define a matroid base polytope decomposition of Q(M)
to be a decomposition
Q(M) =
Q(Mi), (14)
where each Q(Mi) is also a matroid base polytope for some matroid, and for
each i 6= j, the intersection Q(Mi) ∩ Q(Mj) = Q(Mi ∩ Mj) is a face of both
Q(Mi) and Q(Mj). They call such a decomposition a split if t = 2.
Billera, Jia, and Reiner show that the mapping F : Mat → QSym behaves as
a valuation on matroid base polytopes. (See [2] for a discussion of valuations.)
This implies that, given a matroid base polytope decomposition as in Equation
(14), F (M) can be expressed in terms of the set of F (Mj) in an inclusion-
exclusion fashion, where the Mj are the matroids of the faces of the constituent
polytopes in the decomposition. For example, given a split Q(M) = Q(M1) ∪
Q(M2), we have F (M) = F (M1) + F (M2) − F (M1 ∩M2), where Q(M1 ∩M2)
is necessarily a lower-dimensional face. Hence by Fact 4 above, the matroid
M1 ∩M2 is disconnected, and so F (M1 ∩M2) can be expressed as a product.
If we let m :=
d≥1 QSymd be the maximal ideal in the ring QSym, then
F (M1∩M2) ∈ m
2. Therefore in the quotient space QSym/m2, we have F (M) =
F (M1) + F (M2). In general, given a matroid base polytope decomposition as
in Equation (14), there is an algebraic decomposition modulo m2
F (M) =
F (Mi). (15)
One of the open questions raised by Billera, Jia, and Reiner [3] is under what
conditions the converse may hold; given a collection of matroids satisfying (15),
what additional conditions are sufficient to conclude (14)?
Note. So far we have ignored the distinction between the isomorphism class of a
matroid on the one hand and a specific instance of that class on a given ground
set on the other, since the quasisymmetric function of a matroid is invariant
on the elements of the same isomorphism class. When discussing the existence
of matroid base polytope decompositions, it is sometimes necessary to draw a
distinction between the notions, as is done in the statement of Theorem 6.2
below. When this precision is necessary, we use the usual bracket notation [M ]
to denote the isomorphism class of the matroid M .
Given a ground set size n, the converse question is trivial for rank 0 and 1,
and by matroid duality, for rank n and n − 1. One necessary condition they
point out is that a specific set of matroids on a common ground set satisfying
(14) must at least satisfy the condition B(Mi) ⊂ B(M) for all i, in which case
they say that (15) is a weak image decomposition and that F (M) is weak image
decomposable. They specifically ask,
[3, Question 7.12] Does F (M) being weak image decomposable in
QSym/m2 imply that Q(M) is decomposable?
So far, general sufficient conditions are not known beyond the trivial ranks listed
above. We claim that the converse ((15) ⇒ (14)) holds quite generally for rank
two matroids, as shown in Section 6.2. By matroid duality, the converse also
holds for matroids of corank two.
As discussed in [3], the loopless rank two matroids are indexed, up to iso-
morphism, by partitions having two or more parts, where there are as many
parts as there are parellelism classes of elements in the matroid and the parts of
the partition give the respective cardinalities of these classes. For this section
we write Mλ to denote the loopless rank two matroid indexed by the partition
λ. More generally, given a composition α, define Mα = Mλ where λ is the
decreasing rearrangement of the parts of α.
Kapranov [11, §1.3] gives a description of all decompositions of rank two
matroid base polytopes. He shows [11, Lemma 1.3.14] that in rank two, all
matroid base polytope decompositions arise from hyperplane splits. We provide
some description here of the geometric situation, in our own words. Given the
composition λ = (λ1, . . . , λm), with |λ| = n, set t0 = 0 and for 0 ≤ k ≤ m set
i=1 λi be the k-th partial sum. Then the vertices of Q(Mλ) are precisely
those 0/1-lattice points v lying in the hyperplane H = {x ∈ Rn :
i xi = 2}
subject to the restriction that
tk+1∑
i=tk+1
vi ≤ 1
for all 0 ≤ k < m. If ℓ(λ) = 2, then
Mλ = M(λ1,λ2) = U1,λ1 ⊕ U1,λ2 ,
where U1,n is the uniform matroid of rank 1 on n elements. It follows that if
ℓ(λ) = 2, then dimQ(Mλ) = n− 2 and F (Mλ) ∈ m
Supposing that ℓ(λ) = m > 3, choose index j such that 1 < j < m− 1. Let
a = tj and b = n− tj , and define compositions µ = (a, b), α = (a, λj+1, . . . , λm),
and β = (λ1, . . . , λj , b), all of which have weight n. Consider the hyperplane
H ′ = {x ∈ Rn :
i=1 xi = 1}. Then H
′ ∩ Q(Mλ) = Q(Mµ), giving us a
hyperplane split Q(Mλ) = Q(Mα) ∪ Q(Mβ). It follows from the above that
F (Mλ) = F (Mα) + F (Mβ) − F (Mµ), and F (Mλ) = F (Mα) + F (Mβ). We
can summarize this in the following proposition. The relations given in the
proposition remain true even if λ has only two or three parts, but in that case
the resulting relations are trivial.
Proposition 6.1. Let λ = (λ1, . . . , λt) be a composition with at least two parts.
Let 1 ≤ s < t, a =
i=1 λi, and b =
i=s+1 λi. Consider compositions
α = (a, λs+1, . . . , λt), β = (λ1, . . . , λs, b), and µ = (a, b). We then have
F (Mλ) = F (Mα) + F (Mβ)− F (Mµ),
and modulo m2,
F (Mλ) = F (Mα) + F (Mβ).
Moreover there is a split of matroid base polytopes
Q(Mλ) = Q(Mα) ∪Q(Mβ).
The splitting process can be repeated on the constituent matroid base polytopes
until we have decomposed Q(Mλ) into the union of matroid base polytopes of
type Q(Mα) where ℓ(α) = 3. Consequently, modulo m
2, F (Mλ) can be written
as a positive sum
F (Mλ) =
F (Mi),
where each Mi is a loopless rank 2 matroid indexed by a partition of length 3.
In this setting, Billera, Jia, and Reiner , pose the following question:
[3, Question 7.10] Fix n and consider the semigroup generated by
F (M) within QSymn/m
2 as one ranges over all matroids M of rank
2 on n elements. Is the Hilbert basis for this semigroup indexed by
those M for which λ(M) has exactly 3 parts?
By repeated application of Proposition 6.1, the set {F (Mλ) : ℓ(λ) = 3}
generates the semigroup in question, so the point of the question is whether this
generating set is minimal, and whether distinct indices yield distinct functions.
We prove that this is the case as a corollary of Theorem 6.2.
6.2 Results for rank two matroids
In this section, we prove that the morphism F : Mat → QSym distinguishes
isomorphism classes of rank two matroids and that decomposability of F (M)
for a rank two matroid M implies decomposability of Q(M), as stated in the
following theorem.
Theorem 6.2. Let λ ⊢ n with ℓ(λ) ≥ 3, and let J be a multiset of partitions of
n, all of length three or more, such that
F ([Mλ]) =
F ([Mµ]), (16)
where [Mτ ] denotes the isomorphism class of (loopless) rank two matroids on n
elements indexed by the partition τ . Then, taking the set of standard basis vec-
tors of Rn as the common ground set, there exists a collection of representative
matroids on this ground set, Mλ ∈ [Mλ] and Mµ ∈ [Mµ] for all µ ∈ J which
form a decomposition of matroid base polytopes
Q(Mλ) =
Q(Mµ). (17)
Before the main proof of this theorem, we establish some preliminary results.
We begin by developing a formula for F (Mλ) in terms of the new basis {Nα}.
We define the following quasisymmetric functions in
V n2 = span{Nα : |α| = n, r(α) = 2}.
For all 1 ≤ k ≤ n− 1 let
T nk :=
N(2,n−2) +
k − 1
N(1,j,1,n−2−j), (18)
where we understand N(1,j,1,n−2−j) to be N(1,n−2,1) when j = n − 2. We also
define quasisymmetric functions
Unk := k(n− k)T
Note that each of the sets {T nk } and {U
k } forms a basis for the subspace V
where we consider QSym to have rational coefficients.
Lemma 6.3. Let Mλ be the rank two matroid on n elements indexed by the
partition λ = (λ1, . . . , λm). Then
F (Mλ) =
Unλi . (19)
Proof. We write c(λi) to denote the parallelism class of elements in Mλ cor-
responding to the part λi. A typical base B ∈ B(Mλ) is B = {ei, ej}, where
ei ∈ c(λi) and ej ∈ c(λj) are in distinct parallelism classes. The Hasse diagram
of PB has two minimal elements, ei and ej. There are edges from ei to all
elements of the cobase Bc = E(Mλ) − B except for the λj − 1 elements which
are in the same parallelism class c(λj) as ej. Similarly, there are edges from ej
to all elements of the cobase except for the λi − 1 elements which are in the
same parallelism class c(λi) as ei.
We can analyze F (PB) as in the proof of Lemma 5.1 by applying a strict
labeling γ : E(Mλ) → [n] such that γ(ei) = n, γ(ej) = n − 1, and the cobase
elements are arbitrarily labeled with {1, 2, . . . , n − 2}. We take T = {B,Bc}
to be our antichain-inducing partition of (PB , γ). There is one induced ordered
partition (of [n]) of type (2, n − 2), namely K = (B,Bc), classifying one set
of permutations in L(PB , γ), and thus contributing one N(2,n−2) term to the
expansion of F (PB). For each 1 ≤ k < λj , and for each k-set A ⊂ B
c(λj), there is an induced ordered partition K = ({ej}, A, {ei}, B
c −A) of type
(1, k, 1, n − 2 − k) contributing a term N(1,k,1,n−2−k) to the expansion. Thus
there are
such terms N(1,k,1,n−2−k) corresponding to ordered partitions
K of type (1, k, 1, n−2−k) withK1 = {ej}. Likewise there are
such terms
N(1,k,1,n−2−k) corresponding to ordered partitions K of type (1, k, 1, n− 2− k)
with K1 = {ei}. All the Nα ∈ N
2 are of one of these types, and we know that
the terms of F (PB) must lie in V
2 , so these are the only types appearing in the
expansion for F (PB). There can be no other terms than these due to the order
relations in PB. Thus
F (PB) = N(2,n−2) +
λi − 1
λj − 1
N(1,k,1,n−2−k). (20)
Using Equation (18), we can rewrite this as
F (PB) = T
+ T nλj .
Finally, there are λiλj such bases B ∈ c(λi)× c(λj). Summing over all pairs of
parallelism classes of the matroid yields the formula
F (Mλ) =
λi(n− λi)T
Unλi .
Next we develop a similar formula for F (Mλ) in QSymn/m
2. Our starting
point is the following corollary.
Corollary 6.4. Let a and b be positive integers such that a+ b = n. Then
ab ·N(1,a−1) ·N(1,b−1) = U
a + U
Proof. Let λ = (a, b). ThenMλ = U1,a⊕U1,b, where U1,m is the uniform matroid
of rank one onm elements. As discussed in Example 5.3, F (U1,m) = mN(1,m−1).
Therefore by the Hopf algebra morphism, we have
F (Mλ) = F (U1,a) · F (U1,b) = aN(1,a−1) · bN(1,b−1).
On the other hand, by Lemma 6.3 we have F (Mλ) = U
a + U
b . Equating right
hand sides yields the desired formula.
Since QSym with respect to its product structure is graded by composition
rank as well as degree, the vector subspace V n2 ∩m
2 is spanned by the vectors
{N(1,a−1) ·N(1,b−1) : a+ b = n}.
Thus a basis for V n2 ∩ m
2 is {Unk + U
n−k : 1 ≤ k ≤
}. For expressing our
formula for F (Mλ), we find it convenient to define vectors U
k as follows:
Unk =
Unk if k <
0 if k = n
−Unn−k if k >
Thus the set {Unk : 1 ≤ k <
} forms a basis (over rational coefficients) for
V n2 /m
2. We have the immediate corollary of Lemma 6.3:
Corollary 6.5. Let Mλ be the rank two matroid on n elements indexed by the
partition λ = (λ1, . . . , λm). Then
F (Mλ) =
Unλi . (22)
The next proposition provides a necessary step for the main result, but may be
of interest in its own right.
Proposition 6.6. Let M2 be the set of matroid isomorphism classes (including
those with loops) of rank two matroids. Let Matc be the vector subspace of Mat
spanned by the isomorphism classes of connected matroids, and let M2c be the
set of matroid isomorphism classes of connected rank two matroids. Then the
algebra morphism F : Mat → QSym is injective when restricted to M2, and the
induced quotient map of vector spaces F : Matc → QSym/m
2 is injective when
restricted to M2c.
Proof. We show that we can recover the isomorphism class of the matroid from
its respective function. Suppose we are given F (M) for a rank two matroid M .
We know that F (M) is a non-zero homogeneous function of degree n = |E(M)|,
and so we recover the size of the ground set. Clearly, n ≥ 2.
It is possible that M may have loops or coloops. By Lemma 5.4 we can
recover the total number s of loops and coloops of M from F (M) by Equation
(13). If s = n, then M consists of two coloops and n − 2 loops. Otherwise
s ≤ n− 2, and we may factor F (M) as
F (M) = N(s) · F (M
where (s) is the one-part composition of s, and M ′ is the matroid obtained
from M by removing all loops and coloops. If now F (M ′) ∈ V n−s1 , we have
M ′ ∼= U1,n−s and M has one coloop and s− 1 loops. Otherwise M has s loops,
no coloops, F (M ′) ∈ V n−s2 , and M
′ is a loopless rank two matroid on n − s
elements.
So now without loss of generality, we assume that M has no loops or coloops
and thus is isomorphic to Mλ for some λ ⊢ n. We expand F (M) as
F (M) =
k . (23)
This expansion can be determined since the set of {Unk } form a basis of V
2 . Per
Lemma 6.3, for each k, the coefficient tk is the number of parts of λ that are
equal to k, and so we recover λ from F (Mλ).
The argument for recoveringM from F (M) for a connected rank two matroid
M is similar. Since M is connected, it has no loops or coloops, and so again
M is isomorphic to Mλ for some λ ⊢ n with ℓ(λ) ≥ 3, where n is the degree of
F (M). We expand
F (M) =
⌊(n−1)/2⌋∑
k . (24)
This expansion can be determined since the set {Unk : 1 ≤ k <
} forms a basis
for the subspace V n2 /m
2. Note that λ cannot have a pair of parts with values
k and n − k. Using this fact together with Corollary 6.5, we see that if the
coefficient tk is nonnegative, then λ has exactly tk parts with value k. From
this we can determine all the parts of λ which are < n
. Since λ cannot have
more than one part ≥ n
, this allows us to determine the remaining part of λ, if
Proof of Theorem 6.2. We write A⊔B to denote the disjoint union of multisets
A and B. Note that a partition may be considered to be a multiset of integers.
We fix n > 2 and λ ⊢ n with ℓ(λ) ≥ 3, and proceed by induction on |J |. The
base case |J | = 1 follows from Proposition 6.6. So we assume that the statement
holds for |J | < m for some fixed m > 1. Suppose now that
F ([Mλ]) =
F ([Mµ]), (25)
where |J | = m. Say that a pair of elements µ, ν ∈ J are matching if for some
value 1 < k < n − 1 we have k ∈ µ and n − k ∈ ν. If µ, ν are a matching
pair, then we can apply Proposition 6.1 to form a new relation of type (25) by
replacing J with J ′ = (J − {µ, ν}) ⊔ {τ}, where τ = (µ ⊔ ν) − {k, n − k}. At
the same time, Proposition 6.1 tells us that we also have a decomposition of
base polytopes Q(Mτ ) = Q(Mµ) ∪ Q(Mν). Since |J
′| < m, we can apply our
induction hypothesis, and we are done. It remains to show that there exists a
matching pair in J .
For a partition τ ⊢ n, define the multiset g(τ) = {τi : τi > 1, τi 6=
Define multisets L = g(λ) and R =
µ∈J g(µ). Per Corollary 6.5 we expand
F (Mλ) =
ℓ(λ)∑
Unλi ,
and we similarly expand each F (Mµ) on the right hand side of (25). Since the
set {Unk : 1 ≤ k <
} forms a basis for V n2 /m
2, with Unk = −U
n−k, we conclude
that L ⊆ R and that the parts in R − L can be matched into complementary
pairs of the form (k, n− k). Since no partition in J can contain both parts of a
complementary pair, there exists a matching pair in J if R− L 6= ∅.
We are assuming that |J | ≥ 2, and that R and L contain all the parts not
equal to n
or 1 on the respective sides of (25). The parts equal to 1 on both sides
must match since all of the partitions have at least three parts and hence no
part equal to (n− 1). The only way to have R−L = ∅ is if there exist µ, ν ∈ J
each of which contains a part equal to n
, in which case they are matching.
Thus in all cases, there exists a matching pair µ, ν ∈ J , and the result follows
by induction.
Now we can give an affirmative answer to [3, Question 7.10].
Corollary 6.7. For a fixed n, the Hilbert basis for the semigroup in QSym/m2
generated by the set S = {F (Mλ) : λ ⊢ n, ℓ(λ) ≥ 3} is indexed by those Mλ for
which ℓ(λ) = 3.
Proof. Let T = {F (Mλ) : λ ⊢ n, ℓ(λ) = 3}. It follows from Proposition 6.1
that for ℓ(λ) > 3, F (Mλ) is decomposable into a sum
µ F (Mµ), where for all
µ, ℓ(µ) < ℓ(λ). Hence T generates the same semigroup as S. As noted in [3,
Section 7], if ℓ(λ) = 3, then Q(Mλ) is indecomposable. Theorem 6.2 then implies
that F (Mλ) must also be indecomposable, so T is the minimal generating set,
i.e. the Hilbert basis of the semigroup. By Proposition 6.6, distinct indexing
partitions yield distinct images, establishing the claim.
7 Additional observations
In this section we discuss additional aspects of our new basis, especially regard-
ing the expansion of F (M) for a matroid M .
7.1 Matroid duality, loops, and coloops
Although we describe the basis {Nα} as ‘matroid-friendly’, things are slightly
less friendly when considering matroid duality in the presence of coloops. This
is due to the fact, mentioned in Section 5.1, that the mapping F : Mat → QSym
factors through the quotient Mat → Mat/∼ → QSym, where ∼ denotes loop-
coloop equivalence.
For example, a fact proved in [3] is that, for any matroid M , in terms of the
monomial basis for QSym the following relationship holds:
F (M) =
α =⇒ F (M∗) =
α∗ . (26)
where α∗ is the reversal of α, obtained by writing the parts of α in reverse order.
If M be is a matroid of rank r on n elements having no loops or coloops, then
we have the analogous relationship
F (M) =
mαNα =⇒ F (M
mαNα∗ . (27)
However this relationship breaks down if M has loops or coloops.
We showed in Theorem 5.2 that if M is a loopless matroid of rank r on n
elements, then F (M) ∈ V nr . More generally, if M is of rank r on n elements
and has exactly ℓ loops, then F (M) ∈ V nr+ℓ. Thus if M has exactly c coloops,
then we have the duality relationship
F (M) ∈ V nr =⇒ F (M
∗) ∈ V nn−r+c.
7.2 Comultiplication
The matroid Hopf algebra is graded by matroid rank as well as ground set size.
Let Wnr be the subspace of Mat spanned by the classes of matroids of rank r
on n elements. Then Wnr ·W
s ⊂ W
r+s . For any matroid M and A ⊆ E(M),
r(M) = r(M |A) + r(M/A). So comultiplication in Mat also respects these
gradings. (For general background on Hopf algebras, see [8].) That is,
∆Wnr ⊆
a+b=n,
s+t=r
W as ⊗W
. (28)
One might wonder whether the standard comultiplication of the Hopf algebra
QSym respects the grading by the rank function for our new basis, that is,
whether
∆V nr ⊆
a+b=n,
s+t=r
V as ⊗ V
. (29)
This is not the case. For the simplest example, consider n = 2 and r = 1. We
have N 00 = {N0} = {1} and N
1 = {N11} = {x
11}. Note that there is no Nm0
(or rather, Nm0 = ∅) for m > 0. The basis vectors corresponding to the right
hand side of (29) are
N11 ⊗N0 = x
11 ⊗ 1, and N0 ⊗N11 = 1⊗ x
However,
∆N11 = ∆x
11 = x11 ⊗ 1 + x1 ⊗ x1 + 1⊗ x11,
which clearly does not lie in the span of the above vectors.
The failure of the comultiplication to respect the rank grading can be viewed
as another artifact of loop-coloop equivalence under the morphism F , as evi-
denced by the fact that the rank grading is respected by comultiplication in the
quotient space corresponding to matroids with neither loops nor coloops. Let
J ⊂ QSym be the ideal generated by degree one elements, i.e. by {N1} = {x
Similarly, let I ⊂ Mat be the ideal generated by degree one elements, i.e. by
{[U0,1], [U1,1]}. Both I and J are Hopf ideals in their respective Hopf algebras,
hence Mat/I and QSym/J (with their naturally induced comultiplications) are
Hopf algebras. Moreover, I = F−1(J), so F : Mat → QSym induces a sur-
jective Hopf algebra morphism Mat/I → QSym/J . Note that a natural basis
for Mat/I is the set of all matroid isomorphism classes that have neither loops
nor coloops, while a natural basis for QSym/J is {Nα : ℓ(α) is even}. Taking
appropriate images under the quotient map, the relation (29) holds in QSym/J .
The duality formula (27) also holds in QSym/J .
7.3 Comparison with other QSym bases
In the course of their proof in Section 10 of [3], the authors introduce two new
Z-bases for QSym. They also compare their bases to another Z-basis due to
Stanley [19].
Our new basis is different from these three, as evidenced by the report by
those authors that all three of these bases have some negative structure con-
stants, whereas our new basis does not. However, of the three, ours most closely
resembles that of Stanley. Stanley’s basis element indexed by a composition
α = (α1, . . . , αm) is F (P ) where, as with our basis, P = A1 ⊕ · · · ⊕ Am, is
the ordered sum of antichains A1, · · · , Am on α1, . . . , αm elements respectively.
However, Stanley applies a natural labeling to P , whereas we apply an alter-
nating labeling to the ranks in the poset for our basis.
7.4 Surjectivity of the Hopf algebra morphism
Billera, Jia, and Reiner devote [3, Section 10] to showing that the morphism
F : Mat → QSym is surjective over rational coefficients. In this subsection we
sketch one way to shorten their proof somewhat using our new basis. The reader
will need to consult [3] to have the full context.
Define an ordering on compositions as follows. To each composition α we
assign the binary word b(α) that begins with α1 zeros followed by α2 ones, then
α3 zeros, then α4 ones, etc. We then linearly order compositions according to
their binary words: α < β if b(α) <lex b(β).
In their proof, Billera, Jia, and Reiner make use of a novel basis for the
quasisymmetric functions based on a family of posets {Rσ} of maximum rank
one, indexed by binary words σ ∈ 0{0, 1}n−1, where n is the number of elements
of the poset. We may equivalently index them using compositions of weight n,
declaring Rα = Rb(α). We refer the reader to [3, Section 10] for the definition of
this basis. Billera, Jia, and Reiner show, through a series of theorems that the
set of {F (Rα)}, where the posets are strictly labeled, forms a Z-basis for QSym.
Using our basis, one can show this more directly. We know from Lemma 5.1
that all β ∈ supp(F (Rα)) are of rank r(α) and weight |α|. It is not too hard
to show that the largest β ∈ supp(F (Rα)) with respect to the above ordering
is precisely α, and that the coefficient of Nα in the expansion of F (Rα) is one.
Thus an array giving the expansion of all the {F (Rα)} of a fixed set size |α| = n
in terms of {Nα} with rows and columns suitably ordered is unitriangular.
Acknowledgments
I wish to thank the referees for their helpful comments. I extend many thanks
to Isabella Novik and Sara Billey for their encouragement and their many hours
of proofreading and advice through several drafts of this manuscript. Thanks
also go to Vic Reiner and Lou Billera for their clarification of parts of their
paper and their helpful comments on this work. Special thanks go to Isabella
Novik for bringing the paper of Billera, Jia, and Reiner to my attention, and
to Vic Reiner for pointing me specifically to [3, Question 7.10], which was the
starting point for my investigation.
While working on this project the author was partially supported by a gradu-
ate fellowship from VIGRE NSF Grant DMS-0354131. The seeds of this project
were planted at the ICM in Madrid, 2006. The trip there was made possible by
funds from NSF Grant DMS-9983797.
References
[1] M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf al-
gebras and generalized Dehn-Sommerville relations., Compos. Math., 142
(2006), pp. 1–30.
[2] A. Barvinok, A Course in Convexity., Graduate Studies in Mathematics.
54. Providence, RI: American Mathematical Society., 2002.
[3] L. J. Billera, N. Jia, and V. Reiner, A quasisymmetric function for
matroids, arXiv:math.CO/0606646.
[4] H. Crapo and W. Schmitt, Primitive elements in the matroid-minor
Hopf algebra, arXiv:math.CO/0511033.
[5] H. Crapo and W. Schmitt, A free subalgebra of the algebra of matroids.,
Eur. J. Comb., 26 (2005), pp. 1066–1085.
[6] , A unique factorization theorem for matroids., J. Comb. Theory, Ser.
A, 112 (2005), pp. 222–249.
[7] , The free product of matroids., Eur. J. Comb., 26 (2005), pp. 1060–
1065.
[8] S. Dăscălescu, C. Năstăsescu, and c. Raianu, Hopf Algebras. An
Introduction., Pure and Applied Mathematics, Marcel Dekker. 235. New
York, NY: Marcel Dekker., 2001.
[9] I. Gel’fand and V. Serganova, Combinatorial geometries and torus
strata on homogeneous compact manifolds., Russ. Math. Surv., 42 (1987),
pp. 133–168.
[10] I. M. Gessel, Multipartite P-partitions and inner products of skew Schur
functions. Combinatorics and algebra, Proc. Conf., Boulder/Colo. 1983,
Contemp. Math. 34, 289-301, 1984.
[11] M. Kapranov, Chow quotients of Grassmannians. I. Gelfand, Sergej (ed.)
et al., I. M. Gelfand Seminar. Providence, RI: American Mathematical
Society. Adv. Sov. Math. 16(2), 29-110, 1993.
[12] L. Lafforgue, Pavages des simplexes, schémas de graphes recollés et com-
pactification des PGLn+1r /PGLr., Invent. Math., 136 (1999), pp. 233–271.
[13] , Chirurgie des grassmanniennes., CRM Monograph Series. 19. Prov-
idence, RI: American Mathematical Society., 2003.
[14] J. G. Oxley, Matroid Theory., Oxford Graduate Texts in Mathematics 3.
Oxford: Oxford University Press., 2006.
[15] W. R. Schmitt, Incidence Hopf algebras., J. Pure Appl. Algebra, 96
(1994), pp. 299–330.
[16] D. E. Speyer, A matroid invariant via the K-theory of the Grassmannian,
arXiv:math.AG/0603551.
[17] R. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math.
Soc., (1972). American Mathematical Society, Providence, RI.
[18] , Enumerative Combinatorics, vol. 2, Cambridge University Press,
Cambridge, MA, 1999.
[19] R. P. Stanley, The descent set and connectivity set of a permutation., J.
Integer Sequences, (2005).
	Introduction
	Preliminaries
	Compositions
	Well-known QSym bases
	Posets and P-partitions
	The new basis
	Additional facts regarding F(P)
	Ordered partitions
	Unordered partitions of X P
	Structure constants for the new basis
	Matroids
	The quasisymmetric function of a matroid
	Expanding F(M) in the {N} basis
	Matroid base polytopes
	Matroid base polytopes and their decompositions
	Results for rank two matroids
	Additional observations
	Matroid duality, loops, and coloops
	Comultiplication
	Comparison with other QSym bases
	Surjectivity of the Hopf algebra morphism
