CATEGORICAL INVARIANTS OF GRAPHS AND MATROIDS
by
DANE MIYATA
A DISSERTATION
Presented to the Department of Mathematics
and the Division of Graduate Studies of the University of Oregon
in partial fulfillment of the requirements
for the degree of
Doctor of Philosophy
June 2023
DISSERTATION APPROVAL PAGE
Student: Dane Miyata
Title: Categorical Invariants of Graphs and Matroids
This dissertation has been accepted and approved in partial fulfillment of the
requirements for the Doctor of Philosophy degree in the Department of Mathematics
by:
Nicholas Proudfoot Chair
Nicolas Addington Core Member
Ben Elias Core Member
Patricia Hersh Core Member
Donald Morgan Institutional Representative
and
Krista Chronister Vice Provost for Graduate Studies
Original approval signatures are on file with the University of Oregon Division of
Graduate Studies.
Degree awarded June 2023
ii
© 2023 Dane Miyata
This work is licensed under a Creative Commons Attribution License
iii
DISSERTATION ABSTRACT
Dane Miyata
Doctor of Philosophy
Department of Mathematics
June 2023
Title: Categorical Invariants of Graphs and Matroids
Graphs and matroids are two of the most important objects in combinatorics.
We study invariants of graphs and matroids that behave well with respect to
certain morphisms by realizing these invariants as functors from a category of
graphs (resp. matroids).
For graphs, we study invariants that respect deletions and contractions of
edges. For an integer g > 0, we define a category of Gop¬g of graphs of genus at most
g where morphisms correspond to deletions and contractions. We prove that this
category is locally Noetherian and show that many graph invariants form finitely
generated modules over the category Gop¬g. This fact allows us to exihibit many
stabilization properties of these invariants. In particular we show that the torsion
that can occur in the homologies of the unordered configuration space of n points
in a graph and the matching complex of a graph are uniform over the entire family
of graphs with genus g.
For matroids, we study valuative invariants of matroids. Given a matroid,
one can define a corresponding polytope called the base polytope. Often, the base
polytope of a matroid can be decomposed into a cell complex made up of base
iv
polytopes of other matroids. A valuative invariant of matroids is an invariant that
respects these polytope decompositions. We define a category M∧id of matroids
whose morphisms correspond to containment of base polytopes. We then define the
notion of a categorical matroid invariant which categorifies the notion of a valuative
invariant. Finally, we prove that the functor sending a matroid to its Orlik-Solomon
algebra is a categorical valuative invariant. This allows us to derive relations among
the Orlik-Solomon algebras of a matroid and matroids that decompose its base
polytope viewed as representations of any group Γ whose action is compatible with
the polytope decomposition.
This dissertation includes previously unpublished co-authored material.
v
CURRICULUM VITAE
NAME OF AUTHOR: Dane Miyata
GRADUATE AND UNDERGRADUATE SCHOOLS ATTENDED:
University of Oregon, Eugene, OR
Willamette University, Salem, OR
DEGREES AWARDED:
Doctor of Philosophy, Mathematics, 2023, University of Oregon
Bachelor of Arts, Mathematics, 2017, Willamette University
PROFESSIONAL EXPERIENCE:
Graduate Employee, University of Oregon, 2017-2023
PUBLICATIONS:
Sanjana Agarwal, Maya Banks, Nir Gadish, and Dane Miyata. Deletion and
contraction in configuration spaces of graphs, Algebr. Geom. Topol. 21
(2021), no. 7, 3663–3674.
Rebecca Garcia, Luis David Garcia Puente, Ryan Kruse, Jessica Liu, Dane
Miyata, Ethan Petersen, Kaitlyn Phillipson, and Anne Shiu, Gröbner bases
of neural ideals, Internat. J. Algebra Comput. 28 (2018), no. 4, 553–571.
Derek Hanely, Jeremy L. Martin, Daniel McGinnis, Dane Miyata, George D.
Nasr, Andrés R. Vindas-Meléndez, and Mei Yin, Ehrhart theory of paving
and panhandle matroids, 2022. (Submitted)
Jacob P. Matherne, Dane Miyata, Nicholas Proudfoot, and Eric Ramos,
Equivariant Log Concavity and Representation Stability, Int. Math. Res.
Not. IMRN (2023), no. 5, 3885–3906.
Dane Miyata and Eric Ramos. The graph minor theorem in topological
combinatorics, 2023. (Submitted)
vi
ACKNOWLEDGEMENTS
First, I would like to thank my advisor, Nicholas Proudfoot, whose instruction
and guidance have been invaluable. I am also grateful to Eric Ramos for his
mentorship during my early years as a graduate student. I would also like to
thank Lorenzo Vecchi for being a wonderful collaborator. Without these three,
this dissertation would not exist. To my undergraduate professors, thank you
for sparking my interest in mathematics and inspiring me to pursue a PhD in
mathematics. I would also like to thank my friends, family, and my partner Annie,
for their ongoing love and support.
vii
TABLE OF CONTENTS
Chapter Page
I. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1. Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
II. THE CATEGORICAL GRAPH MINOR THEOREM . . . . . . . . . . 11
2.1. Gröbner theory of categories . . . . . . . . . . . . . . . . . . . . 11
2.1.1. Modules over algebras over categories . . . . . . . . . . . . 13
2.1.2. Gröbner pairs . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.3. Gröbner bases . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.4. Quasi-Gröbner pairs . . . . . . . . . . . . . . . . . . . . . 23
2.2. Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1. Defining the graph categories . . . . . . . . . . . . . . . . 25
2.2.2. Edge functors . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.3. Finite generation . . . . . . . . . . . . . . . . . . . . . . . 35
2.3. Homology of configuration spaces of graphs . . . . . . . . . . . . 38
2.3.1. The reduced Świątkowski complex . . . . . . . . . . . . . 39
2.3.2. Finite generation . . . . . . . . . . . . . . . . . . . . . . . 40
2.4. The matching complex and monotone graph properties . . . . . 43
2.4.1. The edge module . . . . . . . . . . . . . . . . . . . . . . . 44
viii
Chapter Page
2.4.2. Finite generation . . . . . . . . . . . . . . . . . . . . . . . 45
2.4.3. Other graph complexes . . . . . . . . . . . . . . . . . . . . 47
2.5. Commutative algebra of graph complexes . . . . . . . . . . . . . 48
2.5.1. Betti numbers . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5.2. Squarefree monomial ideals . . . . . . . . . . . . . . . . . 52
2.6. Linear subspace arrangements of line graph complements . . . . 55
III. CATEGORICAL VALUATIVE INVARIANTS OF MATROIDS . . . . 61
3.1. Background on matroids . . . . . . . . . . . . . . . . . . . . . . 61
3.1.1. Matroid operations . . . . . . . . . . . . . . . . . . . . . . 63
3.2. Matroid polytopes and valuative invariants . . . . . . . . . . . . 63
3.2.1. Matroid polytope decompositions . . . . . . . . . . . . . . 66
3.2.2. Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3. Matroid categories . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3.1. The category M∧id(E) . . . . . . . . . . . . . . . . . . . . 73
3.3.2. The determinant functor . . . . . . . . . . . . . . . . . . . 75
3.3.3. Valuative categorical matroid invariants . . . . . . . . . . 76
3.4. The Orlik–Solomon functor . . . . . . . . . . . . . . . . . . . . 79
3.4.1. The nbc condition . . . . . . . . . . . . . . . . . . . . . . 82
3.5. Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.5.1. Equivariant relaxation . . . . . . . . . . . . . . . . . . . . 88
3.5.2. Relaxing a stressed hyperplane . . . . . . . . . . . . . . . 90
3.5.3. The Vámos matroid . . . . . . . . . . . . . . . . . . . . . 91
ix
Chapter Page
REFERENCES CITED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
x
LIST OF FIGURES
Figure Page
1 The base polytope for the matroid U2,4 forms an octahedron. . . . . . . 65
2 As in Example 3.2.3, the base polytope for the matroid M is given on the
left. The base polytopes for the internal faces of a decomposition of M
are given on the right. Here, the vertices are labeled with the basis that
they correspond to. . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3 The Vámos matroid V8. The five shaded rectangles correspond to the five
circuit hyperplanes of V8. Note, this does not depict the base polytope
of V8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
xi
CHAPTER I
INTRODUCTION
This dissertation includes previously unpublished co-authored material.
Chapter II was written in collaboration with Eric Ramos. Chapter III was written
in collaboration with Nicholas Proudfoot and Lorenzo Vecchi.
In this dissertation, we study invariants of graphs and matroids, two of the
most important objects in combinatorics. We do this categorically by looking at
graph or matroid invariants that are functors from a specific category of graphs or
matroids. In both the graph and the matroid case, working categorically provides
powerful machinery for studying these invariants.
In the graph case, our categorical setup will give us stabilization properties of
various invariants that are uniform for all graphs of genus at most g. In the matroid
case, our categorical setup will give us relations among group representations built
out of matroids and their symmetries.
1.1. Graphs
Throughout the introduction, a graph will refer to an at most one-
dimensional CW complex that is both connected and finite. We say that a graph
G is a minor of a graph G′ if G can be obtained from G′ by a sequence of edge
deletions and contractions. In Chapter II, we study a category G¬g where we have a
morphism of graphs G → G′ whenever G is isomorphic to a minor of G′. A precise
definition of this category is given in 2.2.
Let C be a category and k a Noetherian ring. A C-module over k is a functor
from C to the category of k-modules. Let Repk(C) be the category of C-modules.
1
A C-module M is finitely generated if there is a finitely list of objects {Xi}i in
C, such that M(Xi) is a finitely generated k-module for each i and for any object
X of C, M(X) is generated as a k-module by images of the M(Xi) under maps
coming from morphisms in C. The category Repk(C) is called locally Noetherian
if every submodule of a finitely generated C-module is itself finitely generated.
The theory of quasi-Gröbner categories in [SS17] provides a powerful tool for
proving the category of modules over C is locally Noetherian. In particular they
define what it means for C to be quasi-Gröbner and prove that the if C is quasi-
Gröbner, then Repk(C) is locally Noetherian. This theory along with the results of
[PR19b] allow us to show the following.
Theorem 1.1.1. The category Gop¬g is quasi-Gröbner. Thus, the category of G
op
¬g-
modules is locally Noetherian which means every submodule of a finetely generated
Gop¬g is itself finitely generated.
Remark 1.1.2. In their seminal series of papers, Robertson and Seymour proved,
among many other things, that the minor relation is actually a well-quasi-order
[RS04, RS10]. That is to say, in any infinite collection of graphs, there must be a
pair where one is a minor of the other. We will refer to this as the Graph Minor
Theorem. Theorem 1.1.1 can be seen as a weakened categorical version of this
theorem.
Modules over algebras over categories
In section 2.1 we generalize the Gröbner theory of categories in [SS17]. Let
C be a category and S a functor from C to the category FI of finite sets with
inclusions. There is a natural functor taking an object X in C to the polynomial
2
ring
AS = k[te | e ∈ S(X)].
We define an AS-module to be a C-module M where for each object X of C, M(X)
is a module over the ring AS(X) in a natural way. See 2.1 for a precise definition.
Let Repk(C, S) be the category of AS-modules. We define what it means for a AS-
module to be finitely generated and we say the category Repk(C, S) is locally
Noetherian if every submodule of a finitely generated AS-module is itself finitely
generated. We then define what it means for the (C, S) to be quasi-Gröbner
and prove that if the pair (C, S) is quasi-Gröbner, then the category Repk(C, S)
is locally Noetherian.
In the context of graphs, we have a functor E : Gop¬g → FI taking a graph G to
its set of edges. We prove the following.
Theorem 1.1.3. The pair (Gop¬g, E) is quasi-Gröbner. Thus the category Repk(C, S)
is locally Noetherian for any Noetherian ring k, which means every submodule of a
finitely generated Gop¬g-module is itself finitely generated.
One should think of Theorems 1.1.1 and 1.1.3 as a translation from Robertson
and Seymour’s Graph Minor Theorem in combinatorics, to a algebraic statement
about the representations of the category Gop¬g. We then leverage these theorems
to prove a number of nontrivial stability results in three main applications,
configuration spaces of graphs, simplicial complexes coming from graphs, and
subspace arrangements coming from graphs.
3
Configuration spaces of graphs
For an integer n ­ 0 and a graph G viewed as a 1-dimensional CW-complex,
the unordered configuration space of n points in G is the topological space
Un(G) := {(x1, . . . , xn) ∈ Gn | xi ̸= xj}/Sn.
The homology groups of these spaces have been extensively studied in [Abr00],
[ADCK19], [KP12].
In [ADCK19], though they do not use this language, An, Drummond-Cole,
and Knudsen prove that for any i ­ 0 the assignment of a graph G to the group
⊕
Hi(G) := Hi(Un(G);Z)
n∈N
has the structure of a AE-module. We show the following.
Theorem 1.1.4. The AE-module Hi is finitely generated.
This allows us to conclude, among other things, the following.
Corollary 1.1.5. For any i, g ∈ N there exists an integer ϵi,g such that for any
graph G of genus at most g, and any n ∈ N, the torsion part of Hi(Un(G);Z) is
annihilated by ϵi,g.
Previously, by the work of Ko and Park, it was known that the only torsion
that can appear in H1(Un(G);Z) is 2-torsion [KP12, Corollary 3.6]. Our result
can be seen as a generalization of this result. However, our bound on the torsion
does depend on the genus of the graph and the theory we have developed tells us
nothing about what this bound is, only that the bound is uniform.
4
Homology of the matching complex
For a graph G, a matching of G is a collection of pairwise non-adjacent
edges. The matching complex M(G) of G is the simplicial complex whose
simplices are in bijection with matchings on G. Matching complexes of complete
graphs and complete bipartite graphs have been studied extensively using a wide
variety of techniques including discrete Morse theory. It is notable, however, that
there is relatively little known about the matching complexes of general graphs.
We aim to fill this gap by considering a new perspective on the problem: instead of
focusing on the matching complex M(G) for some particular graph G, we consider
the matching complexes of all graphs of genus at most g at once.
The key observation that allows us to do this is that whenever G is a minor of
G′ there is a natural way to embed the edges of G into those of G′. Moreover, this
embedding preserves the condition that the edges are disjoint, as any ”undoing” of
an edge deletion or contraction can only push things further apart. We therefore
obtain simplicial complex maps M(G) → M(G′) whenever G is a minor of G′,
which induce maps on homology Hi(M(G)) → H (M(G′i )). In particular, for any
fixed i ­ 0, the assignment
G 7→ Hi(M(G))
is a well-defined Gop¬g-module over Z. Using the categorical graph minor theorem, we
will prove the following
Theorem 1.1.6. The Gop¬g-module
G 7→ Hi(M(G);Z)
5
is finitely generated. This implies that there exists an integer ϵi,g, depending only on
i and g, such that the torsion part of Hi(M(G)) is annihilated by ϵi,g, for all graphs
G.
The statement about torsion in the above theorem should be particularly
interesting, as the torsion appearing the homology of the matching complex has
been a subject of considerable intrigue in recent years [SW07] [Jon10b] [Jon10a].
We also note that, by the very general nature of the weak categorical graph
minor theorem, the conclusions of Theorem 1.1.6 will remain true when the
matching complex is replaced by a large variety of graph-based complexes, such
as those discussed in [Jon08]. See Section 2.4 for more on this.
Graphical linear subspace arrangements
To any graph G, one may define a linear subspace arrangement induced by
the edge relation of its vertices. We define the complement of this arrangement in
(Cd)V (G) by Conf(G,Cd). More precisely, we have
Conf(G,Cd) = {(x d V (G)v)v∈V (G) ∈ (C ) | xv ̸= xw if {v, w} is an edge of G}.
For instance, if G = Kn is the complete graph, Conf(G,Cd) is the classical
configuration space of points in Cd. If instead G = Ka,b is the complete bipartite
graph, then one recovers the colored configuration spaces Z̃Da+b as studied by Farb,
Wolfson, and Wood [FWW19]. In this work we will specialize to the family of line
graph complements.
Given a graph G, we write Lc(G) to denote the simple graph whose vertices
are indexed by the edges of G, and whose edges indicate the corresponding edges
in G do not share a vertex. These graphs have been called generalized Kneser
6
graphs by some authors [DMM20], as the usual Kneser graph K(n, 2) is seen to
be Lc(Kn).
The same observation made above tells us that whenever G is a minor of G′,
one obtains a graph embedding
Lc(G) ↪→ Lc(G′).
This embedding induces a ”forgetful” map
Conf(Lc(G′),Cd)→ Conf(Lc(G),Cd),
which when composed with cohomology yields
H i(Conf(Lc(G),Cd))→ H i(Conf(Lc(G′),Cd)).
We then obtain the following.
Theorem 1.1.7. For any fixed i, d, g, the assignment
G 7→ H i(Conf(Lc(G),Cd))
defines a finitely generated Gop¬g-module over Z.
One observes that the complete bipartite graph Ka,b can (essentially) be
realized as the line graph complement of some other graph. In particular, the finite
generation result of Theorem 1.1.7 can be seen as a generalization of some results in
[FWW19] (see Theorem 2.6.4).
7
1.2. Matroids
A matroid is an object that abstracts the notion of linear independence.
Precisely, a matroid is a pair M = (E,B) where B is a collection of subsets of E
satisfying the following
(B1) B ̸= ∅
(B2) If B1, B2 ∈ B and x ∈ B1 \ B2, then there exists y ∈ B2 \ B1 such that
(B1 \ {x}) ∪ {y} ∈ B.
The set E is called the ground set of M and elements of B are called bases. Given
a matroid M = (E,B), one can define its base polytope as the convex hull of the
indicator vectors of it bases in RE.
A decomposition of M is a decomposition of its base polytope PM as a
CW-complex where the closed cells of the complex are base polytopes of other
matroids. See Example 3.2.3 and Figure 1. A valuative invariant of matroids,
is an invariant taking values in an abelian group that is compatible with all such
decompositions. See Section 3.2 for a precise definition.
Said another way, if E is a finite set and Mat(E) is the free abelian group
generated by matroids on E, then there is a homomorphism from Mat(E) to
Z-valued functions on RE taking a matroid M to the indicator vector of its
base polytope. The kernel I(E) of this homomorphism is generated by elements
corresponding to decompositions of matroids. Thus, a matroid invariant thought of
as a homomorphism from Mat(E) to an abelian group is valuative if it descends to
the quotient Mat(E)/I(E).
A number of interesting matroid invariants turn out to be valuative. For
example, the Tutte polynomial and characteristic polynomial [Spe08, Lemma
8
6.4], the Kazhdan-Lusztig polynomial [AS23, Theorem 8.8], and Eur’s volume
polynomial [Eur20, Proposition 4.6] just to name a few.
In Chapter III we define a category M∧id(E) whose objects are matroids on
E where we have a morphism M → M ′ whenever the polytope PM contains the
polytope PM ′ . See 3.3 for a precise definition. A categorical matroid invariant,
is a functor from M∧id(E) to the category of finite dimensional (graded) vector
spaces over Q. This induces a functor from the homotopy category of bounded
chain complexes Kid(E) of M∧id(E). The Grothendieck group of Kid(E) is the
group Mat(E) so in this way a categorical matroid invariant categorifies the
induced matroid invariant on Grothendieck groups. We then define what it means
for a categorical matroid invariant to be valuative and we see that the matroid
invariant categorified by a valuative categorical invariant must itself be valuative in
the non-categorical sense.
The benefit of working categorically, is that if Φ is a categorical valuative
invariant that is equivariant with respect to permutations on E and we have a
group Γ acting on the ground set E such that Γ preserves a decomposition of a
matroid, then we will obtain relations among the Φ(M) for M in the decomposition
viewed as Γ-representations.
The Orlik-Solomon algebra of a matroid
Our main application of the theory of valuative categorical invariants of
matroids will be the Orlik-Solomon algebra. Let M be a matroid on the ground set
E. The Orlik-Solomon algebra of M denoted OS(M) is a quotient of the exterior
algebra of QE whose generators correspond to circuits of the matroid. Namely, the
subsets of E that are not contained in a basis of M . The Orlik-Solomon algebra
9
of a matroid is a graded algebra and the dimensions of its graded pieces are equal
(modulo signs) to the coefficients of the characteristic polynomial of the matroid.
Furthermore, whenever PM contains PM ′ , we obtain a natural map of algebras
OS(M) → OS(M ′). In this way OS can be viewed as a functor from the category
M∧id(E) to finite dimensional graded vector spaces over Q. Thus OS is a categorical
invariant of matroids. In Section 3.4 we will prove the following.
Theorem 1.2.1. OS is a categorical valuative invariant.
Then in Section 3.5 we use the fact that OS is valuative to obtain relations
among OS(M) as Γ-representations for groups Γ acting on E. We look at specific a
family of matroid decompositions in Subsection 3.2.2 coming from the operation of
relaxation of a stressed flat introduced by Ferroni and Schröter in [FS]. Then,
in 3.5 we obtain the following explicit relations among the Sn-representations
OS(M) for matroids M involved in the operation of relaxation of a stressed
hyperplane.
Theorem 1.2.2. Let M be a matroid equipped with an action of the group Γ. Let
H be a stressed hyperplane of M , and let M̃ be the matroid obtained from M by
relaxing γH for all γ ∈ Γ. Then
( ) ( )
OS(M̃) = OS(M) + IndΓ Sh k−1Γ ResΓ ∧ V[h−1,1] ⊗ Q[1− k]⊕Q[−k]H H
as virtual graded representations of Γ.
In this way, we see that the theory of valuative categorical matroid invariants
provides a very powerful tool for studying matroid invariants equivariantly with
respect to group actions that preserve certain matroid polytope decompositions.
10
CHAPTER II
THE CATEGORICAL GRAPH MINOR THEOREM
This chapter was written in collaboration with Eric Ramos.
2.1. Gröbner theory of categories
Let C be an essentially small category and k a ring. A C-module over k is
a functor from C to the category of k-modules. Let Repk(C) be the category of
C-modules over k where a morphism of C-modules is a natural transformation.
The category Repk(C) is abelian. Let M be a C-module. A submodule of M
is a C-module M′ such that for each object X of C, M′(X) is a k-submodule of
M(X) and for any morphism ϕ : X → Y in C, M′(ϕ) is the restriction of
M(ϕ) to M′(X). Equivalently, M′ is a submodule of M when there is a natural
transformation M′ to M whose components are inclusions of k-modules. If x ∈
M(X) for some object X of C, we say x is an element of M or that M contains
x. The C-module M is finitely generated if there exist finitely many elements
x1, . . . , xr of M such that the only submodule of M containing x1, . . . , xr is M
itself. In this case, we say that x1, . . . , xr generate M. If every submodule of M is
finitely generated, then M is said to be Noetherian. If every finitely generated
module is Noetherian, the category Repk(C) is said to be locally Noetherian.
Sam and Snowden have developed powerful machinery for proving that module
categories are locally Noetherian which we summarize below.
Given an object X of C, let Cx be the set of equivalence classes of morphisms
out of X where ϕ ∈ HomC(X, Y ) is equivalent to ψ ∈ HomC(X,Z) if there exists an
isomorphism ρ ∈ HomC(Y, Z) such that ρ ◦ ϕ = ψ. There is a natural quasi-order
11
¬ on CX where ϕ ¬ ψ if and only if there exists a morphism ρ ∈ HomC(Y, Z) such
that ρ ◦ ϕ = ψ. Consider the following two conditions for the category C.
– Property (G1): For every object X of C there exists a linear order ≺ on CX
preserved under post composition. That is to say, given ϕ1, ϕ2 ∈ HomC(X, Y ),
if ϕ1 ≺ ϕ2, then ρ ◦ ϕ1 ≺ ρ ◦ ϕ2 for any ρ ∈ HomC(Y, Z).
– Property (G2): The quasi-order ¬ is a well-quasi-order on CX . Namely,
for any infinite sequence ϕ1, ϕ2, ϕ3, . . . of elements of CX , there exists a pair of
indices i < j such that ϕi ¬ ϕj.
Note, the order ≺ in property (G1) is independent from the order ¬. The category
C is directed if there are no nontrivial endomorphisms. The category C is called
Gröbner if C is a directed category and satisfies properties (G1) and (G2).
Let C and D be categories and Φ : D → C a functor. The functor Φ is
said to satisfy property (F) if for any object X of C there exist finitely many
(not necessarily distinct) objects Y1, . . . , Yn of D along with a morphism ϕi ∈
HomC(X,Φ(Yi)) for each i, such that for any object Y of D and any morphism
ϕ ∈ HomC(X,Φ(Y )), there exists a morphism ψ ∈ HomD(Yi, Y ) such that
ϕ = Φ(ψ) ◦ ϕi. The category C is said to be quasi-Gröbner if there exists a
Gröbner category D and a functor Φ : D → C satisfying property (F). Note
that any Gröbner category is necessarily quasi-Gröbner since the identity functor
satisfies property (F).
Theorem 2.1.1. [SS17, Theorem 1.1.3] If C is a quasi-Gröbner category and k is a
Noetherian commutative ring, then Repk(C) is locally Noetherian.
12
2.1.1. Modules over algebras over categories
Let FI be the category of finite sets with injections. Let C be a category
equipped with a functor S : C → FI and let k be a commutative ring. There is a
natural functor from C to k-algebras taking an object X to the polynomial ring
AS(X) := k[te | e ∈ S(X)].
Let us define the category Repk(C, S) to be the category whose objects are C-
modules M such that M(X) is a module over the k-algebra AS(X) for each X in a
natural way. Concretely, for any morphisms ϕ̃ ∈ HomC(X̃,X) and ϕ ∈ HomC(X, Y )
and any a ∈ AS(X̃), the following diagram commutes
M M(ϕ)(X) M(Y )
AS(ϕ)(a) AS(ϕ◦ϕ̃)(a)
M(X) M(Y )
M(ϕ)
where the vertical arrows are given by multiplication by the indicated element. We
will refer to an object of Repk(C, S) as an AS-module. Note that the category
Repk(C, S) is abelian.
For each graph G, AE(G) is a graded k-algebra where te is in degree 1 for
each edge e ∈ E(G). A graded AE-module M is an AE-module such that M(G)
is a graded AE(G)-module and for any for any minor morphism ϕ : G → G′, the
image under M(ϕ) of the degree i part of M(G′) is contained in the degree i part
of M(G). For AS-modules M and M′ we say that M′ is a submodule of M if,
when viewed as C-modules, M′ is a submodule of M. An AS-module M is called
finitely generated if there exist finitely many elements x1, . . . , xr ∈ M such that
the only submodule of M containing x1, . . . , xr is M itself. In this case x1, . . . , xr
13
generateM. If every submodule of M is finitely generated, then M is said to be
Noetherian. If every finitely generated AS-module is Noetherian, the category
Repk(C, S) is said to be locally Noetherian. Now, we outline some basic facts
about finitely generated AS-modules and Noetherian AS-modules, the proofs of
which are completely standard. Let C be a category, S : C → FI a functor, and
k a commutative ring. For any object X of C, define the principal projective
PSX ∈ Repk(C, S) to be the module that takes an object X ′ to the free AS(X ′)-
module spanned by the set HomC(X,X ′), with maps defined via composition.
Lemma 2.1.2. A module M ∈ Repk(C, S) is finitely generated if and only if there
exists a surjection ⊕r
PSX ↠Mi
i=1
for some list of (not necessarily distinct) objects X1, . . . , Xr of C.
Proof. Suppose that X1, . . . , Xr are objects of C and xi ∈ M(Xi) for all i. These
classes generate M if and only if the map
⊕r
PSX →Mi
i=1
taking id SX ∈ P (X ) to x is surjective.i Xi i i
Lemma 2.1.3. A module M is Noetherian if and only if every ascending chain of
submodules of M eventually stabilizes.
Proof. Suppose that M is Noe⋃therian and (Ni | i ∈ N) is an ascending chain of
submodules of M. Let N := i∈NNi ⊆ M. Since M is Noetherian, N is finitely
generated. If we choose i large enough so that Ni contains all of the finitely many
generators of N , then we have Nj = N for all j ­ i.
14
Conversely, suppose that M has a submodule N ⊆ M that is not finitely
generated. We will define an ascending chain of finitely generated submodules (Ni |
i ∈ N) as follows. Let N0 = 0. Once we have defined Ni, the fact that Ni is finitely
generated means that Ni ⊊ N , so we may choose an object Xi of C such that we
have xi ∈ N (Xi) \ Ni(Xi). Then, define Ni+1 to be the smallest submodule of N
containing both Ni and xi. This chain of submodules clearly does not stabilize.
Lemma 2.1.4. Suppose that 0 →M′ →M →M′′ → 0 is short exact sequence in
Repk(C, S). Then M is Noetherian if and only if both M′ and M′′ are Noetherian.
Proof. If M is Noetherian, then M′ is Noetherian by definition. If N ′′ ⊂ M′′ is a
submodule, let N ⊆ M be the preimage of N ′′ in M. Since M is Noetherian, N is
finitely generated, thus so is N ′′ by Lemma 2.1.2.
Conversely, suppose that both M′ and M′′ are Noetherian, and let (Ni | i ∈
N) be an ascending chain of submodules of M. For each i, let N ′i := N ′i ∩M and
let N ′′i be the image of Ni in M′′. Since M′ and M′′ are both Noetherian, Lemma
2.1.3 tells us that there is an index n such that, for all i > n, N ′ = N ′i i+1 and
N ′′i = N ′′i+1. We can then conclude that Ni = Ni+1 by applying the Five Lemma to
the following diagram:
0 N ′ N N ′′i i i 0
= =
0 N ′ N N ′′i+1 i+1 i+1 0
Thus M satisfies the ascending chain condition, and is therefore Noetherian by
Lemma 2.1.3.
15
Remark 2.1.5. The notion of a principal projective module of Repk(C) was
defined in [SS17]. Given an object X of C, the principal projective module PX
is the C-module that sends an object X ′ to the free k-module generated by the
set HomC(X,X ′). Note the difference in notion between the principal projective
modules PX in Repk(C) and PSX in Repk(C, S). Furthermore, when working in
Repk(C), the analogues of Lemmas 2.1.2, 2.1.3, and 2.1.4 all hold in this case too.
In the following sections, we build on the work of [SS17] and define what it
means for the pair (C, S) to be Gröbner (resp. quasi-Gröbner) and prove the
following generalization of Theorem 2.1.1.
Theorem 2.1.6. Let C be a category and S : C → FI a functor. If the pair
(C, S) is quasi-Gröbner, then Repk(C, S) is locally Noetherian for any Noetherian
commutative ring k.
Remark 2.1.7. Theorem 2.1.6 is motivated by the work of Nagel and Römer
[NR19]. Though they do not make these definitions in the same generality, they
essentially prove that the pair (FI, id) is quasi-Gröbner, and they use this result to
show that Repk(FI, id) is locally Noetherian for any Noetherian commutative ring
k. Moreover, they show that if Sd : FI → FI is the functor taking a set T to the
set of unordered d-tuples of distinct elements of T , then the pair (FI, Sd) is quasi-
Gröbner and the category Repk(FI, id) is locally Noetherian if and only if d ¬ 1
[NR19, Proposition 4.8].
Remark 2.1.8. Note that we have Repk(C) = Repk(C, ∅), where ∅ : C → FI is the
constant functor that takes every object of C to the empty set. We will see that the
category C is Gröbner (resp. quasi-Gröbner) in the sense of [SS17] if and only if the
pair (C, ∅) is quasi-Gröbner.
16
2.1.2. Gröbner pairs
Let OI be the category whose objects are totally ordered finite sets and
whose morphisms are ordered inclusions, and let Ψ : OI → FI be the functor
that forgets the order on a finite set. Let D be an essentially small category and
T : D → OI any functor. Recall the definition of AΨ◦T as in the previous section.
For convenience, we will write AT := AΨ◦T The purpose of this section is to define
what it means for the pair (D, T ) to be Gröbner.
A quartet for the pair (D, T ) is a quadruple µ = (D,D′, ϕ,m), where D and
D′ are objects of D, ϕ ∈ Hom ′D(D,D ), and m : T (D′) → N is a map of sets. For
any morphism ψ ∈ Hom (D′, D′′D ), we will write
ψ(µ) := (D,D′′, ψ ◦ ϕ,mψ),
where mψ is determined by the conditions that mψ◦T (ψ) = m and mψ is identically
zero outside of the image of T (ψ). For any map n : T (D′)→ N, we will write
µ+ n := (D,D′, ϕ,m+ n).
If µ1 = (D,D′1, ϕ1,m1) and µ2 = (D,D
′
2, ϕ2,m2), we say that µ1 ¬ µ2 if there exists
a morphism ψ : D′1 → D′ and a map n : T (D′′2 )→ N such that µ2 = ψ(µ1) + n.
Remark 2.1.9. The motivation for these definitions is that, once we choose a
commutative ring k, the quartet µ determines a monomial
∏
tm := tm(a) ′a ∈ AT (D )
a∈T (D′)
17
along with an element
b := tmµ · ϕ ∈ PD(D′) ∈ Repk(D,Ψ ◦ T ).
Then µ1 ¬ µ2 if and only if ϕ2 factors through ϕ1 via a map ψ and we have
b = tnµ2 ψ(bµ1)
for some monomial tn ∈ A(D′2).
We say that µ1 and µ2 are equivalent if µ1 ¬ µ2 and µ2 ¬ µ1. For each
object D of D, let |DTD| denote the poset of equivalence classes of quartets with first
coordinate D. Given a quartet µ = (D,D′, ϕ,m), we will write [µ] to denote its
equivalence class in |DTD|. A well-order ≺ of |DTd | is called admissible if, given two
quartets µ1 = (D,D′, ϕ1,m1) and µ2 = (D,D′, ϕ2,m2) with the same source and
target along with a morphism ψ : D′ → D′′ and a map n : T (D′′) → N, we have
that [µ1] ≺ [µ2] implies [ψ(µ1) + n] ≺ [ψ(µ2) + n].
We say that the pair (D, T ) satisfies property (G1) if, for every object
D of D, the poset |DTD| admits an admissible well-order. A poset P is said to be
Noetherian if, for any sequence (pi | i ∈ N) in P , there exist natural numbers
i < j such that pi ¬ pj. We say that the pair (D, T ) satisfies property (G2)
if, for every object D of D, the poset |DTD| is Noetherian. We call the pair (D, T )
Gröbner if D is directed and (D, T ) satisfies properties (G1) and (G2).
Remark 2.1.10. Property (G1) for the pair (D, ∅) is equivalent to property (G1)
for D as defined in [SS17, Section 1.1], and similarly property (G2) for the pair
(D, ∅) is equivalent to property (G2) for D. Thus a directed category D is Gröbner
in the sense of [SS17] if and only if the pair (D, ∅) is Gröbner.
18
The following Proposition says that the functor T does not add anything
interesting to property (G1). In other words, the distinction between a Gröbner
category and a Gröbner pair lies entirely in the property (G2).
Proposition 2.1.11. The pair (D, T ) satisfies property (G1) if and only if the pair
(D, ∅) satisfies property (G1).
Proof. If ≺ is an admissible order of |DTD|, then restriction to quartets with m = 0
gives an admissible order of |D∅D|. Conversely, if we have an admissible order of
|D∅D|, we can compare the classes of two quartets µ1 = (D,D′1, ϕ1,m1) and
µ2 = (D,D′2, ϕ2,m2) for (D, T ) by first comparing the classes of the quartets
(D,D′1, ϕ1, 0) and (D,D
′
2, ϕ2, 0) for (D, ∅) and then, if they are equal, breaking
the tie by comparing m1 and m2 lexicographically.
2.1.3. Gröbner bases
Let D be an essentially small category and T : D → OI a functor such that
the pair (D, T ) is Gröbner, and choose an admissible well-order ≺ of |DTD| for each
object D of D as in the definition of property (G1). For any pair of objects D and
D′ in D, let QD,D′ be the set of quartets of the form whose first two entries are D
and D′ respectively. The fact that D is directed implies that the natural map from
QD,D′ to |DTD| is injective, thus QD,D′ is well-ordered by ≺.
Fix a commutative ring k, so that we may define the representation category
Repk(D,Ψ ◦ T ). For any nonzero element
∑
p = λ b ∈ PT (D′µ µ D )
µ∈QD,D′
19
where bµ is defined as in Remark 2.1.9, we define the leading quartet LQ(p) to be
the maximal µ with respect to the well-order ≺ such that the coefficient λµ ∈ k is
nonzero. If µ = LQ(p), we define the leading term LT(p) := λ Tµbµ ∈ PD(D′) and
the leading coefficient LC(p) := λµ ∈ k.
Lemma 2.1.12. Suppose we have a morphism ψ : D′ → D′′, a map n : T (D′)→ N,
and an element 0 ≠ p ∈ PTD(D′). Then
LT(xnψ(p)) = xnψ(LT(p)).
Proof. This is precisely the definition of admissibility of the well-order ≺.
Given a submodule N ⊂ PTD, we define a subset
{ ∣ }
LQ(N ) := [LQ( )] ∣p ∣ 0 ≠ p ∈ N (d′) ⊂ |DTD|.
For each object D′ of D, we define
{ }
LT(N )(D′) := {0} ∪ LT(p) | 0 ̸= p ∈ N (D′) ⊂ PTD(D′) .
For each quartet µ = (D,D′, ϕ,m), we define the ideal
Lc(N , µ) := {0} ∪ {Lc(p) | 0 ≠ p ∈ N (D′) and LQ(p) = µ} ⊂ k.
Lemma 2.1.12 implies that LT(N ) ⊂ PTD is a submodule and that we have an
inclusion of ideals Lc(N , µ ) ⊂ Lc2 (N , µ1) whenever [µ1] ¬ [µ2].
20
Suppose we are given a finite set B = {(D′1, p1), . . . , (D′r, pr)} of pairs with
0 ̸= pi ∈ N (D′i) for all i. We say that B is a Gröbner basis for N if the module
LT(N ) is generated by the classes LT(pi) for 1 ¬ i ¬ r.
Lemma 2.1.13. If B is a Gröbner basis for N , then B generates N .
Proof. If not, choose an element p ∈ N (D′) that is not in the submodule generated
by B, and choose it in such a way that the leading quartet LQ(p) is minimal with
respect to the admissible well-order on |DTD|. Since B is a Gröbner basis, we may
choose an index i, a morphism ψ : D′ → D′i , a function n : T (D′) → N, and a
scalar λ ∈ k such that LT(p) = λxnψ(LT(pi)). By Lemma 2.1.12, this is equal to
LT(λxnψ(pi)). But then p − λxnψ(pi) is not in the submodule generated by B and
has a leading quartet strictly smaller than LQ(p), which gives a contradiction.
Proposition 2.1.14. Suppose that the ring k is Noetherian. For every object D of
D, the principal projective PTD ∈ Repk(D,Ψ ◦ T ) is Noetherian.
Proof. By Lemma 2.1.13, it is sufficient to show that every submodule N ⊂ PTD has
a Gröbner basis. By property (G2), the set LQ(N ) ⊂ |DTD| has only finitely many
minimal elements with respect to the partial order. Choose finitely many quartets
µ1, . . . , µr representing these minimal classes, and write µi = (D,D′i, ϕi,mi). For
each i, the fact that k is Noetherian implies that the ideal Lc(N , µi) is generated
by finitely many elements
λ1i , . . . , λ
si
i ∈ k.
For each j ¬ si, choose an element 0 ̸= pj ∈ N (D′i i) with LT(p
j
i ) = λ
j
i bµ , and leti
B := {(D′i, p
j
i ) | 1 ¬ i ¬ r, 1 ¬ j ¬ si}.
21
We claim that B is a Gröbner bases for N .
Let 0 ̸= p ∈ N (D′) be given; we will show that LT(p) is in the submodule of
PTd generated by the classes LT(p
j
i ). Let ν := LQ(p). By definition of the quartets
µ1, . . . , µr, there exists an index i such that [µi] ¬ [ν]. That means that we can
choose a morphism ψ : D′i → D′ and a map n : T (D′)→ N such that ν = ψ(µi) + n.
Since [µi] ¬ [ν], we have Lc(N , ν) ⊂ Lc(N , µi), and therefore there exist elements
ζ1i , . . . , ζ
si
i ∈ k such that
Lc(p) = ζ1i λ1i + · · ·+ ζ
siλsii i .
Then
LT(p) = Lc(p)bν
= (ζ1λ1 + · · ·+ ζsii i i λ
si
i )bψ(µi)+n
= xnψ( 1 j(ζi λi bµ + · · ·+ ζ
siλj
i i i bµ )i )
= xnψ ζ1 LT(p1) + · · ·+ ζsi LT(psii i i i )
is in the submodule of PTD generated by the classes LT(p
j
i ).
Corollary 2.1.15. Let D be an essentially small category, T : D → OI a
functor, and k a Noetherian commutative ring. If the pair (D, T ) is Gröbner, then
Repk(D,Ψ ◦ T ) is locally Noetherian.
Proof. Suppose that M ∈ Repk(D,Ψ ◦ T ) if finitely generated. By Lemma 2.1.2,
M is a quotient of a direct sum of principal projectives. Proposition 2.1.14 tells us
that each of these principal projectives is Noetherian, and Lemma 2.1.4 then tells
us that the same is true of M.
22
2.1.4. Quasi-Gröbner pairs
Let Φ : D → C be a functor. Following Sam and Snowden [SS17, Definition
3.2.1], we say that Φ has property (F) if, for any object X of C, there exist
finitely many objects D1, . . . , Dr of D along with morphisms ϕi : X → Φ(Di)
such that, for any object D of D and any morphism ψ : X → Φ(D), there exists an
i and a morphism ρ : Di → D such that ψ = Φ(ρ) ◦ ϕi. Given a functor S : C → FI,
we say that the pair (C, S) is quasi-Gröbner if there exists a Gröbner pair (D, T )
and an essentially surjective functor Φ : D → C with property (F) such that S ◦ Φ is
naturally isomorphic to Ψ ◦ T .
Remark 2.1.16. The pair (C, ∅) is quasi-Gröbner if and only if the category C is
quasi-Gröbner in the sense of [SS17].
Let Φ : D → C and S : C → FI be any functors. For any commutative ring
k, we have an exact functor Φ∗ : Repk(C, S) → Repk(D, S ◦ Φ) that takes a module
M∈ Repk(C, S) to
Φ∗M :=M◦ Φ ∈ Repk(D, S ◦ Φ).
Proposition 2.1.17. Let Φ : D → C be a functor with property (F), let S : C → FI
be any functor, and let k be a commutative ring. If M ∈ Repk(C, S) is finitely
generated, then Φ∗M∈ Repk(D, S ◦ Φ) is finitely generated.
Proof. Since M is finitely generated, Lemma 2.1.2 tells us that M is a quotient
of a direct sum of principal projectives. Since Φ∗ is exact, Φ∗M is a quotient of a
direct sum of pullbacks of principal projectives. Thus, it is sufficient to show that,
for any object X of C, Φ∗PTX is finitely generated. Choose finitely many objects
D1, . . . , Dr of D along with morphisms ϕi : X → Φ(Di) as in the definition of
23
property (F). Consider the maps
PTD → Φ∗PT ∗ TΦ(D ) → Φ PX ,i i
where the first map is induced by Φ and the second is induced by ϕi. Property (F)
says precisely that the direct sum map
⊕r
PT ∗ TD → Φ Pi X
i=1
is surjective, which implies that Φ∗PTX is finitely generated.
Proof of Theorem 2.1.6. Let (C, S) be quasi-Gröbner pair. That means that there
exists a Gröbner pair (D, T ), an essentially surjective functor Φ : D → C with
property (F), and a natural isomorphism Ψ ◦ T ∼= S ◦ Φ. Fix a commutative ring k,
a finitely generated module M ∈ Repk(C, S), and a submodule N ⊂ M. We need
to prove that N is finitely generated, as well.
Proposition 2.1.17 tells us that Φ∗M ∈ Repk(D, S ◦ Φ) ≃ Repk(D,Ψ ◦ T )
is finitely generated, and Corollary 2.1.15 then implies that Φ∗N ⊂ Φ∗M is
also finitely generated. Choose a finite generating set x1, . . . , xr of Φ∗(M) where
xi ∈ Φ∗N (Di). This means that, for any object D of D, Φ∗N (D) is spanned over
AS◦Φ(D) by the images of the elements xi along the maps induced by all possible
morphisms ϕi : D → Di. This is equivalent to saying N (Φ(D)) is spanned over
AS(Φ(D)) by the elements Φ(xi) ∈ N (Φ(Di)) along the maps induced by all
morphisms Φ(ϕi) : Φ(d) → Φ(di). Since Φ is essentially surjective, this means
that N is finitely generated.
24
2.2. Graphs
We define the category G¬g of genus at most g along with the edge functor
E : G¬g → FI and use the tools in Section 2.1 to prove that G¬g is quasi-Gröbner
and the pair (G¬g, E) is quasi-Gröbner.
2.2.1. Defining the graph categories
A directed graph is a quadruple (V,A, h, t), where V and A are finite sets
(vertices and arrows), and h and t are each maps from A to V (head and tail). A
graph is a quintuple (V,A, h, t, σ), where (V,A, h, t) is a directed graph and σ is a
fixed-point-free involution of A with the property that h = t ◦ σ. If (V,A, h, t, σ)
is a graph, elements of the quotient A/σ are called edges. Given a directed graph
D = (V,A, h, t), we define the underlying graph D̄ = (V, Ā, h, t, σ), where Ā =
A × {±1}, h(a, 1) = h(a) = t(a,−1), t(a, 1) = t(a) = h(a,−1), and σ acts by
toggling the second factor. We will usually suppress h and t from the notation and
simply write (V,A, σ) for a graph.
Remark 2.2.1. This might seem to be an unnecessarily complicated definition of
a graph. For example, one might try defining a graph to consist of a vertex set, and
edge set, and a map from edges to unordered pairs of vertices. However, we want a
graph with a loop to have a nontrivial automorphism that reverses the orientation
of the loop. It is difficult to formalize this with the unordered pair definition.
If G = (V,A, σ) is a graph and v, v′ ∈ V , a walk in G from v to v′ is a finite
sequence (a1, . . . , an) of arrows with t(a1) = v, h(an) = v′, and h(ai) = t(ai+1) for
all 1 ¬ i < n. A path in G from v to v′ is a walk from v to v′ such that removing
any collection of ai from the walk is no longer a walk. We say that G is connected
25
if there exists at least one path between any pair of vertices, and we say that G is
a forest if there exists at most one path between any pair of vertices. A nonempty
connected forest is called a tree.
Let G = (V,A, σ) and G′ = (V ′, A′, σ′) be graphs. A minor morphism from
G to G′ is a map
ϕ : V ⊔ A ⊔ {⋆} → V ′ ⊔ A′ ⊔ {⋆}
satisfying the following properties:
– ϕ(⋆) = ⋆.
– For every vertex v ∈ V , ϕ(v) ∈ V ′.
– For every arrow a ∈ A, ϕ ◦ σ(a) = σ′ ◦ϕ(a) where σ′ acts trivially on V ′ ⊔ {⋆}.
– For every arrow a′ ∈ A′, there exists a unique arrow a ∈ A with ϕ(a) = a′.
– If ϕ(a) ∈ A, then ϕ ◦ h(a) = h′ ◦ ϕ(a) and ϕ ◦ t(a) = t′ ◦ ϕ(a).
– If ϕ(a) ∈ V , then ϕ ◦ h(a) = ϕ(a) = ϕ ◦ t(a).
– For every v′ ∈ V ′, ϕ−1(v′) consists of the edges and vertices of a tree.
The edges that map to vertices are called contracted edges and the edges that
map to ⋆ are called deleted edges. Note that the second condition and third
conditions imply that the edges of G that are neither deleted nor contracted map
bijectively to the edges of G′. In particular, ϕ induces an injection ϕ∗ : A′/σ′ →
A/σ.
Remark 2.2.2. If G and G′ are connected graphs, then a minor morphism ϕ :
G → G′ is determined by its restriction to the set of arrows of G. (Connectedness
26
is necessary because the graph with two vertices and no arrows has a nontrivial
automorphism swapping the vertices.) However, it is convenient to define ϕ on
the whole set V ⊔ A ⊔ {⋆} so that minor morphisms can be composed simply
by composing functions. Note that ϕ is not determined by the map on edges
ϕ∗. To see this, consider the example where G has two vertices and two parallel
edges between them, and G′ consists of a single vertex with no edges. There are
two minor morphisms from G to G′, corresponding to the choice of which edge is
deleted and which edge is contracted.
Let G denote the category whose objects are nonempty connected graphs and
whose morphisms are minor morphisms.
Conjecture 2.2.3. The category Gop is quasi-Gröbner.
Remark 2.2.4. The Gröbner cover of Gop should be the category ODop of directed
graphs whose arrows are ordered with opposite minor morphisms that preserve the
order of arrows. That is if ϕ : (V,A, h, t) → (V ′, A′, h′, t′) is a minor morphism of
directed graphs whose arrows are ordered, then we also require that whenever a′1 ¬
a′2 in A
′, then ϕ∗(a′1) ¬ ϕ∗(a′2) in A. However, to prove that ODop satisfies property
(G2) one would need a stronger version of Robertson and Seymour’s labeled graph
minor theorem [RS10, 1.7] where the order of the labels on edges is preserved in the
above sense. If Conjecture 2.2.3 is proven, then all of the results in later sections
can be upgraded from statements about graphs with genus at most g to statements
about all graphs with no restriction on genus.
In light of Remark 2.2.4, we restrict our attention to a family of full
subcategories of Gop. The combinatorial genus or simply genus of a graph
G = (V,A, σ) is the quantity |A/σ| − |V | + 1. Viewed as a 1-dimensional
27
CW-complex where the 1-cells correspond to edges and the 0-cells correspond to
∨vertices, every graph is homotopy equivalent to a finite wedge product of g circlesg S1i=1 . For any g ­ 0, let G¬g be the full subcategory of G whose objects are non-
empty connected graphs of genus at most g.
Theorem 2.2.5. For any positive integer g, Gop¬g is quasi-Gröbner.
The proof of Theorem 2.2.5 follows mostly from the work in [PR19a]. We will
need slight generalizations of the theory they present which we outline below.
A rooted tree is a pair (T, v) where T is a tree and v is a vertex of T called
the root. There is a natural partial order on the vertex set of rooted tree where
w ¬ u if and only if the unique path from w to the root passes through u. A direct
descendant of a vertex w is a vertex covered by w with respect to this partial
order. A planar rooted tree is a rooted tree equipt with a linear order on the set
of direct descendants of each vertex. Note that this gives a depth first linear order
on the set of vertices.
In a nonempty connected graph G, a spanning tree for G is a subgraph that
is a tree and contains all vertices of G. Now, for each genus g, fix once and for all
a graph Rg with one vertex and g loops. Define a rigidified graph of genus g to
be a quadruple (G, T, v, τ) where G is a graph of genus g, (T, v) is a planar rooted
spanning tree of G, and τ : G → Rg is a minor morphism where the contracted
edges are exactly the edges of T . Note that rigidified graphs come equipt with
a linear order on the vertices coming from their planar rooted spanning trees. A
morphism of rigidified graphs (G, T, v, τ) → (G′, T ′, v′, τ ′) between rigidified
graphs of genus g is a minor morphism ϕ : G → G′ that restricts to a minor
morphism T → T ′ such that ϕ(v) = v′, and if w′ ¬ u′ under linear order on
vertices of G′, then the smallest vertex in the preimage of w′ comes before the
28
smallest vertex in the preimage on u′ under the linear order on the vertices of G.
Note that a minor morphism between graphs of the same genus necessarily has no
deleted edges.
Let RGg be the category whose objects are rigidified graphs of genus g and
whose morphisms are minor morphisms of rigidified graphs of genus g. Let RGop¬g
denote the category whose objects are rigidified graphs of genus at most g and
whose morphisms are minor morphisms of rigidified graphs between graphs of the
same genus. One can think of RGop¬g as a kind of disjoint union of the finitely many
categories RGoph for h ¬ g.
Theorem 2.2.6 ([PR19a]). For any g ­ 0, the category RGopg is Gröbner.
Corollary 2.2.7. For any g ­ 0, the category RGop¬g is Gröbner.
Proof. It is clear from the definitions that RGop¬g satisfies properties (G1) and (G2)
since RGoph satisifies both properties for each of the finitely many h ¬ g and there
are no morphisms between rigidified graphs of different genus in RGop¬g.
There is a forgetful functor
Φ op op¬g : RG¬g → G¬g
which sends a rigidified graph to its underlying graph and a minor morphism of
rigidified graphs to the underlying minor morphism of graphs.
Lemma 2.2.8. The functor Φ¬g satisfies property (F).
Proof. This proof is similar to the proof of [PR19a, Lemma 3.11]. The fact that
Φ¬g is essentially surjective is clear as every graph can be given a rigidified graph
structure.
29
Let G be a graph of genus h ¬ g with exactly n edges. To show Φ¬g has
property (F), we need to produce a finite collection (Gi, Ti, vi, τi) of Rigidified
graphs of genus at most g along with minor morphisms ϕi : Gi → G such that,
given any rigidified graph (G′, T ′, v′, τ ′) and minor morphism ϕ : G′ → G,
there exists an index i and a morphism of rigidified graphs ρ : (G′, T ′, v′, τ ′) →
(Gi, Ti, vi, τi) with ϕ = ϕi ◦ Φ¬g(ρ).
Consider all possible rigidified graphs with at most n + 2g − h edges and
genus at least h and at most g. For each isomorphism class of such rigidified graph,
choose a representative (G′′, T ′′, v′′, τ ′′) and add it to our collection (Gi, Ti, vi, τi) as
many times as there are minor morphisms G′′ → G. Then, take our collection of
minor morphisms ϕi so that for each i, every possible minor morphism Gi → G
appears in our collection. Note, there are only finitely many isomorphism classes of
rigidified graphs with at most n + 2k − h in RGoph and for such a rigidified graph
there are only finitely many minor morphisms from the underlying graph to G.
Thus our collection of rigidified graphs and minor morphisms is indeed finite.
Now, fix a rigidified graph (G′, T ′, v′, τ ′) with genus k where h ¬ k ¬ g and
a minor morphism ϕ : G′ → G. Let E ′ be the set of edges that are contracted
under ϕ. In a morphism of rigidified graphs, we are only allowed to contract edges
in the designated spanning tree. Thus, let ρ be the morphism of rigidified graphs
ρ : (G′, T ′, v′, τ ′) → (G′/(E ′ ∩ T ′), T ′/(E ′ ∩ T ′), v′, τ ′) corresponding to contracting
the edges of E ′ ∩ T ′. Clearly ϕ factors through Φ¬g(ρ). All that we must verify is
that (G′/(E ′ ∩ T ′), T ′/(E ′ ∩ T ′), v′, τ ′) is a member of our collection. In otherwords,
we must show that G′/(E ′ ∩ T ′) has at most n+2g− h edges. Let n′ be the number
of edges of G′. Since deleting an edge lowers the genus of the graph by 1, we know
that under ϕ, exactly k − h edges are deleted. Thus, n′ = n + k − h + |E ′| or
30
equivalently,
|E ′| = n′ − (n+ k − h).
Furthermore, we know that the number of edges in T ′ is equal to n′ − k. Thus,
|E ′ ∩ T ′| ­ n′ − (n+ k − h)− k = n′ − n− 2k + h.
This implies that the number of edges in G′/(E ′ ∩ T ′) is at most
n′ − (n′ − n− 2k + h) = n+ 2k + h
which is no more than n+ 2g + h since k ¬ g.
2.2.2. Edge functors
Recall that given a minor morphism of graphs ϕ : (V,A, σ) → (V ′, A′, σ′), we
get an inclusion of edge sets ϕ∗ : A′/σ′ → A/σ. Thus, we have an edge functor
E : Gop¬g → FI
taking a graph G to its set of edges. Similarly, the edges of a rigidified graph
are totally ordered and given minor morphism of rigidified graphs, the pullback
inclusion on edge sets preserves this order. This gives an ordered edge functor
Ω : RGop¬g → OI
31
taking a rigidified graph to its ordered set of edges. Recall from Section 2.1.2 that
Ψ : OI → FI is the forgetful functor that sends an ordered set to its underlying
(unordered) set.
Lemma 2.2.9. Ψ ◦ Ω and E ◦ Φ¬g are naturally isomorphic functors RGop¬g → FI.
Proof. This is clear from the definitions of the functors.
Theorem 2.2.10. The pair (RGop¬g,Ω) is Gröbner.
To prove Theorem 2.2.10 we will need a labeled version of a planar rooted
tree. This is a slightly generalized version of the notion of an S-labeled planar
rooted tree in [PR19a]. Let L be a set equipt with a well quasi order ¬. An L-
labeled planar rooted tree is a triple (T, v, ℓ) where (T, v) is a planar rooted
tree and ℓ is a function from the set of vertices of T to L. An L-labeled minor
morphism of planar rooted trees or simply L-labeled minor morphism
(T, v, ℓ)→ (T ′, v′, ℓ′) is a minor morphism ϕ : (T, v)→ (T ′, v′) of rigidified graphs of
genus 0 (planar rooted trees are exactly the rigidified graphs of genus 0) such that
ℓ′(w′) ¬ ℓ′(maxϕ−1(w′)) where maxϕ−1(w′) is the first vertex in the preimage of w′
under ϕ with respect to the natural depth first order on the vertices of T . Let PT L
denote the category whose objects are L-labeled planar rooted trees and whose
morphisms are L-labeled minor morphisms. For a fixed L-labeled planar rooted
tree (T, v, ℓ), we may give a quasi oreder ¬L to the L-labeled minor morphisms into
(T, v, ℓ). Namely, if ϕ′ : (T ′, v′, ℓ′) → (T, v, ℓ) and ϕ′′ : (T ′′, v′′, ℓ′′) → (T, v, ℓ)
are L-labeled minor morphisms, then ϕ ¬ ϕ′′L if and only if there exists an L-
labeled minor morphism ϕ : (T ′′, v′′, ℓ′′) → (T ′, v′, ℓ′) such that ϕ′′ = ϕ′ ◦ ψ. Let
|(PT opL )(T,v,ℓ)| denote the poset of equivalence classes of L-labeled minor morphisms
into (T, v, ℓ) under this quasi order.
32
Lemma 2.2.11. Let L be a well-quasi-ordered set. Partially order the isomorphism
classes of L-labeled planar rooted trees where [(T ′, v′, ℓ′)] ¬ [(T, v, ℓ)] if and only if
there is a minor morphism of L-labeled planar rooted trees (T, v, ℓ) → (T ′, v′, ℓ′).
This is a well-quasi-order.
Corollary 2.2.12. Let L be a well-quasi-ordered set. Fix an L-labeled planar rooted
tree (T, v, ℓ). The poset |(PT opL )(T,v,ℓ)| is a well-quasi-order.
Remark 2.2.13. As stated before, the notions of an L-labeled planar rooted
tree and L-labeled minor morphism are, repsectively, slight generalizations of the
notions of an S-labeled planar rooted tree and an S-labeled contraction defined in
[PR19a] where the set of labels was an (unordered) finite set. Lemma 2.2.11 and
Corollary 2.2.12 are the analogues of and have identical proofs to [PR19a, Theorem
3.6] and [PR19a, Corollary 3.7] respectively. Thus, we omit their proofs here.
⊔ Recall from Section 2.1.2 that a quartet µ = (R,R
′, ϕ,m) for the pair
( oph¬gRGh , OE) consists of two rigidified graphs of genus at most g, R =
(G, T, v, τ), R′ = (G′, T ′, v′, τ ′), a minor morphism of rigidified graphs ϕ : R′ → R,
and a map of sets m from the edges of R′ to N. We should think of m as assigning
to each edge of R′ a natural number. For any fixed rigidified graph R, We also
have a quasi order on quartets whose first coordinate is R where (R,R′, ϕ′,m′) ¬
(R,R′′, ϕ′′,m′′) if there exists a minor morphism of rigidified graphs ψ : R′′ → R′
such that ϕ′′ = ϕ′ ◦ ψ and if e′ is an edge in R′, m′(e′) ¬ m′′(ϕ∗(e′)) where ϕ∗ is the
natural inclusion of the edges of R′ to the edges of R′′. Denote the corresponding
poset of equivalence classes under this quasi order by |(RGop OE¬g)R |.
Fix a rigidified graph R = (G, T, v, τ) with genus h ¬ g. Now for a suitable
choice of L, we wish to encode each quartet with first coordinate R as an L-
labeled planar rooted tree so that the poset |(RGop OE¬g)R | is equivalent to the poset
33
|(PT opL )(T,v,ℓ)| where (T, v) is the planar rooted tree of R and ℓ is some suitable
label. To this end, let L = (N∪{⋆})2h×N. Order (N∪ ⋆) with the usual order order
on N along with setting ⋆ to be incomparable to all elements of N. Then, give L the
usual order on the cartesian product of posets.
Given a quartet of the form (R,R′, ϕ,m), where R′ = (G′, T ′, v′, τ ′) the
corresponding L-labeled planar rooted tree will be of the form (T ′, v′, ℓ′) for some
labeling ℓ′. Note that R′ must also have genus h since we only have morphisms
of rigidified graphs between rigidified graphs of the same genus. Thus, R′ has h
extra edges not in T ′. The planar rooted structure of (T ′, v′) gives an orientation
and ordering to these h extra edges (we orient them from smaller to larger vertex
and then order them by the order on their terminating vertex). Call these extra
edges e′ , . . . , e′1 h. For each 1 ¬ i ¬ h, let w′2i−1 be the vertex at which ei originates
and let w′2i be the vertex at which ei terminates. Then for each vertex w
′ of T ′,
and each 1 ¬ j ¬ 2h, define the jth coordiante of ℓ′(w′) to be m(e′j) if w ­ wj
and ⋆ otherwise. Then for each edge e′ in T ′, if w′ is the vertex of e′ further from
the root, set the last coordinate of w′ to m(e′). Finally set the last coordinate
of ℓ′(v′) to 0. The intuition behind this labeling is that the first 2h coordinates
encode the location and weights given by m for the h edges not in T ′. The last
coordinate encodes the weights given by m of the edges in T ′. Finally, let ℓ be the
fixed labeling of (T, v) corresponding to the quartet (R,R, IdR, 0).
Lemma 2.2.14. Let (R,R′, ϕ,m) be a quartet and (T ′, v′, ℓ′) be the corresponding
L-labeled planar rooted tree as defined above. Then ϕ induces an L-labeled
morphism ϕ : (T ′, v′L , ℓ′)→ (T, v, ℓ).
Proof. This follows from the proof of Lemma [PR19a, Lemma 3.8].
34
Lemma 2.2.15. Let µ′ = (R,R′, ϕ′,m′) and µ′′ = (R,R′′, ϕ′′,m′′) be quartets with
corresponding L-labeled planar rooted trees (T ′, v′, ℓ′) and (T ′′, v′′, ℓ′′) and define ϕ′L
and ϕ′′ as in Lemma 2.2.14. Then µ′ ¬ µ′′ if and only if ϕ′ ¬ ϕ′′ in |(PT opL L L L )(T,v,ℓ)|
Proof. Note that µ′ ¬ µ′′ means there exists a minor morphism of rigidified
graphs ψ : R′′ → R′ such that ϕ′′ = ϕ′ ◦ ψ and for any edge e′ of R′,
m′(e′) ¬ m′′(ψ∗(e′)). The proof of [PR19a, Lemma 3.8] shows that such a minor
morphism ψ is equivalent to an L-labeled minor morphism of L-labeled planar
rooted trees ψL : (T ′′, v′′, ℓ′′)→ (T ′, v′, ℓ′) such that ϕ′′L = ϕ′L ◦ ψL. This is equivalent
to saying ϕ′ ¬ ϕ′′L L.
proof of Theorem 2.2.10. That the pair (RGop¬g,Ω) satisfies property (G1) follows
from Corollary 2.2.7 and Proposition 2.1.11. The fact that (RGop¬g, OE) satisifies
property (G2) follows from Lemma 2.2.15 and Corollary 2.2.12.
Theorem 2.2.16. The pair (Gop¬g, E) is quasi-Gröbner
Proof. This follows from Lemmas 2.2.8 and 2.2.9.
2.2.3. Finite generation
Theorems 2.2.5 and 2.2.16 tell us that the categories of representations
Rep (Gopk ¬g) and Repk(G
op
¬g, E) are locally Noetherian. That is, every submodule
of any finitely generated module of either of these categories, is itself finitely
generated. If M is a module in one of these categories, this Noetherianity property
allows us to conclude global properties about M that only depend on the module
M itself and g. The first such property gives a bound on how fast Gop¬g-modules can
grow. For the following statement, we write e(G) for the number of edges of G, and
v(G) for the number of vertices and gen(G) for the genus of G.
35
Theorem 2.2.17. Let M be a finitely generated Gop¬g-module over a field k. Say M
is generated by the graphs G1, . . . , Gr. Let N = maxi |e(Gi)|. Then there exists a
polynomial Pg ∈ Q[x, y] of degree at most N such that, for any graph G of genus at
most g,
dimkM(G) ¬ τ(G)P (e(G), v(G)),
Proof. By 2.1.2, it will suffice to prove the theorem in the case where M is the
principal projective Gop¬ -module P ′ ′G′ , for some fixed graph G of genus h ¬ g. In
this case, for any graph G of genus h ¬ g, the dimension of PG′(G) is precisely
the number of minor morphisms from G to G′. Any such morphism, up to an
automorphism of G′, can be determined in the following way: First one picks a
spanning tree of G in which all of the contractions and none of the deletions will
take place. There are exactly h edges not in this spanning tree and we need to
select h − h′ of them to delete, or equivalently h′ of them not to delete. There
are e(G) − h in the spanning tree and we need to contract all but e(G′) − h′ of
those edges. Thus, the number of minor morphisms from G to G′, or equivalently
dimPG′(G), has the following bound.
( )( )
P h e(G)− hdimk G′(G) ¬ τ(G) ′
h′ e(G′ ′
|Aut(G )|.
)− h
This implies
′( )e(G′)−h′
dimkM(G) ¬ τ(G)hh e(G)− h |Aut(G′)|.
We can rewrite this using the fact that h = e(G)−v(G)+1 and h′ = e(G′)−v(G′)+1,
which gives
( )e(G′)−v(G′)+1( )e(G′)−h′
dimkM(G) ¬ τ(G) e(G)− v(G) + 1 v(G)− 1 |Aut(G′)|.
36
Since G′ is fixed, the product of terms after τ(G) is a polynomial in e(G) and
v(G) of degree at most e(G′). Since PG′ is generated by the single element idG′ ∈
PG′(G′), the result holds.
Remark 2.2.18. The bound of Theorem 2.2.17 is an improvement of a bound
found in [PR19a]., and can be seen to be sharp. Consider the principal projective
module PG0 , over the graph G0 consisting of a single vertex with no edges. A minor
morphism from a graph G to G0 is precisely determined by a choice of spanning
tree for G. In particular,
dimk PG0(G) = τ(G)
Our second global property shows the kinds of torsion that can appear
in M(G) for M a finitely generated modules in Repk(G
op
¬g) or Rep (G
op
k ¬g, E) is
independent of the graph itself.
Theorem 2.2.19. Let M be a finitely generated Gop¬g-module (resp. AE-module)
over Z. Then, there exists a non-negative integer ϵg such that for all graphs G of
genus at most g, the torsion part of M(G) is annihilated by ϵg.
Proof. If t ∈ M(G) is a torsion element, then for any minor morphism ϕ : G′ → G,
the induced map M(G) →M(G′) must send t to a torsion element. Thus, we have
a submodule T of M, where T sends a graph G to the torsion part of M(G). By
assumption M(G) is a finitely generated, so Theorem 2.2.5 (resp. Theorem 2.2.16)
tells us that T is also finitely generated, by say the elements x1, . . . , xn. We may
take ϵg to be the least common multiple of the annihilators of x1, . . . , xn.
Remark 2.2.20. It is important to note that Theorems 2.2.17 and 2.2.19 are very
much not constructive. Thus, they give us no control over the polynomial that
37
bounds dimension growth or the torsion that can appear. They simply tell us that
these properties are uniform for all graphs of genus ¬ g.
In the remaining sections of Chapter II we gives examples of finitely generated
Gop¬ -modules and AE-modules and leverage Theorems 2.2.17 and 2.2.19 to prove
certain graph invariants are uniform over all graphs with genus at most g for any
fixed g.
2.3. Homology of configuration spaces of graphs
Let G be a graph and n a natural number. We can think of G as a 1-
dimensional CW-complex whose 0-cells correspond to the vertices of G and whose
1-cells correspond to the edges of G. The unordered configuration space of n
points in G, is the topological space
{ ∣ }
Un(G) := (x1, . . . , x n
∣
n) ∈ G ∣ xi ≠ xj /Sn
where Sn acts by permuting the coordinates of (x1, . . . , xn) ∈ Gn.
Fix an integer g ­ 0. Let E : Gop¬g → FI be the edge functor sending a graph
G to its set of edges and let AE be the associated Gop¬g-algebra for the pair (G
op
¬g, E)
over the ring k = Z. That is, given a graph G of genus ¬ g,
AE(G) = Z[te | e ∈ E(G) = A/σ.
For any graph G, let ⊕
Hi(G) := Hi(Un(G);Z).
n∈N
38
Our goal is to show that Hi can be given the structure of a finitely generated
graded AE-module.
2.3.1. The reduced Świątkowski complex
Let G = (V,A, σ) be a graph. For a vertex v ∈ V , let Mv(G) be the free
AE(G)-module generated by the formal symbol ∅ along with the set
hv := {a ∈ A | h(a) = v}.
Equip a bigrading on Mv(G) where deg te = (0, 1) for all e ∈ E(G), deg ∅ = (0, 0),
and deg a = (1, 1) for any a ∈ hv. Let M̃(G) ⊆ M(G) be the submodule generated
by ∅ and elements of the form a − a′ for a, a′ ∈ hv. For a, a′ ∈ hv =⊆ A, let
[a], [a′] ∈ E(G) be their respective images in E(G) and give M̃(G) the differential
∂v of degree (−1, 0) by setting
∂(a− a′) := (t[a] − t[a′])∅ and ∂∅ = 0
and extending AE(G)-linearly to all of M̃(G). The reduced Świątkowski
complex of G is ⊗
S̃(G) := M̃v(G)
v∈V
where the tensor product is taken over AE(G).
In [ADCK19, Lemma C.7], An, Drummond-Cole, and Knudson show that
whenever ϕ : G → G′ is a minor morphism, there is an induced map ϕ̃∗ : S̃(G′) →
S̃(G) of R(G′)-modules. which gives S̃ the structure of an AE-module. Moreover,
the AE-module structure on S̃ respects the bigrading and differential. Thus, for
39
each i ∈ N , S̃i,• also has the structure of an AE-module and the differential in S̃
can be seen as a morphism ∂i : S̃i,• → S̃i−1,• of AE-modules. Taking homology in
degree i, we obtain another AE-module
Hi(S̃) := ker(∂i)/ im(∂i+ 1).
Note that Hi(S̃) is graded via the second component of the grading on S̃. The
following theorem appears in [ADCK19, Theorem 4.5 and Proposition 4.9].
Theorem 2.3.1. Let G be a graph. For all i > 0, there exists a canonical
isomorphism graded A ∼E-modules Hi(S̃(G)) = Hi(G).
2.3.2. Finite generation
Identifying Hi(S̃(G)) with Hi(G) under the isomorphism given in Theorem
2.3.1 gives us an AE-module structure on Hi. In [ADCK20, Theorem 2.10], it is
shown that for a graph G, the action of AE(G) on Hi(G) comes from a map of
topological spaces. Specifically, for an edge e ∈ E(G), there is a stabilization map
of topological spaces Σn,e : Un(G) → Un+1(G) which adds a point to the edge e and
the generator te ∈ AE(G) acts on Hi(G) via the induced map (Σn,e)∗ on homology.
Thus, the AE-module structure on Hi can be fully described without the use of S̃.
However, to prove finite generation of Hi, we will need to take advantage of the
isomorphism with Hi(S̃).
Proposition 2.3.2. The AE-module S̃i,• is generated by S̃i,i(G) for all graphs G of
genus ¬ g with at most 2i edges. More precisely, let G1, . . . , Gr be representatives
of each isomorphism class of graph with at most 2i edges. For each 1 ¬ s ¬ r,
40
choose a basis for the finite rank free abelian group S̃i,i(Gs). Taken all together,
these finitely many classes generate S̃i,•.
Proof. For each graph G = (V,A, σ), A(G)-module S̃i,•(G) is generated by classes
of the form ⊗i ⊗
ξ := (a − a′j j) ⊗ ∅,
j=1 v∈/{v1,...,vi}
where v1, . . . , vi are distinct vertices and, for each j, a ′j and aj are arrows with
h(aj) = vj = h(a′j).
We will call v1, . . . , vi ∈ V distinguished vertices and [a ′1], [a1], . . . , [ai], [a′i] ∈
E(G) distinguished edges. If G has an edge e such that at least one vertex
incident to e is not distinguished and e is not a loop, then the class ξ may be
pulled back from the graph obtained from G by contracting e [PR19a, Section
5.3]. Furthermore, if e is not distinguished and not a bridge, then it is clear that
the class ξ may be pulled back from the graph obtained from G by deleting e.
Note that contracting an edge preserves the genus of a graph and deleting an edge
decreases the genus, thus the graphs obtained either by deleting or contracting an
edge e are objects in Gop¬g. Thus, if we are looking for generators for S̃i,•, we may
restrict our attention to the graphs G in Gop¬g and classes ξ ∈ S̃i,•(G) for which
every edge of G is either a distinguished edge or a bridge between distinguished
vertices. Finally, it is straightforward to check that ξ may be written as a linear
combination of classes for which every bridge between distinguished vertices is itself
a distinguished edge. Since there are at most 2i distinguished edges, it is sufficient
to consider those graphs with at most 2i edges.
Theorem 2.3.3. For any i ∈ N, the AE-module Hi is finitely generated.
41
Proof. When i = 0, the theorem is trivial. If i > 0, we know that Hi is isomorphic
to a subquotient of S̃i,• by Theorem 2.3.1. Theorems 2.1.6 and 2.2.5 imply that
subquotients of finitely generated AE-modules are themselves finitely generated.
Proposition 2.3.2 shows that S̃i,• is finitely generated so the result follows.
By Theorem 2.2.19, we immediately have the following Corollary.
Corollary 2.3.4. For any i ∈ N and g > 0, there is an integer ϵi,g depending only
on i and g such that for any graph G of genus ¬ g and any n ∈ N, the torsion part
of Hi(Un(G);Z) is annihilated by ϵi, g.
Note that S̃i,• is finitely generated as a A -module but not as a GopE ¬g-
submodule of Hi. In particular, S̃i,•(G) is infinite dimensional over Z for any graph
G. However, let us now fix n ∈ N and consider the Gop¬g-submodule of S̃i,n of S̃i,•.
Proposition 2.3.5. The Gop¬g-module S̃i,n is finitely generated. Moreover, finite list
of generators can be taken from S̃i, n(G) for graphs G with at most 2i edges.
Proof. By Proposition 2.3.2, S̃i,• is generated as an AE-module by the finitely many
generators of S̃i,i(G) for the finitely many graphs G with at most 2i edges. Let
x1, . . . , xr be this finite list of generators where for each 1 ¬ j ¬ r, xj ∈ S̃i,i(Gj)
for the graph Gj with 2i edges. Thus, as a Gop¬ -module, S̃i,n is generated by all
elements of the form axj ∈ S̃i,n(Gj) where a ∈ AE(Gj) = Z[te | E(Gj)] is a
monic monomial of degree n− i of which there are finitely many.
Now applying Theorem 2.2.17 we obtain the following.
Corollary 2.3.6. For any natural number i, and any natural number n, there exists
a polynomial P (x, y) of degree at most 2i such that for any graph of genus at most
42
G, if V is the set of vertices of G,
dimHi(Un(G);Z) ¬ τ(G)P (|E(G)|, |V |).
Proof. By Theorem 2.3.1, dimHi(Un(G);Z) ¬ dim S̃i,n(G). By Proposition 2.3.5,
S̃i,n is finitely generated by finitely many elements coming from S̃i,n(G′) for graphs
G′ with at most 2i edges. Thus 2.2.17 gives the desired result.
2.4. The matching complex and monotone graph properties
For a graph G, a matching on G is a subset S ⊆ E(G) of non-loop edges
such that no two edges in S share a vertex. Note that any subset of a matching
is also a matching and the empty set, ∅, is a matching. Thus, the collection of
matchings on G forms a simplicial complex M(G) whose vertices are the edges of
G, which we call the matching complex on G.
The topology of matching complexes on the complete graphs Kn and the
complete bipartite graphs Km,n have been well studied. Much of what is known
about the topology of these complexes is outlined in [Wac03] and [Jon08]. We
outline a few notable results on these complexes below.
The rational homology of these complexes is known due to the work of
Bouc [Bou92] and Friedman and Hanlon [FH98]. However, much is still unknown
regarding the torsion in the integral homology of these complexes. Shareshian and
Wachs show that the homology of M(Kn) exhibits 3-torsion for sufficiently large
n and the homology of M(Km,n) also contains 3-torsion for certain (but infinitely
many) values of m and n [SW07]. Later, Jonsson showed that 5-torsion in present
in the homology of M(Kn) for sufficiently large n and found that there are elements
43
of order 5, order 7, order 11, and order 13 appearing in the homology of M(Kn)
for varying values of n [Jon10a]. For graphs other than Kn and Km,n, not much is
known about the topology of their matching complex.
There is also a natural generalization of the matching complex. Note, that
for a graph G, and any subset F ⊆ E(G), we have the induced the subgraph GF
of G. Namely, GF is the graph with V (GF ) = V (G) and E(GF ) = F . Thus, F
is a matching on G if and only if each vertex of GF has degree at most 1. More
generally, for any integer d ­ 1 we can consider subsets F ⊂ E(G) such that each
vertex of GF has degree at most d. Call such a subset a d-matching of G. Note
that the collection of all d-matchings on G forms a simplicial complex which we will
denote Md(G). In particular, M1(G) = M(G), the matching complex. Complexes of
d-matchings of graphs have been studied in [Sin20] and [Jon13].
We will study the homology of these complexes Md(G) by showing that Md
has the structure of a finitely generated Gop¬g-module.
2.4.1. The edge module
Fix the base ring k = Z. Let E be the Gop¬g-module which assigns to each
graph G the free Z-module with basis indexed by the edges of G. Given a minor
morphism ϕ : G → G′, the natural inclusion ϕ∗ : E(G′) → E(G) gives us a natural
inclusion E(ϕ) : E(G′) → E(G). Thus, E is a Gop¬g-module which we will call the
edge module. It satisfies a very important property.
Lemma 2.4.1. For any i, the ith tensor power of the edge module, E⊗i, is a finitely
generated Gop¬g-module generated by graphs with at most i edges.
Proof. For any graph G, E⊗i(G) has basis given by i-tuples of edges of G. Let G
be a graph with strictly more than i edges. Then for any tuple (e1, . . . , ei) of edges
44
of G, one may find an edge e of G that is not among the ej. By contracting e, or
deleting it in the case where e is a loop, one obtains a minor morphism ϕ : G → G′
for a new graph G′. It is clear that the tuple (e1, . . . , ei) will be in the image of the
map E(G′) → E(G) induced by ϕ. Thus, E⊗i is generated by graphs with at most i
edges, of which there are only finitely many up to isomorphism in Gop¬g.
2.4.2. Finite generation
Now we are ready to prove that Hi(Md(−);Z) is a finitely generated Gop¬g-
module.
Theorem 2.4.2. For any i ­ 0 and any d ­ 1, Hi(Md(−);Z) is a finitely generated
Gop¬g-module.
Proof. For this proof, we are working with Z-coefficients, though we will supress
this from the notation. Also, for a graph G, let V (G) denote its set of vertices.
First, we argue that Hi(Md(−)) is in fact a Gop¬g-module. Given a minor
morphism ϕ : G → G′ of connected graphs, we have an induced inclusion on
edge sets ϕ∗ : E(G′) → E(G). Now, let F ′ ⊂ E(G′). If some vertex v ∈ V (G)
were incident to more than d edges in ϕ∗(F ′), then ϕ(v) ∈ V (G′) would be incident
to more than d edges in F ′. Thus, if F ′ is a d-matching on G′, then ϕ∗(F ′) is a d-
matching on G. We may therefore, consider ϕ∗ as a function
ϕ∗ : {d-matchings on G′} → {d-matchings on G}.
45
Furthermore, this map is compatible with taking boundaries of simplices and so we
get a map of chain complexes
ϕ ′• : C•(Md(G ))→ C•(Md(G))
where C•(Md(G)) denotes the simplicial chain complex of Md(G). This induces a
map H ′i(Md(G ))→ Hi(Md(G)). The above construction is compatible compositions
of minor morphisms and so indeed H (M (−)) is a Gopi d ¬g-module.
To see that it is finitely generated, note that following the above construction,
for any i, Ci(Md(−)) also forms a Gop¬g-module and Hi(∧Md(−)) is a subquotient of
Ci(Md(−)). Notice that Ci(Md(−)) is a submodule of i E , the ith wedge power of
the edge module, which is a quotient of E⊗i. Therefore Hi(Md(−)) is a subquotient
of E⊗i. By Lemma 2.4.1, E⊗i is a finitely generated Gop¬g-module and so Theorem
2.2.5 tells us Hi(Md(−)) is itself finitely generated.
Corollary 2.4.3. For any i ­ 0 and d ­ 1, there exists a polynomial Pd,g(x, y) of
degree at most i, such that for any connected graph G with genus ¬ G,
dimHi(Md(G), ;Z) ¬ τ(G)P (|E(G)|, |V (G)|).
Proof. By the proof of Theorem 2.4.2, dimHi(Md(G);Z) ¬ dim E⊗i which is finitely
generated by graphs with at most i edges. Thus applying Theorem 2.2.17 gives the
desired result.
Applying Theorem 2.2.19 we also have the following.
46
Corollary 2.4.4. For any i ­ 0 and any d ­ 1, there exists a positive integer
ϵi,d,g such that, for any connected graph G with genus at most g, the torsion part of
Hi(Md(−)) is annihilated by ϵi,d,g.
2.4.3. Other graph complexes
The matching complex of a graph is just one example of a simplicial
complex on the edges of a graph. More generally, one can consider what is called a
monotone graph property. This is a collection P of (not necessarily connected)
graphs, closed under isomorphisms, such that if G ∈ P and G′ is another graph
with V (G′) = V (G) and E(G′) ⊆ E(G), then G′ ∈ P . In other words, P is
closed under edge deletions. Note that, for any graph G, we obtain a simplicial
complex ∆P(G) on the edges of G where the n-simplices of ∆P(G) correspond to
graphs G′ ∈ P with V (G′) = V (G), E(G′) ⊂ E(G), and |E(G′)| = n + 1.
Intuitively if we identify a graph in P with its set of edges, the n-simplices of
∆P(G) are just subsets of E(G) of size n + 1 that are in P . See [Jon08] for a
comprehensive reference on graph complexes. In particular [Jon08, Table 7.1] gives
a list of monotone graph properties and what is known about the homotopy type of
their corresponding simplicial complexes.
A minor morphism ϕ : G → G′ induces an inclusion ϕ∗ : E(G′) → E(G).
Suppose that P is a monotone graph property with the extra condition that, if
ϕ : G → G′ is a minor morphism and H ′ is a simplex in ∆ ′P(G ) (that is, H ′ ∈ P ,
V (H ′) = V (G′), and E(H ′) ⊆ E(G′)), then the subgraph of G induced by the
image ϕ∗(E(H ′)) is also in P . Call such a P a Gop¬g-monotone graph property.
In rough terms, a Gop¬g-monotone graph property is a monotone graph property that
is also preserved under “uncontracting” edges. Note that by construction, if P is a
47
Gop¬g-monotone graph property, then for any minor morphism ϕ : G → G′, the n-
simplices of ∆ (G′P ) naturally include in the n-simplices of ∆P(G). This observation
and the argument used in the proof of Theorem 2.4.2 yields the following result.
Theorem 2.4.5. Let P be a Gop¬g-monotone graph property. For any i, the
assignment of G to the ith simplicial homology group Hi(∆P(G)) forms a finitely
generated Gop¬g-module.
Thus, for any Gop¬g-monotone graph property, one would obtain an analogous
result to Corollaries 2.4.3 and 2.4.4 about dimension of and the torsion that can
appear in the ith homology group of ∆P(G) as G ranges over all graphs with genus
at most g.
2.5. Commutative algebra of graph complexes
Famously, the study of simplicial complexes is, in a formal sense, dual to the
commutative algebra of squarefree monomial ideals through the Stanley-Reisner
correspondence. We consider this perspective in this section. Fix a field k. Recall
that given the edge functor E : Gop¬g → FI gives rise to another functor AE from G
op
¬g
to k-algebras where
AE(G) = k[te | e ∈ E(G)].
In [NR19], Nagel and Römer show there are uniform bounds on the degrees
for nonvanishing graded Betti numbers for certain families of ideals that form
modules over a particular FI-algebra. Using similar techniques, we start by
describing some of the homological algebra for AE-modules and prove analogous
results about the graded Betti numbers for families of ideals forming modules over
the edge algebra AE.
48
Lemma 2.5.1. For any finitely generated AE-module M there exists a projective
resolution F• of M by finitely generated AE-modules.
Proof. By Lemma 2.1.2, since M is finitely generated, there exists graphs
G1, . . . , Gn and a surjection ⊕n
PEG →Mi
i=1 ⊕
where PEG is the principal projective A -module at G . Let F = n PEi E i 0 i=1 G . Thei
kernel K of this surjection must be finitely generated by Theorem 2.2.16 and so
again, we may find finitely many graphs H1, . . . , Hm such that there is a surjection
⊕m
PEH → K.i
i=1
⊕
Let F = m E1 i=1PH . Continuing in this fashion, we build the entire projectivei
resolution F• of M .
Given two finitely generated AE-modules, M and N , we may take their
tensor product over AE by taking the pointwise tensor product. This gives an AE-
module M⊗A N . Explicitly, for any graph G,E
(M⊗A N )(G) =M(G)⊗A (G) N (G),E E
where the morphisms are defined in the obvious way. Now, take a projective
resolution F• of M as in Lemma 2.5.1. Tensoring this resolution with N gives a
chain complex F•⊗A N of AE-modules. We define Tori(M,N ) to be the homologyE
of this chain complex. Specifically,
Tori(M,N ) = Hi(F• ⊗A N ).E
49
Remark 2.5.2. Given a finitely generated graded AE-module M, we may
upgrade the surjection of Lemma 2.1.2 to a surjection of graded AE-modules in the
following way. Suppose M is generated by the elements x1, . . . , xn where for each i,
xi ∈ M(Gi). We may assume that each xi is a homogeneous element of M(Gi) of
degree di. Then, for each i, we give a grading to the principal projective AE-module
PEG the grading where ϕ ∈ PEG (G) is homogeneous of degree di for any graph G,i i
and minor morphism ϕ : G→ Gi. Then, the morphism of AE-modules
⊕n
PEG →Mi
i=1
that sends idG to xi is a surjection of graded AE-modules. With this fact, we seei
that the projective resolution of Lemma 2.5.1 may, in fact, be upgraded to a a
projective resulotion of graded AE-modules.
Let IE be the AE-submodule of AE itself where IE(G) is the ideal ⟨te | e ∈
E(G)⟩ ⊂ AE(G) for each graph G. Call IE the edge ideal of AE. Then, kA =E
AE/IE is the graded AE-module taking each graph to the base field k in degree 0,
where all morphisms get sent to the identity and for each graph G, monomials of
AE(G) act by zero, and elements of K ⊆ AE(G) act by multiplication.
Lemma 2.5.3. If M is a finitely generated graded AE-module, then Tori(M,kA )E
is also a finitely generated graded AS-module for all i.
Proof. Let F• be a projective resolution of M where each term is finitely generated
as in Lemma 2.5.1. By Remark 2.5.2 we may assume F• is a projective resolution
by graded AE-modules. For each i, Fi ⊗ kA is isomorphic as an AE-module toE
the module Fi/IEFi taking a graph G to the AE(G)-module Fi(G)/IE(G)Fi(G).
50
Thus, Tori(M,kA ) is a subquotient of a finitely generated AE-module and is thus,E
finitely generated by Theorem 2.2.10.
2.5.1. Betti numbers
Given a finitely generated graded AE-module M , a graph G, and integers
i, a ­ 0, the ith graded Betti number of M in degree a with respect to G is
defined to be
βGi,a(M) := dimk(Tori(M,kA )(G))E a,
the dimension of the degree a part of Tori(M,kA )(G).E
Theorem 2.5.4. Let M be a finitely generated graded AE-module and fix i ­ 0.
Then, there exists an integer ni such that for any graph G of genus at most g,
βGi,a(M) = 0 for all a > ni.
Proof. By Lemma 2.5.3, we know that Ti := Tori(M,kA ) is a finitely generatedE
AE module. Therefore, we can find a finite list x1, . . . , xn of generators of Ti where
xj ∈ M(Gj). Moreover, we may assume that each xj is homogeneous of degree
dj. Then, define ni := max{d }nj j=1. We know that βGi,a(M) = dimk(Ti(G))a is
the number of generators of degree a in a minimal homogeneous generating set of
Ti(G) (see for instance [MS05, Lemma 1.32]). Thus, since the images of the xj
under maps induced by minor morphisms Gj → G contain a minimal homogeneous
generating set of Ti(G), if a > ni, we must have βGi,a(M) = 0.
For any fixed graph G, we can consider AE(G) = K[te|e ∈ E(G)] as an NE(G)-
graded K-algebra where te is in degree ve ∈ NE(G) which has a 1 in the e coordinate
and 0’s elsewhere. We call this grading the edge-grading on AE(G). Note that
51
kA is an edge-graded AE-module where kA (G) is concentrated in degree 0 ∈E E
NE(G). Thus, if M is an edge-graded AE-module, this induces an edge-graded AE-
module structure on Tori(M,kA ) for any i.E
Now, given an edge-graded AE-module M, a graph G, an integer i ­ 0, and
a ∈ NE(G), we can consider the ith edge-graded Betti number of M(G) in
degree a denoted βi,a(M(G)) where
βi,a(M(G)) = dimk(Tori(M,kA )(G))E a.
Let sum(a) denote the sum of the entries of a. We see that
∑
βGi,a(M) = βi,a(M(G)).
sum(a)=a
By Theorem 2.5.4, we have the following immediate result.
Corollary 2.5.5. Let M be a finitely generated edge-graded AE-module and fix
i ­ 0. Then, there exists an integer ni such that for any graph G with genus at most
g,
βi,a(M(G)) = 0 whenever sum(a) > ni.
2.5.2. Squarefree monomial ideals
Let us now consider the case where M is a finitely generated edge-graded
AE-module such that for each graph G, M(G) is a squarefree monomial ideal of
AE(G) = k[te | e ∈ E(G)]. In this case, using the Stanely-Reisner construction, one
can associate to M(G) a simplicial complex ∆M(G) on the set E(G). Namely, the
simplices of ∆M(G) are given by squarefree monomials of AE(G) not contained in
M(G). Now, let us identify each subset σ ⊆ E(G) with its indicator vector in NE(G)
52
so that each such subset of E(G) corresponds to a squarefree degree in the edge-
grading of AE(G). The commutative algebra of M(G) is intimately linked with the
topology and combinatorics of ∆M(G). See [Sta96] for an in-depth treatment of
this relationship. In particular, there is a nice relationship between the edge-graded
Betti numbers of M(G) and the simplicial complex ∆M(G) due to Hochster (see
[MS05, Corollary 5.12]).
Theorem 2.5.6 (Hochster’s formula). The nonzero Betti numbers of M(G) lie
only in square free degrees, namely degrees corresponding to subsets σ ⊂ E(G).
Furthermore,
β (M(G)) = dim H̃ |σ|−i−2i,σ K (∆M(G)|σ;K)
where ∆M(G)|σ = {τ ∈ ∆M(G) | τ ⊆ σ}.
Hochster’s formula together with Corollary 2.5.5 give the following.
Corollary 2.5.7. Fix i ­ 0. There exists an integer ni such that for any graph G
with genus at most g, if σ ⊆ E(G) with |σ| > ni, then
dim H̃ |σ|−i−2K (∆M(G)|σ;K) = 0.
As an application of the above results, we first define a specific AE-module
which will be denoted ILc . For a graph G, the edge ideal of G is the ideal I ⊆
k[tv|v ∈ V (G)] generated by monomials tvtw where v and w are connected by an
edge in E(G). Given a graph G, define the line graph of G denoted L(G) to be
the simple graph whose vertices are the the edges of G and two vertices of L(G)
are adjacent if and only if they share a vertex in G. Then, define the line graph
complexement of G, denoted Lc(G), to be the complement of L(G). Namely, the
53
vertices of Lc(G) are the edges of G and two vertices of Lc(G) are adjacent if and
only if they do not share a vertex in G.
Example 2.5.8. If G is the star graph - i.e. the tree with one vertex of degree
n and all other vertices of degree 1 - then Lc(G) is immediately seen to be a
disjoint collection of points. On the other hand, if G is the complete graph Kn,
then Lc(G) is the Kneser graph K(n, 2). indeed, certain authors refer to line graph
complements as being generalized Kneser graphs for this reason [DMM20].
Now, let ILc be the AE-module taking a graph G to the edge ideal of Lc(G).
We see that
ILc(G) = ⟨tetf |e, f ∈ E(G) don’t share a vertex⟩ ⊆ AE(G).
Indeed, ILc(G) is a squarefree monomial ideal of AE(G). Furthermore, if ϕ : G →
G′ is a minor morphism, and e, f ∈ E(G) don’t share a vertex, then ϕ∗(e), ϕ∗(f) ∈
E(G′) don’t share a vertex. Thus ILc does, in fact, give an AE-module of squarefree
monomial ideals.
Proposition 2.5.9. The AE-module ILc is finitely generated.
Proof. Note that ILc is a submodule of the edge ideal IE. We see IE is finitely
generated by the graphs G1 and G2, where G1 consists of two vertices and a single
edge connecting them and the graph G2 consists of a single vertex and a loop at
that vertex. This is because for any graph G and any edge e ∈ E(G), we can find a
minor morphism G→ Gi for some i ∈ {1, 2} such that e gets sent to the single edge
in Gi. Thus, Theorem 2.2.16 tells us that ILc is a finitely generated AE-module.
Applying Corollary 2.5.5 for any fixed i, we immediately get the existence
of a bound on the degrees of the nonzero edge-graded Betti numbers βi,a(ILc(G))
54
that is uniform as G ranges over all graphs. Moreover, Corollary 2.5.7 tells us about
the cohomology of some subcomplexes of the simplicial complexes ∆ILc (G) as G
ranges over all graphs. We note that ∆ILc (G) is precisely what is known as the flag
complex - or clique complex - of the line graph L(G).
2.6. Linear subspace arrangements of line graph complements
In this section we study the cohomology of a certain family of hyperplane
arrangement complements. In particular, we prove a finite generation result that
recovers and expands upon similar results present in [FWW19].
For a graph G let V (G) denote its set of vertices and as usual, let E(G)
denote its set of edges. Let d be a positive integer, and let k be either C or R. For
each e ∈ E(G), if v, w ∈ V (G) are the endpoints of e, let W ⊆ (kd)Ve be the
subspace ( )
W := {x ∈ kd
V
e |xv − xw = 0}.
In the definition of We, note that xv and xw are elements of kd. The collection
of all We as e ranges over the edges of G is a subspace arrangement called the
graphical arrangement of G denoted A (G). In the case where d = 1, each We is
a hyperplane of kV . In general, We is a codimension d subspace of (kd)V . Now, let
Conf(G,Kd) = (Kd)V − A (G) be the space obtained by removing the subspaces
of A (G). In the case where G is the complete graph Km, Conf(G,Kd) is the usual
ordered configuration space of m points in kd.
To each graph G, let us assign it to the space Conf(Lc(G), Kd) where Lc(G)
is the line graph complement defined in the previous section. We see that if ϕ :
G→ G′ is a minor morphism, then the inclusion ϕ∗ : E(G′)→ E(G) is an inclusion
55
V (Lc(G′))→ V (Lc(G)). Thus, ϕ∗ induces a natural projection
( ) c ( ) c ′
d V (L (G)) d V (L (G ))ϕ : k → k
Furthermore, ϕ∗ preserves pairs of edges that do not share a ve(rtex. This)yields a
natural inclu(sion E(Lc(G) ′)) → E(Lc(G)). Thus, if x ∈ Conf Lc(G),kd , then
ϕ(x) ∈ Conf Lc(G′),kd so ϕ restricts to a map
( ) ( )
Conf Lc(G),kd → Conf Lc(G′),kd .
The construction of the above map is functorial with respect to compositions of
minor morphisms. Thus, we have a functor from G¬g to the category of topological
spaces sending a graph G to Conf(Lc(G),kd). Then, taking the cohomology with Z
coefficients, gives a functor Gop¬g to the category of abelian groups.
Theorem 2.6.1. For any i, the Gop i c¬g-module H (Conf(L (−),kd);Z) is a finitely
generated Gop¬g-module where k is either C or R.
Proof. For a graph G, we know that topologically Conf(Lc(G),kd) is the
complement of a subspace arrangement over R where each subspace has real
codimension r = d when k = R and r = 2d when K = C. Thought of as
a real vector space, let U denote the ambient vector space for Conf(Lc(G),kd).
For each subspace Ũ ⊆ U that is an intersection of some of the subspaces of
the form Wf for f ∈ E(G), fix an orientation of the quotient space U/Ũ . In
[dLS01, Corollary 5.6], de Loungueville and Schultz give a presentation for the
cohomology ring of the complement of a subspace arrangement over R where each
subspace has the same codimension. This result tells says that the cohomology ring
H•(Conf(Lc(G),kd);Z) has the following presentation:
56
If r is even
• ∧• cH (Conf(Lc(G),kd);Z) ∼= ZE(L (G))/I
where the ideal I is generated by elements of the form
∑k
(−1)iϵ(e1, . . . , êi, . . . , ek)e1 ∧ · · · ∧ êi ∧ · · · ∧ ek
i=0
for all subsets {e1, . . . , ek} ⊆ E(Lc(G)) that form a cycle in Lc(G). Here,
ϵ(e1, . . . , ek) is a the sign of the determinant, with respect to our choices of
orientations, of the isomorphism
U/(We1 ∩ · · · ∩We )→ U/We ⊕ · · · ⊕ U/Wk k e1
given by the canonical projections onto each summand. If r is odd
H•
c
(Conf(Lc(G),kd);Z) ∼= Sym• ZE(L (G))/I
where the ideal I is generated by elements of the form
∑k
e2 and (−1)iϵ(e1, . . . , êi, . . . , ek)e1 · · · êi · · · ek
i=0
for any e ∈ E and all subsets {e , . . . , e } ⊆ E(Lc1 k (G)) that form a cycle in Lc(G).
Here, ϵ(e1, . . . , ek) is defined as in the even case. Whether r is even or odd, the
generator e is in degree r − 1 for any edge e ∈ E(G).
We know cycles of Lc(G) correspond to minimal sets {f1, . . . , fk} of edges in
E(G) that satisfying the condition that fi and fi+1 do not share a vertex and f1
and fk do not share a vertex. Given a minor morphism ϕ : G → G′, the inclusion
57
ϕ∗ : E(G′) → E(G) preserves pairs of edges that don’t share a vertex, and so
the induced map E(Lc(G′)) → E(Lc(G)) sends cycles to cycles. Furthermore,
the inclusion ϕ∗ : E(G′) → E(G) gives a natural inclusion of the ambient real
vector space U ′ for Conf(Lc(G′), Kd) into the ambient real vector space U for
Conf(Lc(G),kd). Thus, if ϕ∗(f ′) = f for f ′ ∈ E(G′), then under this inclusion
Wf ′ ⊆ Wf . Thus, given orientations on all the quotient spaces U/Ũ where Ũ
is an intersection of some of the Wf for f ∈ E(G), fixing an orientation of
U/U ′ determines all of the orientations of U ′/Ũ ′. Therefore, the presentation for
H•(Conf(Lc(G)),Cd);Z) given above, is compatible with minor morphisms.
From this presentation, we see that for each i, the Gop¬g module
H i(r−1)
c
(Conf(Lc(−),Cd);Z) is a quotient of the ith tensor power of ZE(L (G)),
⊗i
ZE(Lc(−)).
j=1
c
Recall the edge module E from 2.4. Notice that ZE(L (−)) is the submodule of
c
the second tensor power of the edge module E⊗2, where ZE(L (G)) is generated
by elements of the form fi ⊗ fj where fi, fj ∈ E(G) do not share a vertex.
We know that E⊗2 is finitely generated by 2.4.1. We have shown that, for any i,
H i(Conf(Lc(−),kd;Z) is a subquotient of a finitely generated Gop¬g-module so the
result follows from Theorem 1.1.1.
Remark 2.6.2. If d = 1, Conf(Lc(G),k) is the complement of a hyperplane
arrangement in kV . When k = C, H•(Conf(Lc(G), K)) is just the Orlik-Solomon
algebra of the complex hyperplane arrangement where the generators live in degree
1. If d > 1, the above presentation shows that H•(Conf(Lc(G), Kd)) is still
isomorphic to the aforementioned Orlik-Solomon algebra, only now the generators
58
live in degree 2d − 1. When k = R, H•(Conf(Lc(G), K)) is the Cordovil algebra
of the real hyperplane arrangement. If d is odd, then H•(Conf(Lc(G), Kd)) is
isomorphic to H•(Conf(Lc(G), K)), only now the generators live in degree d− 1.
Example 2.6.3. Let a, b ­ 1 and let G be the graph with two vertices of degrees
a+1 and b+1, respectively, connected to one another by a single edge. Put another
way, G is two copies of star graphs, of degrees a and b, whose central vertices have
been glued together by a new edge. Then Lc(G) is easily seen to be a complete
bipartite graph Ka,b, disjoint union a point. In this case, we have
Conf(Lc(G),Cd) = Z̃D da+b(C )× Cd
where Z̃D (Cda+b ) are the colored configuration spaces considered by Farb Wolfson
and Wood in [FWW19], with D being the vertices of the complete bipartite graph
colored in the obvious way. Observe moreover that the graph G can be seen as
an edge with a and b leaves sprouted on its two vertices, respectively. Therefore,
Proposition 2.6.4 below implies that Theorem 2.6.1 can be seen as a generalization
of the stabilization phenomena observed by [FWW19].
The following proposition follows directly from [PR19a, Corollaries 4.5 and
4.7, [PR19a]].
Proposition 2.6.4. Let M be a finitely generated Gop¬g-module over a field k, and
let G be a fixed graph, with a distinguished collection of vertices v1, . . . , vr, and
edges e1, . . . , es. We write G(n1,...,nr) for the graph obtained from G by attaching
ni leaves to the vertex vi, and G(m1,...,ms) for the graph obtained from G by
subdividing the edge ej, mj times. Then there exist polynomials P1(n1, . . . , nr) and
59
P2(m1, . . . ,ms) such that
dim M(G(n1,...,nr)k ) = P1(n1, . . . , nr)
dimkM(G(m1,...,ms)) = P2(m1, . . . ,ms),
for all vectors (n1, . . . , nr) and (m1, . . . ,ms) whose each component is sufficiently
large.
60
CHAPTER III
CATEGORICAL VALUATIVE INVARIANTS OF MATROIDS
This chapter was written in collaboration with Nicholas Proudfoot and
Lorenzo Vecchi.
3.1. Background on matroids
The primary objects of study in this section are matroids. Let E be a finite
set. Often we will consider E = [n] := {1, 2, . . . , n} as we only care about E up to
bijections of sets. A matroid M on E is a pair M = (E,B) where B is a collection
of subsets of E satisfying the following properties:
(B1) B ̸= ∅
(B2) If B1, B2 ∈ B and x ∈ B1 \ B2, then there exists y ∈ B2 \ B1 such that
(B1 \ {x}) ∪ {y} ∈ B.
The set E is called the ground set of M and the elements of B are the
bases of M .
Example 3.1.1. Let V be a vector space and E = {v1, . . . , vn} be any spanning
set of vectors in V . Then, taking B to be the subsets of E that are bases of the
vector space V , we see that B satisfies property (B1) since E is a spanning set and
satisfies property (B2) by the Steinitz exchange lemma so M = (E,B) indeed forms
a matroid on E.
It is a well known fact that properties (B1) and (B2) imply that all elements
of B have the same cardinality. The rank of a matroid M is the cardinality of any
basis of M .
61
Exam( p)le 3.1.2. Let E be finite set and fix a nonnegative integer r ¬ |E|. Let
B = E , that is, B consists of all subsets of E with cardinality r. Clearly B satisfies
r
property (B1) since r ¬ |E|. Furthermore for any B1, B2 ∈ B, if x ∈ B1 \ B2, we
can pick any y ∈ B2 \ B1. Then, (B1 \ {x}) ∪ {y} will be a subset of E with size
r and therefore in B. Thus, B satisfies property (B2) so (E,B) is a matroid called
the uniform matroid of rank r on E and it is denoted Ur,E. In the case where
E = [n] for some positive integer n, we will denote this matroid as Ur,n.
Given a matroid M = (E,B), a subset I ⊆ E is called independent if I ⊆ B
for some basis B ∈ B. In the case where M is a matroid as in Example 3.1.1, I
is independent if and only if it is a linearly independent set of vectors. A subset
D ⊆ E is called dependent if it is not independent. A circuit C of M is a minimal
dependent subset of E. Given a subset S ⊆ E the rank of S in M denoted rkM(S)
or just rkS when the matroid in question is clear, is the cardinality of the largest
independent subset of S. Note that the rank of a matroid M is equivalent to the
rank of the entire groundset E. A flat of M is a subset F ⊆ E that is maximal for
its rank. That is, F is a flat of M if for any x ∈ E \ F , rk(F ) < rk(F ∪ {x}). The
collection of flats of a matroid is closed under intersections and the poset of flats of
a matroid ordered by inclusion forms a lattice graded by rank.
We have chosen to defined a matroid on the ground set E in terms of its
bases, but it turns out that one can define a matroid in terms of any one of its
independent sets, its dependent sets, its circuits, its rank function, or its flats. For
simplicity we will stick with our definition in terms of bases.
62
3.1.1. Matroid operations
We now recall a few well known ways of building new matroids from existing
ones. Let M = (E,B) be a matroid. For a subset S ⊆ E the restriction of M
to S, denoted MS is the matroid whose ground set is S and whose set of bases is
{B ∩ S | B ∈ B}. Fix a maximal independent subset I of S. The contraction of M
by S, denoted MS is the matroid whose ground set is E \ S and whose set of bases
is {B′ ⊆ E \ S | B′ ∪ I ∈ B}. It turns out that MS does not depend on our choice of
I.
Given matroids M1 = (E1,B1) and M2 = (E2,B2), the direct sum of M1 and
M2, denoted M1⊕M2 is a matroid whose ground set is E1⊔E2 and whose bases are
of the form B1 ⊔ B2 for some B1 ∈ B1 and B2 ∈ B2. A matroid M is disconnected
if M = M1 ⊕M2 for matroids M1 and M2 with nonempty ground sets. Otherwise,
M is connected. Every matroid M can be written uniquely as a finite direct sum
of connected matroids M1, . . . ,Mn with nonempty ground sets. Here, M1, . . . ,Mn
are called the connected components of M . Notice that if M is a matroid on E
such that M = M1 ⊕M2, if S ⊆ E is the ground set of M1, then MS = M1 and
MS =M2.
3.2. Matroid polytopes and valuative invariants
Let E be a finite set and fix a real vector space RE with a distinguished
basis {e } . A polytope in REi i∈E is defined to be the convex hull of finitely many
points in RE, that is, the unique minimal convex subset of RE containing each
of those finitely many points. Equivalently, the convex hull of p1, . . . , pn, denoted
Conv(p1, . . . , pn) is given by the set
63
{∑n ∑ }n
Conv(p1, . . . pn) = λipi | λi ­ 0 for each i and λi = 1 .
i=1 i=1
The dimension dimP of a polytope P is the dimension of the smallest
Euclidean subspace of RE that contains it. A polytope P is homeomorphic to a
closed ball of the same dimension. A face of a polytope P is any intersection of P
with a halfspace of RE that contains no points in the interior of P . Note that each
face of a polytope is itself a polytope and each point on the boundary of a polytope
is contained in the interior of a unique face of the polytope. The zero dimensional
faces of a polytope are called vertices, the 1-dimensioal faces are called edges, and
the faces of codimension 1 are called f∑acets.
Given a subset S ⊆ E, let e ES = i∈S ei ∈ R be the indicator vector of S. For
a matroid M = (E,B), its base polytope denoted PM is the set
PM = Conv ({eB | B ∈ B}) .
The collection of points eB for B ∈ B are exactly the vertices of PM . Thus,
a matroid is determined by its base polytope. We can see that PM lies in the
hyperplane of RE where the coordinates sum to the rank of M . It is well known
that the dimension of PM is equal to the cardinality of E minus the number of
connected components of M . Furthermore, each nonempty face of PM is a polytope
of the form PM ′ for some matroid M ′.
Example 3.2.1. Consider the matroid U2,4. Its ground set is E = {1, 2, 3, 4}
and every subset of E of size 2 is a basis so PU2,4 is the convex hull of the points
(1, 1, 0, 0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), and (0, 0, 1, 1, ) in R4 so PU2,4 .
64
See Figure 1. Note that U2,4 is a connected matroid, so its basis polytope is 3-
dimensional.
(1, 1, 0, 0)
(1, 0, 0, 1)
(1, 0, 1, 0) (0, 1, 0, 1)
(0, 1, 1, 0)
(0, 0, 1, 1)
FIGURE 1. The base polytope for the matroid U2,4 forms an octahedron.
Let Mat(E) be the free abelian group generated by matroids on E. For each
matroid M on E, let 1M : RE → Z be the indicator function of PM defined
below: 

1 if x ∈ PM
1M(x) =  .0 otherwise
We have a group homomorphism from Mat(E) to the group of functions RE →
Z where M gets sent to 1M . Let I(E) < Mat(E) denote the kernel of this
homomorphism and let Val(E) = Mat(E)/I(E). We call Val(E) the valuative
group on E.
Let A be an abelian group. A homomorphism Mat(E) → A is called a
valuative matroid invariant if f factors through Val(E).
65
3.2.1. Matroid polytope decompositions
In order to determine whether a homomorphism f : Mat(E) → A is
valuative, one needs to show that f sends I(E) to 0. It turns out I(E) is generated
by decompositions of matroids which we now describe. Given a matroid M on the
ground set E, a decomposition of M is a collection N of matroids on E satisfying
the following:
– If N ∈ N , and N ′ is a matroid on E such that PN ′ is a face of PN , then
N ′ ∈ N .
– If N,N ′ ∈ N , then PN ∩ PN ′ is a face of both PN and PN ′ .
⋃
– PM = PN .
N∈N
Equivalently, a decomposition of M is a collection of matroids whose polytopes
form the closed cells in a cell decomposition of M .
The matroids in N are called faces of N . A face N ∈ N is internal if PN
is not contained in the boundary of PM . We write Nint for the set of internal faces
of N . Note that N can be recovered from Nint by including all matroids which
correspond to faces of PN for each N ∈ Nint.
Example 3.2.2. Given any matroid M , the collection N consisting of M itself
and all matroids that correspond to faces of PM is a decomposition of M called the
trivial decomposition of M . In this case Nint = {M}.
Example 3.2.3. Here we describe the simplest nontrivial matroid decomposition.
Let E = {1, 2, 3, 4}, and consider M = U2,4 the uniform matroid of rank 2 on
E. Let N1 be the matroid whose bases are all subsets of size 2 except for {3, 4},
let N2 be the matroid whose bases are all subsets of size 2 except for {1, 2} and
66
let N1,2 be the matroid whose bases are all subsets of size 2 except for {1, 2} and
{3, 4}. Then, Nint = {N1, N2, N1,2} form the internal faces for a decomposition N of
M . See Figure 2. In addition to the internal faces, N also consists of the matroids
corresponding to the eight triangular facets of PM , the twelve edges of PM , and the
six vertices of PM .
12
PN1
12
14
13 24
14 23
14
PM 13 24 13 24 PN23 1,2
23 14
13 24
23
PN
34 2
34
FIGURE 2. As in Example 3.2.3, the base polytope for the matroid M is given
on the left. The base polytopes for the internal faces of a decomposition of M
are given on the right. Here, the vertices are labeled with the basis that they
correspond to.
The following theorem follows from [AFR10, Theorem 3.5] and [DF10,
Corollary 3.9] and says that I(E) is generated by decompositions of M .
Theorem 3.2.4. The subgroup I(E) < Mat(E) is the subgroup generated by
elements of the form
dim∑PM ∑
(−1)dimPMM − (−1)k N
k=0 N∈Nint,
dimPN=k
as M ranges over all matroids on E and N ranges over all decompositions of M .
67
Example 3.2.5. When N is the trivial decomposition of a matroid M , the
corresponding generator is M −M = 0 the identity in Mat(E).
Example 3.2.6. Recall the decomposition N described in Example 3.2.3. In this
case, the corresponding generator of I(E) is given by
−M +N1 +N2 −N1,2.
3.2.2. Relaxation
We next review a large class of matroid decompositions that will be a source
of examples in Section 3.5. Let M be a matroid on the ground set E. A flat F ⊆ E
is called stressed if the deletion MF and the contraction MF are both uniform
matroids. Given a stressed flat F of rank r, Ferroni and Schröter define cusp(F ) to
be the collection of k-subsets S ⊂ E such that |S ∩ F | ­ r + 1. If B is the set
of bases of M , they prove that B ∪ cusp(F ) is the set of bases for a new matroid
Rel(M,F ), which they call the relaxation of M with respect to F [FS, Theorem
3.13]. If F is a circuit-hyperplane, then cusp(F ) = {F}, and this coincides with the
classical notion of relaxation in Matroid theory. See [Oxl11, Proposition 1.5.14]. If
F is a hyperplane, this coincides this coincides with the notion of relaxation of a
stressed hyperplane studied in [FNV22].
Let F be a rank r stressed of a matroid M on E. Let k be the rank of M . By
definition of stressed, we necessarily have that M FF = Uk−r,E\F and M = Ur,F .
Consider the matroid
Πr,k,E,F :=MF ⊕MF = Uk−r,E\F ⊕ Ur,F .
68
Notice that F is a stressed flat of F . Relaxing F in Πr,k,E,F gives the matroid
Λr,k,E,F := Rel(Πr,k,E,F , F ).
The following theorem is proven in [FS, Theorem 5.5].
Theorem 3.2.7. Let M be a matroid of rank k on E and let F be a stressed flat
of M of rank r. Then, the base polytope for Πr,k,E,F is the intersection of the base
polytopes for Λr,k,E,F and M and is a common face of both. Moreover, the base
polytope for Rel(M,F ) is the union of the base polytopes for Λr,k,E,F and M .
In other words, Theorem 3.2.7 says that the matroids M and Λr,k,E,F
along with all matroids corresponding to faces of their base polytopes forms a
decomposition of Rel(M,F ).
Example 3.2.8. Consider the matroid N1,2 from Example 3.2.3. It has two
stressed flats F = 1, 2 and G = 3, 4. In fact, N1,2 = Π2,2,E,F = Π2,2,E,G. The
relaxation Rel(N1,2, F ) is equal to the the matroid N1 from Example 3.2.3 and the
decomposition from Theorem 3.2.7 is trivial. The flat G remains a stressed flat in
N1 and the relaxation Rel(N1, G) gives the matroid U2,4 and the decomposition
coming from this relaxation is exactly the decomposition of U2,4 from Example
3.2.3. Observe that starting with N1,2 we could have relaxed G first and then
relaxed F . Doing so would the same final decomposition of U2,4 in the end.
Example 3.2.8 suggests a slight generalization of Theorem 3.2.7 in which we
relax more than one stressed flat at once. Indeed, the following Proposition tells us
we can do just that.
Proposition 3.2.9. Let F1 and F2 be distinct rank r stressed flats of M . Then, the
flat F2 is a stressed flat of rank r in Rel(M,F1).
69
Proof. Let M̃ denote Rel(M,F1). Because F1 ̸= F2, the intersection F1 ∩ F2
must be a flat of M of rank < r. Since F1 is stressed, every size r subset of F1 is
independent, so we conclude that |F1 ∩ F2| < r. Thus, by [FS, Proposition 3.17], the
rank of F2 in M̃ remains r.
Every basis of M is still a basis of M̃ . Thus, every basis of MF2 is still
independent in M̃F2 and every basis of M
F2 is independent in M̃F2 . The fact that
F2 still has rank r in M̃ implies that MF2 and M̃F2 have the same rank. Similarly
MF2 and MF2 have the same rank. This means M̃F2 and M̃
F2 must be uniform
because MF2 and M
F2 are uniform.
To see that F2 is still a flat of M , observe that for any size r subset S ⊆ F2
and any i ∈ E \ F2, the set S ∪ i is independent in M and thus also in M̃ .
Proposition 3.2.9 tells us that given a collection of stressed flats of M all with
rank r, we may relax all of them one by one. Due to how relaxation works, the
order in which we relax does not matter. This is because whenever F is a stressed
flat of M , the elements of cusp(F ) are not bases in M . Thus, the sets of bases we
add in our sequence of relaxations are all disjoint. Therefore, we may instead think
of this process as relaxing all of these flats at once.
We will be interested in the following special case of this. Suppose that Γ is
a finite group that acts on E by permutations, with the property that Γ fixes the
matroid M . Let F be a stressed flat of M , and let F := {γF | γ ∈ Γ} be the
set of all stressed flats in the same orbit as F . Now define RelΓ(M,F ) to be the
relaxation of M with respect to all of the elements of F . More precisely, if B is the
collection of bases for M , then the collection of bases for RelΓ(M,F ) is
⋃
B ∪ cusp(G).
G∈F
70
Let N be the collection of matroids consisting of M , Λr,k,E,G for all G ∈ F ,
and all matroids whose polytopes are faces of PM or PΛ . The followingr,k,E,G
generalization of Theorem 3.2.7 follows from our discussion above along with
repeated applications of Theorem 3.2.7, once for each G ∈ F .
Theorem 3.2.10. The collection N is a decomposition of RelΓ(M,F ). If M =
Πr,k,E,F , then N is the trivial decomposition of Λr,k,E,F . If not, then the only
internal faces of N are M , Λr,k,E,G for all G ∈ F , and Πr,k,E,G for all G ∈ F .
Example 3.2.11. Let Γ = D4 act on the matroid N1,2 from Example 3.2.3 by
symmetries of the square PN1,2 . For F = {1, 2}, F = {F,G} where G = {3, 4}.
We could also achieve this by setting Γ equal to the subgroup S2 ⊂ D4, with the
nontrivial element γ ∈ S2 acting on E by the formula formula γ(1) = 3 and γ(2) =
4.
3.3. Matroid categories
Our goal in this section is to categorify the notion of a valuative matroid
invariant.
Before we can define the categories we will work with, we need a notion of a
map between matroids. Let E be a finite set. Given matroids M and M ′ on E, a
bijective weak map from M to M ′ is a bijection σ : E → E such that whenever
S ⊆ E is an independent set of M ′, we have that ϕ−1(S) is a independent set of M .
In the case when M and M ′ have the same rank, this is equivalent to requiring that
the preimage of a basis of M ′ is also a basis of M or said another way, that
PM ′ ⊆ ϕ(PM)
71
where ϕ(PM) is obtained from PM by permuting the coordinates in RE via ϕ. We
will only be concerned with bijective weak maps between matroids on the same
rank, thus whenever we use the term weak map, we will assume that it is a weak
map between two matroids of the same rank.
Let M(E) be the category whose objects are matroids on E and whose
morphisms are bijective weak maps between matroids of the same rank. We will
work with M(E) in Section 3.5. For now, let us consider the subcategory Mid(E)
of M(E) whose objects are the same as those of M(E) but whose morphisms
are only the weak maps between matroids of the same rank given by the identity
map idE on E. In otherwords, in M (E), given two matroids M and M ′id if
PM ′ ⊆ PM we have a unique morphism from M to M ′. Let C be the category
of finite dimensional vector spaces over Q or the category of finite dimensional
graded vector spaces over Q. A categorical invariant of matroids is any functor
Φ :Mid(E)→ C.
Example 3.3.1. Let C be the category of finite dimensional vector spaces over
Q and let τ : Mid(E) → C be the functor sending each matroid M to Q and
all morphisms to the identity map on Q. We will call τ the trivial categorical
matroid invariant.
Example 3.3.2. Let C be the category of finite dimensional graded vector spaces
over Q. There is a functor OS : Mid(E) → C that takes a matroid M to its Orlik-
Solomon algebra OS(M). The generators of OS(M) correspond to elements of the
ground set E. idE is a weak map of matroids M → M ′, we get a surjection of
algebras (and thus a surjection of graded vector spaces) OS(M) → OS(M ′) sending
the generator corresponding to an element i ∈ E to the generator of OS(M ′) also
corresponding to i. See section 3.4 for a detailed treatment of this example.
72
3.3.1. The category M∧id(E)
Let C be the category of finite dimensional (graded) vectors spaces over
Q and let Φ : Mid(E) → C be a categorical matroid invariant. In order to
define what it means for Φ to be valuative, we need a way to “upgrade” Φ to be
a triangulated functor from a triangulated matroid category to D(C), the bounded
derived category of C.
If M is a matroid on E, consider the vector space over Q given by
A = Span{x− y | x, y ∈ P } ∩QEM M .
If idE is a weak map M → M ′, then P ′ ⊆ P and so A′M M M is a subspace of AM .
Thus, we may define the 1-dimensional vector space
Q(M,M ′
∧dimPM−dimPM′) = (AM/AM ′).
Notice that if M,M ′, and M ′′ are matroids on E with PM ′′ ⊆ PM ′ ⊆ PM , then the
wedge product gives a canonical isomorphism
∧ : Q(M,M ′)⊗Q(M ′,M ′′)→ Q(M,M ′′). (3.3.1)
If id is not a weak map M → M ′E , define Q(M,M ′) to be the trivial vector space.
Now let us define a new category M∧id(E). The objects of M∧id will be formal direct
sums of objects of M∧id(E). For matroids M , M ′ on E, take
Hom ′M∧ (E)(M,M ) = Q(M,M ′).id
73
A morphism between formal direct sums of matroids will be given by matrices
whose entries consist of morphisms between the individual matroids and
composition is given by matrix multiplication in conjunction with the wedge
product in Equation 3.3.1. Notice that the category M∧id(E) is an additive category.
Remark 3.3.3. The reason we need the category M∧id(E), is because when we
later define what it means for a categorical matroid invariant Φ to be valuative,
we want our invariants to respect symmetries of M that preserve decompositions
N of M . That is, permutations of E that preserve the set of base polytopes of N
under the action on the ambient space RE. The issue that can arise is that such a
symmetry may reverse the orientation on a base polytope and thus, if we are not
careful with our definitions, we will be restricted to symmetries which also preserve
orientations of the polytopes. Intuitively, the morphisms in Mid(E) keep track of
the orientations of polytopes relative to each other. For instance, if PN ′ is a facet
of P , then Q(N,N ′N ) is naturally identified with AN/AN ′ in which is naturally
oriented by the class of the outward normal unit vector of PN ′ in PN .
With Remark 3.3.3 in mind, in order to define what it means for Φ to be
valuative, we want a canonical way to “upgrade” Φ to an additive functor from Φ∧ :
M∧id(E) → C. At first, one may naively try to identify Mid(E) with a subcategory
of M∧id(E) and extend Φ linearly to define Φ∧. However, the 1-dimensional vector
space Q(M,M ′) only admits a canonical basis if dimM = dimM ′ or if M ′ is a facet
of M so most nontrivial weak maps in Mid(E) would need to be identified with
trivial morphisms in M∧id(E). Thus, this strategy only works for if Φ is trivial on
most morphisms. In the next section, we describe how define Φ∧ in general.
74
3.3.2. The determinant functor
Let C be the category of finite dimensional (graded) vector spaces over Q. In
this section, we define an additive functor Det : M∧id(E) → C. For any matroid M
on E, let ∧dimP
Det(M) = M A∗M .
For a nontrivial morphism σ in M∧id(E), i.e. a nontrivial element σ ∈ Q(M,M ′), we
have an isomorphism of vector spaces
∧ ∧
(− ∧ dimP ′ dimPσ) : M ∗ → MA ∗M ′ AM
given by taking the wedge product with σ. Let Det(σ) : Det(M) → Det(M ′) be the
dual of this isomorphism and extend linearly to define Det on all other morphisms
of M∧id(E).
Let Φ : Mid(E) → C be a categorical matroid invariant. Let Φ∧ : M∧id(E) →
C be the functor defined by Φ∧ = Φ ⊗ Det. Concretely, for a matroid M on E,
Φ∧(M) = Φ(M)⊗Det(M) and given
σ ∈ HomM∧ (E)(M,M ′),id
we set
Φ∧(σ) = Φ(idE)⊗Det(σ) : Φ∧(M)→ Φ∧(M ′).
Given a categorical invariant Φ : Mid(E) → C, by tensoring with Det, we
have built a functor Φ∧ : M∧id(E) → C. Let Kid(E) be the homotopy category
of bounded chain complexes in M∧id(E). The category Kid(E) is triangulated and
its Grothendieck group is naturally isomorphic to Mat(E). We know that Φ∧
75
naturally extends to a triangulated functor Kid(E) → D(C) which we will also call
Φ∧. Thus, passing to Grothendieck groups, this induces a group homomorphism
Φ∗ : Mat(E) → Z. In this case, we will say that Φ categorifies the matroid
invariant Φ∗.
Example 3.3.4. The trivial categorical invariant τ from example 3.3.1 categorifies
the trivial invariant Mat(E)→ Z sending each matroid to 1 ∈ Z.
Example 3.3.5. The dimension of the ith graded piece of the Orlik-Solomon
algebra OS(M) is the coefficient of the degree i term in the Poincaré polynomial
of a matroid. Thus, the categorical invariant OS from example 3.3.2 categorifies the
invariant sending a matroid to its Poincaré polynomial in Z[t].
3.3.3. Valuative categorical matroid invariants
We are finally ready to define what it means for a categorical matroid
invariant to be a valuative. Let N be a decomposition of the matroid M on E and
let d = dimPM . We define the chain complex C•(N ) in M∧(E) as follows.
– Let Ck(N ) = 0 for k < 0 or k > d+ 1.
⊕
– For 0 ¬ k ¬ d, let Ck(N ) = N .
N∈Nint
dimPN=k
– Let Cd+1(N ) =M .
If N ∈ Nint with dimPN = d, then AM/AN is trivial so Q(M,N) is canonically
isomorphic to Q. Thus, define the differential Cd+1(N )→ Cd(N ) to be the diagonal
map. For N,N ′ ∈ Nint with dimPN = k and dimPN ′ = k − 1, if PN ′ is not a facet
of P , then set the N → N ′N component of the differential Ck(N ) → Ck−1(N ) to 0.
If PN ′ is a facet of PN , then AN/AN ′ is 1-dimensional and thus equal to Q(N,N ′).
76
In this case, set the N → N ′ component of the differential Ck(N )→ Ck−1(N ) to be
the class of the outward unit normal vector to PN ′ inside of PN in the quotient
space AN/AN ′ = Q(N,N ′). It is straightforward to check that the differential
squares to 0.
Example 3.3.6. Let N be the trivial decomposition of M . The only element of
Nint is M itself. Thus, the chain complex C•(N ) looks like
0→ 1M →− M → 0.
Recall that Q(M,M) can be canonically identified with Q.
Example 3.3.7. Consider the decomposition N of M = U2,4 given in Example
3.2.3. Then, the complex C•(N ) looks like
N
1 1
0 M ⊕ N1,2 0
1
N2
where the maps N1 → N1,2 and N2 → N1,2 correspond to the respective outward
normal unit vector.
A categorical invariant Φ : Mid(E) → C is valuative if for every
decomposition N of a matroid M on E, the chain complex Φ∧(C•(N )) is an exact
chain complex in C. Equivalently, let I(E) be the full triangulated subcategory of
Kid(E) spanned by the complexes C•(N ) for all decompositions N of matroids on
E. Let V(E) be the triangulated category quotient of Kid(E) by I(E). We see that
a categorical invariant Φ is valuative if and only if Φ∧ : Kid(E) → D(C) descends to
a functor V(E)→ D(C).
77
Recall that the Grothendieck group of Kid(E) can be identified with Mat(E).
Under this identification, the Euler characteristic of C•(N ) is exactly the generator
of I(E) corresponding to N as in Theorem 3.2.4. Thus, the Grothendieck group
of I(E) contains I(E) which means that the Grothendieck group of V(E) is a
quotient of Val(E). If Φ : M(E) → C is a valuative categorical invariant, then
the induced matroid invariant Φ∗ : Mat(E)→ Z descends to Val(E) and is therefore
valuative.
Recall the trivial categorical invariant τ from Example 3.3.1.
Proposition 3.3.8. The categorical invariant τ is valuative.
Proof. Let d = dimPM and let C¬d(N ) be the complex obtained from C•(N )
by setting the degree d + 1 term (i.e. the term corresponding to M itself) to 0.
Recall that a decomposition of a matroid gives a cell decomposition of PM and PM
is homeomorphic to a closed ball of dimension d. The terms in C¬d(N ) correspond
to the internal faces of N and we observe that τ∧(C¬d(N )) is the cellular chain
complex of a cell decomposition of a d-dimensional ball relative to its boundary.
Thus, the homology of τ∧(C¬d(N )) is one dimensional and concentrated in degree
d.
We know that τ∧(C¬d(N )) is a subcomplex of τ∧(C•(N )) and the
corresponding quotient complex is Q[−d − 1], the complex consisting of a single
copy of Q in degree d+ 1. Thus, we have an exact sequence of chain complexes
0→ τ∧(C¬d(N ))→ τ∧(C•(N ))→−
q Q[−d− 1]→ 0
where the degree d + 1 part of q is an isomorphism q ∧d+1 : τ (M) → Q. The
map qd+1 determines an orientation Ω of PM . We know that Q[−d − 1] is equal
78
to its homology. Meanwhile, we showed that the homology of τ∧(C¬d(N )) can
be identified with the relative homology of the pair Hd(PM , ∂PM) which is 1-
dimensional and concentrated in degree 1. In the long exact sequence on homology
groups, the boundary map takes the generator of Q[−d − 1] to the orientation class
of Hd(PM , ∂PM) determined by Ω. This map is an isomorphism which tells us that
τ(CΩ• (N )) is trivial.
3.4. The Orlik–Solomon functor
One of the most important matroid invariants is the characteristic
polynomial. The coefficients of the characteristic polynomial equal the dimensions
of the graded pieces of Orlik-Solomon algebra. In this way, the Orlik-Solomon
algebra categorifies the characteristic polynomial. In this section we recall the
definition of the Orlik-Solomon algebra of a matroid and we prove that the
categorical matroid invariant OS taking a matroid to its Orlik-Solomon algebra
is valuative.
Let E be a finite and let M be a matroid on E. Fix a distinguished basis
{xi|i ∈ E} of the vector space QE and consider the exterior algebra Λ(QE). We will
view Λ(QE) as a graded algebra over Q where the generator xe is in degree 1 for
each e ∈ E. For a subset S = {s1, . . . , sk} of E, define wS ∈ Λ(Qn) as
∑k
wS = (−1)ixs1 · · · x̂s · · ·x .i sk
i=1
Let J(M) ⊆ Λ(Qn) be the ideal generated by elements of the form wS where S is a
dependent set in M . Notice that the element wS depends on the ordering of S only
up to sign. Thus the ideal J(M) is independent of the choices of orderings of the
79
dependent sets. The Orlik-Solomon algebra of M , denoted OS(M), is the quotient
Λ(QE)/J(S).
For matroids M and M ′ on E, notice that if idE is a weak map form M to
M ′, then every independent subset of M ′ is also independent in M . Equivalently,
every dependent set of M is also dependent in M ′. This means J(M) is contained
in J(M ′) and so we have a canonical surjection OS(M) ↠ OS(M ′) sending the
generator xe ∈ OS(M) to the generator xe ∈ OS(M ′) for each e ∈ E. Thus, we have
a categorical invariant OS : M(E) → C where C is the category of graded vector
spaces over Q which sends a matroid M to OS(M) viewed as a graded vector space
where the grading is inherited by the grading on Λ(QE).
By [OT92][Theorem 3.43], the Orlik-Solomon algebra of a matroid admits a
concrete (non-canonical) basis depending on an ordering of the ground set which we
now describe. Let us fix an identification of E with the set [n] = {1, . . . , n} (i.e. fix
a linear order on E). For any subset S = {i1, . . . , ik} ⊆ E with i1 < · · · < ik, define
the monomial xS ∈ Λ(QE) as
xS = xi1 · · · xi .k
Notice if S is a dependent set in M , then xS ∈ J(S) because
∑k
x = x − x (−1)jS S i1 (xi1 · · · x̂i · · ·xj i )k
∑ j=2k
= −xi1 (−1)j(xi1 · · · x̂i · · ·xj i )k
j=1
= −xi1wS.
Thus, the image of xS in OS(M) is 0. A broken circuit of M is a subset S ⊆ E =
[n] that can be obtained by removing the minimal element from a circuit. A non-
80
broken circuit set (nbc-set for short) is a subset of E that does not contain a
broken circuit. Let nbc(M) denote the collection of nbc-sets of M . Note that both
broken circuits and nbc-sets are necessarily independent sets as neither can contain
a circuit of M . The images in OS(M) of the set of monomials
{xS ∈ Λ(QE) | S ∈ nbc(M)}
forms a basis for OS(M) as a vector space [OT92, Theorem 3.43]. We will refer to
this basis as the nbc-basis of OS(M).
Now, let us consider a new grading on Λ(QE) where the degree of xi is i
for each i ∈ E. This grading depends on the identification E = [n]. Also,
by [OT92, Theorem 3.43], this grading induces a filtration on OS(M) where,
given S ∈ nbc(M), the nbc-basis element xS lies in the ith filtered piece if its
degree in Λ(QE) is ¬ i, and the associated graded ring grOS(M) under this
filtration is isomorphic to Λ(QE)/J ′(M) where J ′(M) is the ideal generated by
{xS | S is a circuit}.
If idE is a weak map from M → M ′, then any circuit of M is also dependent
in M ′. This means that every broken circuit in M contains a broken circuit of M ′
so if S ∈ nbc(M ′), then S ∈ nbc(M). Thus, the corresponding map OS(M) →
OS(M ′) is filtered with respect to the filtration described above so it induces a map
grOS(M) → grOS(M ′). For S ∈ nbc(M), this map sends an nbc-basis element
xS ∈ grOS(M) to xS ∈ grOS(M ′) is S ∈ nbc(M ′) and to 0 otherwise.
Let N be a decomposition of a matroid M on E, and let d = dimPM . For
any S ∈ nbc(M), let NS ⊆ Nint be the collection of internal faces N ∈ Nint
such that S ∈ nbc(N). The complex τ∧(C•(N )) has a subcomplex consisting
of the terms corresponding to matroids N ∈ Nint \ NS i.e. internal faces where
81
S is not an nbc-set. The fact that this is a subcomplex follows from the second
sentence in the previous paragraph. Let V•(N , S) be the quotient of τ∧(C•(N )) by
this subcomplex. More concretely, V•(N , S) is defined by Vd+1(N , S) = Q and
⊕
Vk(N , S) := Q
N∈NS
dimPN=k
for all 0 ¬ k ¬ d. The previous paragraph tells us we have the following
isomorphism of complexes
∧ ∼ ⊕grOS (C•(N )) = V•(N , S) [−|S|] . (3.4.2)
S∈nbc(M)
We will prove that V•(N , S) is exact, and use this to prove that OS is a valuative
categorical invariant.
3.4.1. The nbc condition
Fix an identification E = [n]. For a matroid M on E, we will give equivalent
notions of what it means for S ∈ nbc(M). For each integer i, let Si = {s ∈ S | s >
i}, and let H+i,S ⊆ RE be the open half-space
 ∣∣ ∑ 
H+ Ei,S = x ∈ R ∣ xj > |Si| .
j∈Si∪{i}
Lemma 3.4.1. If M is a matroid on E, the following are equivalent:
(i). S ∈ nbc(M).
(ii). Si ∪ {i} is independent for all i ∈ E.
(iii). PM ∩H+i,S ̸= ∅ for all i ∈ E.
82
(iv). PM ∩
⋂
i∈E
Proof. The fact that (i) and (ii) are equivalent follows immediately from the
definition of a broken circuit. We know that Si ∪ {i} is independent, if and only
if it is contained in some basis Bi of M . This happens exactly when the indicator
vector eB is in the polynomial PM . Since eB lies in H+i,S, we have the equivalencei i
of (ii) and (iii).
We have shown that (i), (ii), and (iii) are equivalent. It is obvious that (iv)
implies (iii) and so to finish the proof, it suffices to show that (ii) implies (iv).
Assume (ii) holds. For each i ∈ E pick a basis Bi containing Si ∪ {i}. Then,
choose real numbers ϵ0 > ϵ1 > · · · > ϵn such that ϵ0 = 1 and ϵn = 0 and so
that ϵi < ϵi−1/(|Si|+ 1) for all i ∈ E. Define the point
∑
x = (ϵ Ei−1 − ϵi)eB ∈ R .i
i∈E
Notice that x is a positive linear combination of the indicator vectors {eB | i ∈ E}i
whose coefficients sum to 1 so x ∈ PM . We will show that x ∈ H+i,S for all i ∈ E
which will complete the proof.
Let i ∈ E. We know that Bk contains Si whenever k ¬ i. Thus, for any j ∈ Si,
the jth coordinate of eB is equal to 1. Therefore, the jth coordinate xj of x is atk
least the sum of the coefficients of eB for k ¬ i. Concretely, for any j ∈ Si,k
∑
xj ­ (ϵk−1 − ϵk) = 1− ϵi.
k¬i
83
Similarly, we know that Bi contains i and so xi ­ ϵi−1 − ϵi. Putting these together,
we have
∑ ∑
xj = xj + xi
j∈Si∪i j∑∈Si
­ (1− ϵi) + (ϵi−1 − ϵi)
j∈Si
= |Si|(1− ϵi) + (ϵi−1 − ϵi)
= |Si| − (|Si|+ 1)ϵi + ϵi−1
> |Si|
where the last inequality follows from how we chose ϵ0, . . . , ϵn. This shows that
x ∈ H+i,S as desired.
Proposition 3.4.2. For any decomposition N of M and any S ∈ nbc(M), the
complex V•(N , S) is exact.
Proof. The strategy for this proof is similar to Proposition 3.3.8. Let d = dimPM
and let V¬d(N , S) be the complex obtained from V•(N , S) by setting the degree
d + 1 to 0. Note that V¬d(N , S) is a subcomplex of V•(N , S) whose corresponding
quotient complex is Q[−d − 1]. Thus we have a short exact sequence of chain
complexes
0→ V Ω¬d(N , S)→ V Ω• (N , S)→ Q[−d− 1]→ 0.
Just like in the proof of Proposition 3.3.8, we will show that V¬d(N , S) has 1-
dimensional homology concentrated in degree d and that in the long exact sequence
on homology, the generator of Q[−d− 1] gets sent to a generator of the homology of
V¬d(N ). This will imply that V•(N , S) is exact.
84
To do this, given a polytope P ⊆ RE, let P̊ denote its relative interior. Let
⋂
U = P̊M ∩ H+i,S.
i∈E
The equivalence of (i) and (iv) in Lemma 3.4.1 tells us that U is nonempty.
We see that U is an intersection of open convex subsets of a PM so it is itself a
nonempty open convex subset of PM which implies U is homeomorphic to an open
d-dimensional ball.
For each N ∈ N let UN = U ∩ P̊N .
Notice that if N is not an interior face, then UN = by definition of U . If N is
an interior face, then P̊N ⊆ P̊M . In this case,
⋂
UN = P̊ ∩ H+N i,S
i∈E
so Lemma 3.4.1 tells us that UN is nonempty if and only if S ∈ nbc(N). These
UN partition U so adding a single 0-cell, ⋆, and gluing ∂U to it, gives a cell
decomposition of the quotient Ū/∂U . The (open) cells of this cell decomposition
are given by the {UN | N ∈ Nint and S ∈ nbc(N)} ∪ {⋆}. Therefore, the terms
in V Ω¬d(N ) match the terms in the cellular chain complex used to compute the
relative homology of the pair (Ū/∂U, ⋆). To see that differential in these complexes
match, it is enough to notice that if PN ′ is a face of PN , then UN ′ is contained in
the boundary of UN and the outward normal direction of UN ′ relative to UN is
the same as that of P ′N in PN . Thus, V
Ω
¬d(N , S) can indeed be identified with the
cellular chain complex for the pair (Ū/∂U, ⋆) so its homology is identified with the
reduced homology H̃(Ū/∂U). Since (Ū/∂U) is homeomorphic to the sphere Sd, the
homology of this complex is one dimensional and concentrated in degree d.
85
To finish the proof, we simply observe that for the exact sequence
0→ V¬d(N )→ V•(N )→−
q Q[−d− 1]→ 0,
the map q is an isomorphism in degree d+1. In otherwords we have an isomorphism
qd+1 : τ∧(M) → Q. This isomorphism determines an orientation Ω of PM . In
the long exact sequence on homology, the boundary map sends the generator of
Q[−d−1] to the orientation class of Hd(Ū/∂U, ⋆) determined by Ω and so V Ω• (N , S)
is exact.
Theorem 3.4.3. The categorical invariant OS is valuative.
Proof. We need to show that for any matroid M on E and any decomposition
N of M , the complex OS∧(CΩ• (N )) is exact. By Equation 3.4.2 and Proposition
3.4.2, OS∧(CΩ• (N )) admits a filtration whose associated graded is exact. The
spectral sequence of the filtered complex has E1 page equal to the homology of the
associated graded and converges to the homology of the original complex. In this
case, the E1 page is zero, so the original complex must be exact as well.
3.5. Characters
Let C be the category of finite dimensional vector spaces over Q or the
category of finite dimensional graded vector spaces over Q. Consider the bounded
derived category K(C) of C. If V• is an object of K(C) and Γ is a finite group
∑acting on V• via automorphisms in C, then the Euler characteristic χ
Γ(V•) =
k(−1)k[Vk] is a graded virtual representation of Γ depending only on the Γ-
equivariant isomorphism class of V .
86
Suppose Φ : M(E) → C is valuative. Note, now Φ is a functor from M(E)
not from Mid(E). Thus, we are now allowed weak maps that are non-identity
permutations of the ground set E. When we say that Φ is valuative, we mean that
Φ restricted to the subcategory Mid(E) is valuative. Then, for any decomposition
N of a matroid M on E, by definition of valuative, Φ∧(C•(N )) is isomorphic to
the zero object of K(C). Thus, by our discussion in the previous paragraph, we
immediately obtain the following result.
Proposition 3.5.1. Let N be a decomposition of a matroid M on the ground set
E. Let Γ be a finite group acting on E which preserves N . If Φ : M → C is a
valuative categorical invariant, then
χΓ(Φ∧(C•(N ))) = 0
as a virtual representation of Γ. More concretely, setting d = dimPM and Nk =
{N ∈ N | dimPN = k}, we have
( ) ∑  ⊕ d
(−1)dχΓ Φ(M)⊗Det(M) = (−1)dχΓ Φ(N)⊗Det(N)
k∑=0 N∑∈Nk ( )d
= (−1)dχΓ IndΓ ΓNΓ χ Φ(N)⊗Det(N)N
k=0 N∈Nk/Γ
Example 3.5.2. Let N be the decomposition of M in Example 3.2.3, and let Γ =
S2 act by swapping 1 with 3 and 2 with 4. Applying Proposition 3.5.1 to the trivial
categorical invariant τ , we obtain the equation
−Det(M) = −Det(N1)−Det(N2) + Det(N12)
87
of virtual representations of S2. Since S2 acts on PM in an orientation preserving
way, Det(M) is the trivial representation. Since S2 acts on PN12 in an orientation
reversing way, Det(N12) is the trivial representation. Finally, since S2 swaps N1
with N2, Det(N1) + Det(N2) is the regular representation.
3.5.1. Equivariant relaxation
Let M be a matroid of rank k on the ground set E, equipped with an action
of the group Γ. Let F be a stressed flat of rank r, and let F := {γF | γ ∈ Γ}.
Let M̃ = RelΓ(M) be the matroid obtained by relaxing M with respect to every
G ∈ F , as described in Section 3.2.2. Let ΓF ⊂ Γ denote the stabilizer of F . Note
that ΓF acts on the sets F and E \ F , and therefore on the matroids Πr,k,E,F and
Λr,k,E,F from Section 3.2.2. Since r, k, E, F are fixed in this situation, let us simplify
the notation and define
Π = Πr,k,E,F and Λ = Λr,k,E,F .
Let C be the category of finite dimensional graded vector spaces, and let Φ :
M→ C be a valuative categorical invariant.
Proposition 3.5.3. We have the following equality of virtual graded Γ-
representations:
( ) ( ) ( ) ( )
χΓ Φ∧(M̃) = χΓ Φ∧(M) + IndΓ χΓF Φ∧(Λ) − IndΓ χΓFΓ Γ Φ∧(Π) .F F
Proof. If M = Π, then M̃ = Λ and the statement is trivial. Assume now that this
is not the case. Let N be the decomposition of M̃ described in Theorem 3.2.10. For
88
any matroid N , let d(N) := dimPN . By Proposition 3.5.1, we have
( ) ( )
(−1)d(M̃)χΓ Φ∧(M̃)⊗Det(M̃) = (−1)d(M)χ Φ∧(M)⊗(Det(M) )
+ (−1)d(Λ) IndΓ ΓF ∧Γ χ Φ (Λ)⊗Det(Λ)F ( )
+ (−1)d(Π) IndΓ χΓFΓ Φ∧(Π)⊗Det(Π) .F
To simplify this, we first note that
d(M̃) = d(M) = d(Λ) = d(Π) + 1.
Next, we observe that
AM̃ = AM = AΛ = AΠ ⊕Q · vF
where vF is given by the outward normal unit vector of PΠ in PΛ. This implies that
Det(M̃) = Det(M) as representations of Γ. Since ΓF fixes vF , it also implies that
Det(Λ) = Det(Π) = ResΓΓ Det(M) as representations of ΓF . ThusF
( ) ( )
(−1)d(M)χΓ Φ∧(M̃)⊗Det(M) = (−1)d(M)χΓ Φ∧(M)⊗(Det(M) )
+ (−1)d(M) IndΓ ΓFΓ χF (Φ∧(Λ)⊗ ResΓΓ Det(M)F )
− (−1)d(M)(IndΓΓ χΓF Φ∧(Π)⊗)ResΓΓ Det(M)F F
= (−1)d(M)χΓ Φ∧(M)⊗(Det(M))
+ (−1)d(M) IndΓΓ χΓF(Φ∧(Λ)) ⊗Det(M)F
− (−1)d(M) IndΓ ΓF (Γ χ Φ Π) ⊗Det(M).F
Dividing both sides by (−1)d(M)Det(M) yields the statement of the proposition.
89
3.5.2. Relaxing a stressed hyperplane
We conclude by applying Proposition 3.5.3 to the functor OS in the special
case where the stressed flat F = H is a hyperplane, meaning that r = k − 1. In this
case, we have
Πk−1,k,E,H = U1,E\H ⊕ Uk−1,H .
The matroid Λk−1,k,E,H obtained by relaxing Πk−1,k,E,H with respect to the stressed
hyperplane H has as its bases those subsets B ⊂ E of cardinality k with |B ∩H| ­
k − 1. It has no loops, and its simplification is the uniform matroid of rank k on
the ground set H̄ := H ⊔ {∗} obtained from E by identifying all of the elements of
E \H.
For the rest of this section, we will write h = |H| and identify H with
{1, . . . , h}. If λ is a partition of h, we write Vλ to denote the corresponding Specht
module for Sh = Aut(H).
Lemma 3.5.4. We have
(∧ ) ( )k−1
OS(Λk−1,k,E,H)−OS(Πk−1,k,E,H) = V[h−1,1] ⊗ Q[1− k]⊕Q[−k]
as graded virtual representations of Sh.
Proof. The matroids Λk−1,k,E,H and Πk−1,k,E,H have the same independent sets of
cardinality less than k, so their Orlik–Solomon algebras differ only in degrees k − 1
and k. Let us consider the degree k part first. We have
∧
OSk
k−2
(Π ∼k−1,k,E,H) = V[h−1,1]
90
and ∧
k k−1 ∧k−2OS (Λk−1,k,E,H) ∼= V[h−1,1] ⊕ V[h−1,1],
which proves that the lemma is correct in degree k. The statement in degree
∑k − 1 follows from the fact that, for any matroid M on a nonempty ground set,
(−1)iOSi(M) = 0 as a virtual representation of the automorphism group of
M .
Proposition 3.5.3 and Lemma 3.5.4 have the following immediate corollary.
Corollary 3.5.5. Let M be a matroid equipped with an action of the group Γ. Let
H be a stressed hyperplane of M , and let M̃ be the matroid obtained from M by
relaxing γH for all γ ∈ Γ. Then
( ∧ ) ( )k−1
OS(M̃) = OS(M) + IndΓΓ Res
Sh
Γ V[h−1,1] ⊗ Q[1− k]⊕Q[−k]H H
as virtual graded representations of Γ.
Here, we use ResShΓ to denote the pullback of the natural homomorphismH
ΓH → Sh given by the action of ΓH on H.
3.5.3. The Vámos matroid
We conclude by showing a concrete application of Corollary 3.5.5. We will
compute the Orlik-Solomon algebra of the Vámos matroid as a representation
of its symmetry group. The Vámos matroid V8 is the rank 4 matroid on the
ground set [8] whose set of bases are all cardinality 4 subsets of [8] except for
H1 = {1, 2, 3, 4}, H2 = {1, 4, 5, 6}, H3 = {2, 3, 5, 6}, H4 = {1, 4, 7, 8}, and
91
6
5
4 3
1 2
8
7
FIGURE 3. The Vámos matroid V8. The five shaded rectangles correspond to the
five circuit hyperplanes of V8. Note, this does not depict the base polytope of V8
H5 = {2, 3, 7, 8}. The sets H1, . . . , H5 are all circuit-hyperplanes of V8 and are
therefore stressed hyperplanes. See Figure 3 for a visualization of V8.
The symmetry group Γ of V8 is the subgroup of the symmetric group on
[8] generated by the elements (14), (12)(34), (56), and (57)(68). We see that
Γ ∼= D4×D4, where the first copy of D4 is generated by the first two generators and
the second copy of D4 is generated by the second two generators. Under the action
of Γ, the hyperplanes H2, . . . , H5 are all in the same orbit. Meanwhile, H1 is fixed
by Γ. Thus, to compute OS(V8) as a representation of Γ, we will apply Corollary
3.5.5 twice. First with H = H1 and second with H = H2. Doing so, we see that as a
92
virtual representation of Γ,
OS
i(U4,8), for i < 2
OSi(V8) = OS
i(U4,8)− IndΓ ShΓ ResΓ V (3.5.3)H H [1,1,1,1]
 1 1 − IndΓΓ ResShΓ V[1,1,1,1], for i = 3, 4H2 H2
As a representation of S8, when 0 < i ¬ 3, we have
∧i
OSi(U ) ∼= 84,8
∼∧
Q
i ∧i−1
= V[7,1] ⊕ V[7,1]
∼= V[8−i,1i] ⊕ V[9−i,1i−1]
and in degree 4, we have
∧3
OS4(U ) ∼4,8 = V ∼[7,1] = V[5,1,1,1].
Plugging this into Equation 3.5.3, as virtual representations of Γ, we have
OS0(V8) = ResS8Γ (V[8])
OS1(V8) = ResS8Γ (V[7,1] ⊕ V[8])
OS2(V8) = ResS8Γ (V[6,1,1] ⊕ V[7,1])
OS3(V8) = ResS8Γ (V[5,1,1,1] ⊕ V[6,1,1])− IndΓ Res
Sh
Γ VH ΓH [1,1,1,1]1 1
− IndΓ ResShΓH Γ VH [1,1,1,1],2 2
93
OS4(V8) = ResS8Γ (V[5,1,1,1])− IndΓΓ Res
Sh
H Γ VH [1,1,1,1]1 1
− IndΓΓ Res
Sh
Γ VH H [1,1,1,1].2 2
Finally, we will computing these restrictions and inductions explicitly on characters.
Note, ΓH1 = Γ as H1 is fixed by the action of Γ. Meanwhile, ΓH2 is the subgroup
of Γ generated by (14), (56), (23) and (78). Since Γ ∼= D4 × D4, the irreducible
characters of Γ are of the form χ ′i ⊗ χj where χi is an irreducible character of the
copy of D4 generated by (14) and (12)(34) and χ′j is an irreducible character of the
copy of D4 generated by (56) and (57)(68). We use the following character tables
for the two copies of D4
e (1, 4) (14)(23) (12)(34) (1234) e (5, 6) (56)(78) (57)(68) (5768)
χ1 1 1 1 1 1 χ′1 1 1 1 1 1
χ ′2 1 −1 1 −1 1 χ2 1 −1 1 −1 1
χ3 1 −1 1 1 −1 χ′3 1 −1 1 1 −1
χ4 1 1 1 −1 −1 χ′4 1 1 1 −1 −1
χ5 2 0 −2 0 0 χ′5 2 0 −2 0 0
Performing the restrictions and inductions, we have the following.
charOS1(V8) = χ ⊗ χ′1 1 + χ ′1 ⊗ χ4 + χ1 ⊗ χ′5 + χ3 ⊗ χ′ ′ ′3 + χ4 ⊗ χ1 + χ5 ⊗ χ1.
charOS2(V8) = χ1 ⊗ χ′1 + χ1 ⊗ χ′2 + 2χ1 ⊗ χ′4 + 3χ1 ⊗ χ′5 + χ2 ⊗ χ′1 + 2χ ′4 ⊗ χ1
+χ ⊗ χ′ + χ ⊗ χ′4 4 4 5 + 3χ5 ⊗ χ′1 + χ5 ⊗ χ′ + χ ⊗ χ′4 5 5.
charOS3(V8) = 2χ ′ ′ ′1 ⊗ χ2 + χ1 ⊗ χ4 + 3χ1 ⊗ χ5 + 2χ ⊗ χ′ ′ ′2 1 + χ2 ⊗ χ4 + χ2 ⊗ χ5
+χ3 ⊗ χ′1 + χ4 ⊗ χ′1 + χ4 ⊗ χ′2 + 2χ4 ⊗ χ′4 + 3χ4 ⊗ χ′5
+χ5 ⊗ χ′2 + 3χ5 ⊗ χ′4 + 3χ5 ⊗ χ′1 + 3χ5 ⊗ χ′5.
94
charOS4(V8) = χ1 ⊗ χ′ + χ ⊗ χ′2 1 5 + χ ′ ′ ′ ′2 ⊗ χ1 + χ2 ⊗ χ5 + χ2 ⊗ χ4 + χ3 ⊗ χ1
+χ ⊗ χ′4 2 + χ ⊗ χ′4 4 + 2χ4 ⊗ χ′5 + χ5 ⊗ χ′1
+χ ⊗ χ′ + 2χ ⊗ χ′5 2 5 4 + 2χ ′5 ⊗ χ5.
95
REFERENCES CITED
[Abr00] Aaron David Abrams, Configuration spaces and braid groups of graphs,
ProQuest LLC, Ann Arbor, MI, 2000, Thesis (Ph.D.)–University of
California, Berkeley. MR 2701024
[ADCK19] Byung Hee An, Gabriel C. Drummond-Cole, and Ben Knudsen,
Subdivisional spaces and graph braid groups, Doc. Math. 24 (2019),
1513–1583. MR 4033833
[ADCK20] , Edge stabilization in the homology of graph braid groups, Geom.
Topol. 24 (2020), no. 1, 421–469. MR 4080487
[AFR10] Federico Ardila, Alex Fink, and Felipe Rincón, Valuations for matroid
polytope subdivisions, Canad. J. Math. 62 (2010), no. 6, 1228–1245.
[AS23] Federico Ardila and Mario Sanchez, Valuations and the Hopf Monoid of
Generalized Permutahedra, Int. Math. Res. Not. IMRN (2023), no. 5,
4149–4224. MR 4565665
[Bou92] S. Bouc, Homologie de certains ensembles de 2-sous-groupes des groupes
symétriques, Journal of Algebra 150 (1992), no. 1, 158–186.
[DF10] Harm Derksen and Alex Fink, Valuative invariants for polymatroids, Adv.
Math. 225 (2010), no. 4, 1840–1892.
[dLS01] Mark de Longueville and Carsten A. Schultz, The cohomology rings of
complements of subspace arrangements, Mathematische Annalen 319 (2001),
no. 4, 625–646.
[DMM20] Hamid Reza Daneshpajouh, Frédéric Meunier, and Guilhem Mizrahi,
Colorings of complements of line graphs, 2020.
[Eur20] Christopher Eur, Divisors on matroids and their volumes, J. Combin.
Theory Ser. A 169 (2020), 105135, 31. MR 4011081
[FH98] Joel Friedman and Phil Hanlon, On the betti numbers of chessboard
complexes, Journal of Algebraic Combinatorics 8 (1998), no. 2, 193–203.
[FNV22] Luis Ferroni, George D Nasr, and Lorenzo Vecchi, Stressed Hyperplanes
and Kazhdan–Lusztig Gamma-Positivity for Matroids, International
Mathematics Research Notices (2022), rnac270.
[FS] Luis Ferroni and Benjamin Schröter, Valuative invariants for large classes of
matroids, arXiv:2208.04893.
96
[FWW19] Benson Farb, Jesse Wolfson, and Melanie Matchett Wood, Coincidences
between homological densities, predicted by arithmetic, Advances in
Mathematics 352 (2019), 670–716.
[Jon08] Jakob Jonsson, Simplicial complexes of graphs, Lecture Notes in
Mathematics, vol. 1928, Springer-Verlag, Berlin, 2008.
[Jon10a] Jakob Jonsson, More torsion in the homology of the matching complex,
Experimental Mathematics 19 (2010), no. 3, 363–383.
[Jon10b] , On the 3-torsion part of the homology of the chessboard complex,
Annals of Combinatorics 14 (2010), no. 4, 487–505.
[Jon13] Jakob Jonsson, 3-torsion in the homology of complexes of graphs of bounded
degree, Canadian Journal of Mathematics 65 (2013), no. 4, 843–862.
[KP12] Ki Hyoung Ko and Hyo Won Park, Characteristics of graph braid groups,
Discrete Comput. Geom. 48 (2012), no. 4, 915–963. MR 3000570
[MS05] Ezra Miller and Bernd Sturmfels, Combinatorial commutative algebra,
Springer, New York, 2005.
[NR19] Uwe Nagel and Tim Römer, FI- and OI-modules with varying coefficients,
Journal of Algebra 535 (2019), 286–322.
[OT92] Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, Grundlehren
der Mathematischen Wissenschaften [Fundamental Principles of Mathematical
Sciences], vol. 300, Springer-Verlag, Berlin, 1992.
[Oxl11] James Oxley, Matroid theory, second ed., Oxford Graduate Texts in
Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819
[PR19a] Nicholas Proudfoot and Eric Ramos, The contraction category of graphs.
[PR19b] , Functorial invariants of trees and their cones, Selecta Mathematica
25 (2019), no. 4, 62.
[RS04] Neil Robertson and P. D. Seymour, Graph minors. XX. Wagner’s conjecture,
J. Combin. Theory Ser. B 92 (2004), no. 2, 325–357.
[RS10] Neil Robertson and Paul Seymour, Graph minors XXIII. Nash-Williams’
immersion conjecture, J. Combin. Theory Ser. B 100 (2010), no. 2, 181–205.
[Sin20] Anurag Singh, Bounded degree complexes of forests, Discrete Mathematics
343 (2020), no. 10, 112009.
[Spe08] David E. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (2008),
no. 4, 1527–1558.
97
[SS17] Steven V. Sam and Andrew Snowden, Gröbner methods for representations of
combinatorial categories, J. Amer. Math. Soc. 30 (2017), no. 1, 159–203.
[Sta96] Richard P. Stanley, Combinatorics and commutative algebra, second ed.,
Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1996.
[SW07] John Shareshian and Michelle L. Wachs, Torsion in the matching complex
and chessboard complex, Advances in Mathematics 212 (2007), no. 2, 525–570.
[Wac03] Michelle L. Wachs, Topology of matching, chessboard, and general bounded
degree graph complexes, Algebra Universalis 49 (2003), no. 4, 345–385.
98