The contraction category of graphs
Nicholas Proudfoot Eric Ramos
math.CO math.AG math.AT math.CT math.RT

1.2
The contraction category of graphs



Nicholas Proudfoot and Eric Ramos

Department of Mathematics, University of Oregon,
Eugene, OR 97403



Abstract.
We study the category whose objects are graphs of fixed genus and whose morphisms
are contractions.  We show that the corresponding contravariant module categories are Noetherian
and we study two families of modules over these categories.  
The first takes a graph to a graded piece of the homology
of its unordered configuration space and the second takes a graph to an intersection homology group whose dimension
is given by a Kazhdan–Lusztig coefficient; in both cases we prove that the module is finitely generated.
This allows us to draw conclusions about 
torsion in the homology groups of graph configuration spaces, and about the growth of Betti numbers
of graph configuration spaces and Kazhdan–Lusztig coefficients of graphical matroids.
We also explore the relationship between our category and outer space, which is used in the study of outer
automorphisms of free groups.
 



§ INTRODUCTION

We are interested in ways of assigning a vector space or abelian group to a graph that are contravariantly functorial with respect to contractions of graphs.
A contraction, which is defined precisely in Section <ref>, preserves the genus (first Betti number) of a graph,
so we consider the category  whose objects are graphs of genus g and whose morphisms are contractions.
For any commutative ring k, we define _k() to be the category of functors from  to k-modules.
An object of this category is called a -module with coefficients in k.




 §.§ Noetherianity and growth

For any category , a module M∈_k() is called finitely generated if 
there exist finitely many objects x_1,…,x_r of  along with elements v_i∈ M(x_i) such that, for any object
x of , M(x) is spanned over k by the images of the elements v_i along the maps induced by 
all possible morphisms f_i:x_i→ x.  If every submodule of a finitely generated module is itself finitely generated, 
the category _k() is said to be locally Noetherian.

Sam and Snowden have developed powerful machinery for proving that module categories are locally Noetherian.
They define what it means for  to be quasi-Gröbner, and they show that, if  is quasi-Gröbner, then
_k() is locally Noetherian for any Noetherian commutative algebra k <cit.>.  The most prominent example
of a quasi-Gröbner category is the category  of finite sets with injections; the fact that _k() is locally Noetherian
has been used to prove stability patterns in coinvariant algebras and in the cohomology groups of configuration spaces 
and other moduli spaces <cit.>, in the homology groups of congruence subgroups <cit.>, and in the syzygies of Segre embeddings <cit.>.  

In the prequel to this paper, the authors built on work of Barter <cit.> to prove that the opposite category _0^
of trees with contractions is quasi-Gröbner <cit.>.  The technical heart of this paper is the extension of this
result to arbitrary genus.


For any non-negative integer g,
the category  is quasi-Gröbner, and therefore the category _k() is locally Noetherian
for any Noetherian commutative algebra k.


Theorem <ref> is useful for proving that specific -modules are finitely generated, and this gives some control
over their dimension growth.  More precisely, we say that a module is finitely generated in degrees ≤ d
if the objects x_1,…,x_r in the definition of finite generation may be taken to be graphs with at most d edges.
If k is a field and M is finitely generated in degrees ≤ d, then the dimension of M(G) is constrained by a polynomial of degree d
in the number of edges of G (Proposition <ref>).  Furthermore, if we fix a graph and modify it by either
subdividing edges or “sprouting” new leaves at a fixed set of vertices, then the dimension of M evaluated on the modified graph
behaves as a polynomial of degree at most d in the subdivision and sprouting parameters (Corollaries <ref>
and <ref>).

Sometimes we have no control of the generation degree of a finitely generated module, but we can still control its growth.
We say that M is d-small if it is a subquotient of a module that is finitely generated in degrees ≤ d, and 
d-smallish if it admits a filtration whose associated graded is d-small.  Theorem <ref> implies that
d-small modules are finitely generated, and it is not hard to prove that the same is true for d-smallish modules (Proposition <ref>).
The degree of generation of such modules may be much larger than d, but for the purposes of the results mentioned in the
previous paragraphs, they grow as if they were finitely generated in degrees ≤ d.  This will be important for the two classes
of examples that we study in detail, which we describe below.





 §.§ Homology of configuration spaces

Given a graph G and a positive integer n, the n-stranded unordered configuration space of G 
is the topological space

    _n(G) := {(x_1,…,x_n) ∈ G^n  x_i ≠ x_j}/S_n.

The homology groups of these spaces have been extensively studied in settings both theoretical <cit.> and applied <cit.>.

One powerful technique for studying these groups, which is applied for example in <cit.>, is to fix the graph G and consider the direct
sum of the homology groups of _n(G) for all n.  This direct sum is a module over a polynomial ring with generators indexed by the edges
of G, where a variable acts by “adding a point” to the corresponding edge.  An orthogonal approach is to fix n and vary G.
This approach has been used in a number of recent works <cit.>, and it is the approach that we take here.
In particular, the homology of _n(G) is functorial with respect to contractions (Section <ref>), 
and therefore defines an object of _().


Fix natural numbers g, i, and n. The -module

    G ↦ H_i(_n(G); )

is (g+i+n)-small.  In particular, it is finitely generated.


One concrete consequence of Theorems <ref> and <ref> is that we obtain some control of the type of torsion that can appear in these homology groups.
We know from the work of Ko and Park that the only torsion that can appear in H_1(_n(G); ) is 2-torsion <cit.>.
Furthermore, this torsion carries extremely interesting information: it is trivial if and only if G is planar!
The topological meaning of torsion in higher degree homology is more mysterious, but we can at least show that there is a bound on the type
of torsion that can occur.


For any triple (g,i,n) of positive integers, there exists a constant d_g,i,n such that for every graph G of genus g, the torsion part of
H_i(_n(G); ) has exponent at most d_g,i,n.



In this work we only consider unordered configurations of points, mainly because the tools we use largely derive from the paper <cit.>
and this is the setting in which they work. It is likely that one can obtain analogues of Theorem <ref> and Corollary <ref>
for ordered configuration spaces, starting by reproving certain results 
from <cit.> in the ordered setting. 





 §.§ Kazhdan–Lusztig coefficients

Kazhdan–Lusztig polynomials of matroids are analogues of Kazhdan–Lusztig polynomials of Coxeter groups.
Just as Kazhdan–Lusztig polynomials of Weyl groups can be interpreted as Poincaré polynomials of certain intersection homology groups,
the same is true of Kazhdan–Lusztig polynomials of graphical (or, more generally, realizable) matroids.
See <cit.> for a survey that explores this analogy in depth.

More precisely, given a graph G, we can define a complex variety X_G, called the reciprocal plane, 
with the property that the coefficient of t^i in the Kazhdan–Lusztig
polynomial of G is equal to the dimension of _2i(X_G).  These homology groups are functorial with respect to contractions <cit.>,
thus we obtain an object of _ℂ().


Fix a natural number g and a positive integer i.
The -module

    G ↦_2i(X_G)

is (2i-1+g)-smallish.  In particular, it is finitely generated.


For example, Theorem <ref> combines
with the results on subdivision described in Section <ref>
to imply that the  Kazhdan–Lusztig polynomial of the matroid associated with the n-cycle
is a polynomial in n of degree at most i.  Indeed, the formulas for these coefficients appearing in <cit.> demonstrate
that this bound is sharp (Example <ref>).



 §.§ Outer automorphisms of free groups

A further motivation for studying the category  and its modules is that this category
is closely related to (F_g), the outer automorphism group of a free group on g generators.
This group is in many ways analogous to various arithmetic groups and to mapping class groups of surfaces,
and much work has gone into exploring its cohomology; see Vogtmann's ICM address <cit.> for a survey.

We call a graph G of genus g≥ 2 reduced if it has no bridges and no vertices of valence 2.
If we consider the full subcategory of  consisting of reduced graphs and replace it with an equivalent small
category, we obtain a category whose nerve is a classifying space for (F_g) (Corollary <ref>).
This observation leads to the following theorem.


Fix a non-negative integer g and a commutative ring k.  Let M∈_k() be the module that
assigns k to every reduced graph and 0 to every non-reduced graph,
with all nontrivial transition functions equal to the identity.  Then there is a canonical k-algebra isomorphism

    ^*__k()(M,M)  ≅  H^*((F_g); k).



Our proof of Theorem <ref> relies on the very non-trivial theorem of
Culler and Vogtmann that outer space is contractible <cit.>.  Since (F_g) acts on outer space with finite stabilizers,
the rational cohomology of the quotient coincides with the rational cohomology of (F_g).  
We stress, however, that Theorem <ref> holds for arbitrary coefficients. 

As a sample application of this Theorem <ref>, we compute the first cohomology of 
(F_2)≅GL(2,) with coefficients in an arbitrary field k (Section <ref>),
with close attention to the dependence of the answer on the characteristic of k.
This calculation can be performed by other means (Remark <ref>), and the result is surely not new to experts.
Still, we hope that it serves as an example of how one can use the category _k() to perform non-trivial calculations of cohomology groups of (F_g) in arbitrary characteristic.




 §.§ Relationship to earlier and later work

We briefly address the relationship between this paper and the two related works <cit.> and <cit.>.


  * This paper generalizes the authors' previous paper <cit.>, in which we prove Theorems <ref>
and <ref> for the category _0 of trees.  
The proof of Theorem <ref> takes the argument used in <cit.> as a starting point
and builds on this argument in order to treat graphs of higher genus.  While the idea of applying the techniques
of <cit.> is the same, there is a significant additional layer of technical difficulty in the higher genus setting.

Once we have established Theorem <ref>, the proof of Theorem <ref> for arbitrary genus
is nearly identical to the proof in the genus 0 case.  Theorem <ref> has no direct analogue in the genus 0 setting
because Kazhdan–Lusztig polynomials of trees are trivial.  The same goes for Theorem <ref> because (F_0)
is the trivial group.


  * A more recent preprint of Miyata and the authors <cit.>
deals with modules over a category  whose objects are graphs of arbitrary genus and whose morphisms are built out
of contractions and edge deletions.  In particular, the category _g is the full subcategory of  consisting of graphs
of genus g.  In that paper, we improve upon Theorems <ref> and <ref> and Corollary <ref>
by proving analogous results for the category .  The proof of the analogue of Theorem <ref> in that paper
also uses the machinery of <cit.>, but employs a different approach that is not based on choosing a spanning tree.
We believe that the approach based on spanning trees is better adapted to studying the Hilbert series of a module,
as outlined in <cit.>.

Theorem <ref> has no analogue in <cit.> because the intersection homology groups of the reciprocal plane
are not functorial with respect to deletions.  There is also nothing in that paper about automorphism groups of free groups.




Acknowledgments:
NP is supported by NSF grant DMS-1565036.  ER is supported
by NSF grant DMS-1704811. The authors would like to thank Melody Chan, Jim Davis, Dan Dugger, 
Steven Sam, Paul Seymour, Dev Sinha, and Karen Vogtmann for valuable conversations.



§ GRAPH CATEGORIES

We begin by fixing terminology and conventions about graphs and trees and defining all of the various categories of decorated graphs
with which we will work in this paper.  The reader may want to skim this section at first and refer back to it as needed.



 §.§ Graphs

By a graph, we will mean a finite CW complex of dimension at most 1.
The 0-cells are called vertices and the 1-cells are called edges.  We will write |G|
for the number of edges of G.  If G is a non-empty connected graph, we define the genus
of G to be the rank of the first homology group, or equivalently the number of edges minus the number of vertices plus 1.
If we refer to a graph of genus g, we will always implicitly mean that the graph is non-empty and connected.

If f:G→ G' is a map of CW complexes, we say that f is very cellular if it takes every vertex to a vertex
and every edge to either a vertex or an edge.  An edge that maps to a vertex will be called a contracted edge.
If G and G' are graphs, we define a graph morphism from G to G' to be an equivalence class of very cellular maps,
where two very cellular maps are equivalent if and only if they are homotopic through very cellular maps.
We note that a graph morphism φ:G→ G' induces a well defined map on vertex sets, and it also makes sense to talk
about the set of edges that are contracted by φ.

We define a smooshing to be a surjective graph morphism with connected fibers,
and we define a contraction to be a smooshing with contractible fibers.
In particular, any automorphism of G is a contraction from G to itself, which necessarily has no contracted edges.
More generally, a contraction is a smooshing between two graphs of the same genus.
We denote by  the category whose objects are graphs of genus g and whose morphisms are contractions.



 §.§ Trees

The definitions in Sections <ref> and <ref> will be used only in Section <ref>, where we prove Theorem <ref>.

A tree is a graph of genus 0, and a rooted tree is a pair consisting of a tree and a vertex, which is called the root.

The vertex set of a rooted tree is equipped with a natural partial order in which v≤ w if and only if the unique path from v to the root
passes through w (so the root is maximal).  
A leaf of a rooted tree is a minimal vertex with respect to this partial order.  

For any vertex v, we define a descendant of v to be a vertex covered by v in the partial order.
A planar rooted tree is a rooted tree along with a linear order on the set of descendants of each vertex v.
This induces a depth-first linear order on the entire vertex set of the tree.
A contraction of rooted trees is a contraction of trees that preserves the root, and a contraction of planar rooted trees
is a contraction of rooted trees with the additional property that,
if v comes before w in the depth-first order, then the first vertex in the preimage of v
comes before the first vertex in the preimage of w.
Let  and  be the contraction categories of rooted trees and planar rooted trees, respectively.


Barter <cit.> defines the category  whose objects are rooted trees and whose morphisms 
are pointed order embeddings on vertex sets, 
along with the category  whose objects are planar rooted trees and whose morphisms are pointed
order embeddings that preserve the depth-first linear order.
In <cit.>, we prove that  is equivalent to ^, 
and a similar argument shows that  is equivalent to ^.
We will make use of Barter's work, via these equivalences, in Section <ref>.


Finally, we will need a labeled version of the above definitions.  Let S be a finite set.
We define an S-labeled planar rooted tree to be a triple (T,v,ℓ), where
(T,v) is a planar rooted tree and ℓ is a function from the set of vertices of T to S.
The most naive way to define a contraction φ:(T,v,ℓ)→(T',v',ℓ') of labeled planar rooted trees would be 
to say that it is a contraction of planar rooted trees with the property that the pullback of ℓ' along φ is equal to ℓ.
This, however, is not quite what we want.  
If φ:(T,v)→ (T',v') is a contraction of planar rooted trees and φ^*:(T',v')→(T,v) is the corresponding
pointed order embedding under the equivalence of Remark <ref>, we want to impose the condition that the pullback
of ℓ along φ^* is equal to ℓ'.  The proof of <cit.> tells us that 
φ^*(w') = maxφ^-1(w'), so the appropriate condition for φ:(T,v,ℓ)→(T',v',ℓ') to be 
an S-labeled contraction is that ℓ'(w') = ℓ(maxφ^-1(w')) for all w'∈ T'.
Equivalently, we say that a vertex w of T is φ-maximal if u≤ w for all vertices u with φ(u)=φ(w),
and we say that φ is an S-labeled contraction if and only if ℓ'∘φ(w) = ℓ(w) for all φ-maximal vertices w.






 §.§ Rigidified graphs

If G is a graph, a spanning tree of G is a contractible sub-complex of G containing all of the vertices.
A rigidified graph of genus g is a graph of genus g along with a choice of spanning tree 
and an ordering and orientation of the g extra edges that are not in the spanning tree.  More formally, 
fix once and for all a graph R_g with one vertex and g loops, called the rose of genus g.  Then a planar rooted graph of genus g is a 
quadruple (G,T,v,τ), where G is a graph of genus g, (T,v) is a planar rooted spanning tree of G,
and τ is a graph isomorphism from R_g to the quotient space G/T.

We denote by  the category whose objects are rigidified graphs
of genus g and whose morphisms are contractions that restrict to contractions of planar rooted trees
(in particular, only edges in the spanning tree can be contracted) 
and are compatible with the order and orientations of the extra edges.
We use the letter P in the notation because 𝒫𝒢_0 ≅.
The point of this definition is that rigid graphs are graphs with just enough extra structure to eliminate all nontrivial automorphisms.



 §.§ Reduced graphs

Most of the definitions in Sections <ref> and <ref> will be used only in Section <ref>, where we discuss connections
to outer automorphism groups of free groups.  The one exception is that the notion of a half-edge also appears in Section <ref>.

Fix a graph G.
A half-edge of G is defined to be an end, in the sense of <cit.>, of the relative interior of an edge.
For any half-edge h, there is an associated edge e(h) and a vertex v(h) that is incident to e(h).
For any pair (e,v) consisting of an edge and a vertex incident to that edge, there are either one or two half-edges h
with e(h)=e and v(h)=v, depending on whether or not e is a loop.
For any vertex v, the valence of v is defined to be the number of half-edges h with v(h) = v.

An edge of G is called a bridge if deleting the edge increases the number of connected components.
We call a non-empty connected graph with no bridges and no vertices of valence 2 reduced.  We also define the unique graph with one
vertex and one edge to be reduced, even though the vertex has valence 2.  
Intuitively, the idea is that any non-empty connected graph may be obtained from a reduced graph by subdividing
edges and “uncontracting” bridges, and there are finitely many isomorphism classes of reduced graphs of any fixed genus.
For example, there are two reduced graphs of genus 2 up to isomorphism, namely the rose R_2 = ∞ and the melon .


If G is reduced and φ:G→ G' is a contraction, then G' is also reduced.
For example, all contractions with domain equal to the melon are either automorphisms or maps to the rose, 
and all contractions with domain equal to the rose are automorphisms.


We define  to be the full subcategory of  whose objects are reduced graphs.
In the next section, we will want to talk about the nerve of this category, but one can only define the nerve of a small category.
For this reason, we choose a list G_1,…,G_r that includes a unique representative of each isomorphism class of reduced graphs of genus g,
and we let ^small be the full subcategory of  with objects G_1,…,G_r.
Thus ^small is a small category that is equivalent to .



 §.§ Marked reduced graphs

If G is a graph of genus g, a marking of G is a homotopy class of homotophy equivalences from the rose R_g to G.
(Note that a marking is not required to be a graph morphism.)  A marked graph of genus g is a pair (G,f), where G is
a graph of genus g and f is a marking of G.  We observe that the set of all markings of G is a torsor for (F_g).
A contraction from (G,f) to (G',f') is a contraction φ:G→ G'
such that f' = f∘φ.  
We define outer category  to be the category whose objects are marked reduced graphs
of genus g and whose morphisms are contractions.  The group (F_g) acts on 
in a natural way, fixing the graph but changing the marking.

As in Section <ref>, we would like to define a small subcategory of _g that is equivalent to .
We will do this in two
subtlely different ways, which we now describe.
Recall that we have chosen representatives G_1,…,G_r of the isomorphism classes of reduced graphs of genus g.
Let  be the full subcategory of  consisting of objects of the form (G_i,f) for some i and any marking f
of G_i.
Note that there are still isomorphisms between distinct objects
of .  Specifically, if f is a marking of G and φ:G→ G 
is a nontrivial automorphism of G, then f and f∘φ
are distinct markings of G but φ:(G,f)→ (G,φ∘ f) is an isomorphism.  To eliminate this phenomenon,
we choose for each G_i a representative of each (G_i) orbit in the set of markings of G_i, and we define
 to be the subcategory of  generated by these objects.  Note that the natural inclusions

    ⊂⊂
 are both equivalences.  


There is only one reduced graph of genus 1 up to isomorphism, namely the cycle R_1.  A marking of R_1
is the same as an orientation of the loop.  The category _1^small has two objects, 
related by the action (F_1) ≅ S_2,
corresponding to the two choices of marking of R_1.
Neither object has nontrivial automorphisms.
The category _1^tiny has only one object, and it has no nontrivial automorphisms.
We discuss the nerves of these categories in Example <ref>.


The advantage of working with  is that the action of (F_g) on  restricts to an action on , 
where it acts freely on the set of objects.
The advantage of working with  is that it is a poset category in the following sense.


If (G,f) and (G',f') are objects of , then |_((G,f), (G',f'))|≤ 1.
Furthermore, if there exists a morphism in both directions, then (G',f')=(G,f).
In particular, the set of objects of  admits a poset structure with (G',f')≤ (G,f) if and only if there
exists a morphism from (G,f) to (G',f').



If g≤ 1, the proposition is trivial, so we assume that g ≥ 2.  We begin by proving the proposition when G=G'.
In this case, the proposition says that, if σ is an automorphism of G that is homotopic to the identity, then σ
must in fact be equal to the identity.  This is proved in <cit.>.

Next we consider the case where G ≠ G'. Suppose that f is a marking of G and φ:G → G' and ψ:G → G'
are contractions with φ∘ f = ψ∘ f.  This implies that φ is homotopic to ψ.
By <cit.>, φ and ψ differ by an automorphism σ of G'.  Since φ is homotopic to ψ,
σ is homotopic to the identity, therefore σ is equal to the identity by the previous paragraph.
Thus φ=ψ, as desired.




§ LOCAL NOETHERIANITY

The purpose of this section is to prove Theorem <ref>, which says that _k() is locally Noetherian
for any Noetherian commutative ring k.




 §.§ Gröbner theory of categories


Let  be an essentially small category and x an object of C. 
We define _x to be the set of equivalence classes of morphisms out of x,
where f∈_(x,y) is equivalent to g∈_(x,y') if there exists an isomorphism h from y to y' such that h∘ f = g.
The set _x comes equipped with a natural quasi-order defined by putting 

    f ≤ g  there exists a morphism h with  h ∘ f = g.

Note that it is possible to have f≤ g and g≤ f even if the targets of f and g are not isomorphic, hence ≤ is only a quasi-order.
An infinite sequence f_0, f_1, f_2, … of elements of _x is called bad 
if there is no pair of indices i < j such that f_i ≤ f_j.
The category  is said to satisfy property (G2) if, for every object x of , _x admits no bad sequences.
The category  is said to satisfy property (G1) if, for every object x of , _x admits a linear order ≼ that is compatible with post-composition
in the following sense:
if f,g∈_(x,y), h∈_(y,z), and f≼ g, then h ∘ g ≼ h ∘ f.
The category  is called Gröbner 
if it satisfies properties (G1) and (G2) and has no endomorphisms other than the identity maps.




Sam and Snowden <cit.> explain that the motivation for properties (G1) and (G2) is deeply rooted in Gröbner basis theory 
from commutative algebra, with ≤ playing the role of the natural divisibility order on monomials and ≼ 
playing the role of a term order such as the lexicographic order.


Let  and ' be categories and let Φ:' → be a functor. We say that Φ satisfies property (F) if, for all objects x of , 
there exists a finite collection of objects y_1,…,y_r of ' and morphisms f_i:x →Φ(y_i) such that, for any object y of ' and any morphism f:x →Φ(y), there exists a morphism g:y_i → y with f = Φ(g) ∘ f_i. 
We say  is quasi-Gröbner if there exists a Gröbner category  and an essentially surjective functor Φ:' → satisfying property (F).

The motivation for these definitions comes from the following two theorems, both of which are of fundamental
importance in our work.

<cit.>
If Φ: →' has property (F) and M is a finitely generated '-module,
then Φ^*M is a finitely generated -module.


<cit.>
If  is quasi-Gröbner and k is a Noetherian commutative ring, then _k() is locally Noetherian.





 §.§ The category of rigidified graphs of fixed genus is Gröbner

We begin with the following translation of Barter's work to our setting.


The category ^≅𝒫𝒢_0^ of planar rooted trees is Gröbner.



Barter proves that  is Gröbner <cit.>, and the same is true
of ^ by Remark <ref>. 


Our goal in this section is to extend Theorem <ref> to the category  for arbitrary genus g.
We begin with the following corollary of Theorem <ref>.


For any natural number g, the category  satisfies property (G1).



Fix a rigidified graph (G,T,v,τ) of genus g.
We need to define a linear order ≼ on equivalence classes of contractions of rigidified graphs with target (G,T,v,τ) 
(since we are working with the opposite category) that is compatible with pre-composition.
By Theorem <ref>, we know that ^ satisfies property (G1), which means that we have a linear
order on contractions of planar rooted trees with target (T,v) which is compatible with pre-composition.  
Since a contraction of rigidified graphs restricts to a contraction of planar rooted trees, this induces a partial order on 
contractions of rigidified graphs with target (G,T,v,τ) that is compatible with pre-composition.
Let ≼ be any linear refinement of this partial order.  We claim that ≼ is also compatible with pre-composition.

To see this, suppose that φ,ψ:(G',T',v',τ')→ (G,T,v,τ) are contractions with φ≺ψ 
and σ:(G”,T”,v”,τ”)→ (G',T',v',τ')
is an arbitrary contraction.  Since φ≠ψ and a contraction of rigidified graphs is determined by its restriction to
the spanning tree, the restrictions of φ and ψ to (T',v') must be distinct.  This implies
that these restrictions are comparable in the Barter order, and therefore that the restrictions of φ∘σ and ψ∘σ
to (T”,v”) are comparable in the Barter order.  Since ≼ refines the Barter order, we may conclude 
that φ∘σ≺ψ∘σ.


Our next task is to prove that  satisfies property (G2). 
We begin by stating a version of Kruskal's tree theorem for labeled planar rooted trees.
Let S be a finite set.  If (T,v,ℓ) and (T',v',ℓ') are S-labeled planar rooted trees, we define (T',v',ℓ')≤ (T,v,ℓ)
if there exists a contraction from (T,v,ℓ) to (T',v',ℓ').  This defines a quasi-order on the set of isomorphism classes of S-labeled planar rooted trees.



Let S be a finite set.
The quasi-order on the set of isomorphism classes of S-labeled planar rooted trees admits no bad sequences.



After using Remark <ref> to translate between order embeddings and contractions, the case where S is a singleton
is proved in <cit.>.  On the other hand, the theorem is proved for general S, but with rooted trees
instead of planar rooted trees, in <cit.>.  Both proofs are essentially the same, and are in fact modeled
on the original proof of Nash-Williams for unlabeled rooted trees <cit.>.  These arguments can be trivially modified
to cover the result stated above.


The following corollary is a relative version of Theorem <ref>.
The case where S is a singleton is proved in <cit.>.  However, it turns out that the proof is greatly simplified
by allowing labels, as we demonstrate below.


Let S be a finite set and let (T,v,ℓ) be an S-labeled planar rooted tree.
The set (_S^)_(T,v,ℓ) admits no bad sequences.




An element of (_S^)_(T,v,ℓ) is represented by a pair consisting of an S-labeled planar rooted tree (T',v',ℓ')
and a contraction φ':(T',v',ℓ')→ (T,v,ℓ).  Let U := S ×(‖(T)⊔{0}) and
define a U-labeled planar rooted tree
(T',v',ℓ'_U) by putting 
    ℓ'_U(w') := 
    (ℓ'(w'), φ'(w'))    if w' is φ'-maximal
    
    (ℓ'(w'), 0)    otherwise.

Suppose that φ':(T',v',ℓ')→ (T,v,ℓ) and φ”:(T”,v”,ℓ”)→ (T,v,ℓ) represent two elements of (_S^)_(T,v,ℓ)
and let (T',v',ℓ'_U) and (T”,v”,ℓ”_U) be the corresponding U-labeled planar rooted trees.
We have φ'≤φ”
with respect to the quasi-order on (_S^)_(T,v,ℓ) if and only if there exists an S-labeled 
contraction ψ:(T”,v”,ℓ”)→ (T',v',ℓ') such that φ”=φ'∘ψ.
On the other hand, we have (T',v',ℓ'_U)≤(T”,v”,ℓ”_U)
with respect to the quasi-order on isomorphism classes of U-labeled planar rooted trees
if and only if there exists a U-labeled 
contraction ψ:(T”,v”,ℓ”_U)→ (T',v',ℓ'_U).

We claim that an S-labeled contraction ψ is a U-labeled contraction if and only if φ”=φ'∘ψ.
The easiest way to see this is to use Remark <ref> to translate from contractions to pointed order embeddings,
as the statement becomes tautological in that setting.  This implies that 
any bad sequence in (_S^)_(T,v,ℓ) induces a bad sequence of isomorphism classes of U-labeled planar rooted trees,
and Theorem <ref> tells us that no such sequences exist.


Let S = {0,1}^2g.  Given a ridigified graph (G,T,v,τ) of genus g, we construct an S-labeled planar rooted graph (T,v,ℓ) as follows.
Recall that τ induces an ordering and an orientation on the g extra edges of G.
For each 1≤ i≤ g, let w_2i-1 be the vertex at which the  extra edge originates and let w_2i be the vertex at which 
the  extra edge terminates.
Then for each vertex w and each 1≤ j≤ 2g, define the j^th component of ℓ(w) to be 1 if w≥ w_j and 0 otherwise.


Let (G,T,v,τ) and (G',T',v',τ') be rigidified graphs of genus g, and let (T,v,ℓ) and (T',v',ℓ')
be the associated S-labeled planar rooted graphs.  Let φ:(T,v)→ (T',v') be a contraction of planar rooted graphs.
Then φ induces a contraction of rigidified graphs if and only if it is compatible with the S-labeling.



On one hand, φ induces a contraction of rigidified graphs if and only if φ(w_j) = w'_j for all j.
On the other hand, φ is compatible with the S-labeling if and only if, for all φ-maximal vertices w, w ≥ w_jφ(w)≥ w'_j.

Assume first that φ induces a contraction of rigidified graphs, and let w be a φ-maximal vertex.  If w≥ w_j,
then φ(w) ≥φ(w_j) = w'_j.  Conversely, if φ(w)≥ w'_j, then w lies above
that unique φ-maximal preimage of w'_j, which in turn lies above w_j.

Assume next that φ is compatible with the S-labeling.
For any j, we want to show that φ(w_j) = w_j'.  Since w_j≥ w_j, we know that φ(w_j)≥ w_j'.
To prove the opposite inequality, let u_j be the unique φ-maximal preimage of w_j'.  Then

    φ(u_j) = w_j' ⇒ u_j ≥ w_j⇒ w_j' = φ(u_j) ≥φ(w_j).

This completes the proof.





For any natural number g, the category  satisfies property (G2).



Fix a rigidified graph (G,T,v,τ) of genus g, and let (T,v,ℓ) be its associated S-labeled planar rooted graph.  
We need to prove that the set ()_(G,T,v,τ) admits no bad sequences.
By Lemma <ref>, such a bad sequence induces a bad sequence in (_S^)_(T,v,ℓ), and Corollary <ref>
says that no such sequences exist.


We are now ready to prove the main result of this section.


For any g ≥ 0, the category  is Gröbner.



This follows from Corollaries <ref> and <ref>, along with the fact that rigidified graphs have no nontrivial automorphisms.





 §.§ The category of graphs of fixed genus is quasi-Gröbner



The forgetful functor Φ:→ is essentially surjective and has property (F).



Essential surjectivity is clear.
For any genus g graph G, we need to choose a finite collection of genus g rigidified graphs (G_i, T_i, v_i, τ_i)
along with contractions φ_i:G_i→ G such that, for every genus g rigidified graph (G',T',v',τ') and every contraction
φ:G'→ G, there exists an index i and a contraction ψ:(G',T',v',τ')→ (G_i, T_i, v_i, τ_i) such that φ = φ_i∘ψ.

For our rigidified graphs (G_i, T_i, v_i, τ_i) and our contractions φ_i, we will choose a representative of 
every possible isomorphism class of such structures whose number of edges is at most |G|+g.
Since there is a finite number of rigidified graphs with a fixed number of edges and finitely many contractions between any two graphs,
there are only finitely many such choices.

Let (G',T',v',τ') and φ be given, and let E⊂(G') be the set of edges that are contracted by φ.
Let ψ be the canonical contraction from (G',T',v',τ') to (G'/(E∩ T'), T'/(E∩ T'), v', τ').
It is clear from the definition that φ factors through ψ.  It thus remains only to show that the number of edges of G'/(E∩ T')
is at most |G|+g.  Indeed, 
we have |E| = |G'| - |G| and |T'| = |G'| - g, thus |E∩ T'| ≥ |G'| - (|G|+g).
From this it follows that |G'/(E∩ T')| = |G'| - |E∩ T'| ≤ |G| + g.




Let Φ:→ and Ψ:→ be the forgetful functors.
Then Φ, Ψ, and Ψ∘Φ are all essentially surjective and all have property (F).



Essential surjectivity of all three functors is clear.  If we prove property (F) for Φ and Ψ, this will prove property (F)
for Ψ∘Φ <cit.>.  We begin with property (F) for Φ, which is the more difficult statement.

For any genus g rooted graph (G,v), we need to choose a finite collection of genus g rigidified graphs (G_i, T_i, v_i, τ_i)
along with contractions φ_i:(G_i,v_i)→ (G,v) such that, for every genus g rigidified graph (G',T',v',τ') and every contraction
φ:(G',v')→ (G,v), there exists an index i and a contraction 
ψ:(G',T',v',τ')→ (G_i, T_i, v_i, τ_i) such that φ = φ_i∘ψ.

For our rigidified graphs (G_i, T_i, v_i, τ_i) and our contractions φ_i, we will choose a representative of 
every possible isomorphism class of such structures whose number of edges is at most |G|+g.
Since there is a finite number of rigidified graphs with a fixed number of edges and finitely many contractions between any two graphs,
there are only finitely many such choices.

Let (G',T',v',τ') and φ be given, and let E⊂(G') be the set of edges that are contracted by φ.
Let ψ be the canonical contraction from (G',T',v',τ') to (G'/(E∩ T'), T'/(E∩ T'), v', τ').
It is clear from the definition that φ factors through ψ.  It thus remains only to show that the number of edges of G'/(E∩ T')
is at most |G|+g.  Indeed, 
we have |E| = |G'| - |G| and |T'| = |G'| - g, thus |E∩ T'| ≥ |G'| - (|G|+g).
From this it follows that |G'/(E∩ T')| = |G'| - |E∩ T'| ≤ |G| + g.

Property (F) for Ψ is much easier:  for each genus g graph G, we consider the rooted graphs (G,v) for every vertex v of G.
It is clear that every contraction from a rooted graph to G is in fact a rooted contraction to some (G,v).




By Theorem <ref> and Lemma <ref>,  is quasi-Gröbner.
Theorem <ref> then follows from Theorem <ref>.





§ SMALLNESS AND GROWTH

We define what it means for a module over  to be generated in low degree, and see what this tells us about its dimension growth.



 §.§ Generation degree, smallness, and smallishness

Fix a Noetherian commutative ring k.
For any genus g graph G, let P_G∈_k() be the principal projective module that assigns to a genus g graph G'
the free k-module with basis _(G',G).
Note that a module M is finitely generated if and only if it is isomorphic to a quotient of a finite sum of principal projectives.
We say that a module M∈_k() is
finitely generated in degree ≤ d if we only need to use principal projectives 
corresponding to graphs with d or fewer edges.
The following lemma illustrates this notion in a specific example.


Let E be the -module that takes a graph G to the free k-module with basis indexed by edges of G, with the obvious maps.
The -module E^⊗ i is generated in degrees ≤ g+i.



For any graph G of genus g, E^⊗ i(G) has a basis given by an ordered i-tuple of edges, and any such basis
element is in the image of the map induced by a contraction φ:G→ G' if and only if none of the distinguished
edges are contracted by φ.  If G has more than g+i edges, then it has more than i edges that are not loops,
therefore for any given i-tuple, one can find a non-distinguished edge to contract.


We say that a module M is d-small if it is a subquotient of a module that is generated in degrees ≤ d.
We say that M is d-smallish if it admits a filtration whose associated graded is d-small.


If M is d-smallish for some d, then M is finitely generated.



Choose a filtration of M such that the associated graded M is d-small.
Theorem <ref> implies that M is finitely generated.  This means that there is a finite collection
G_1,…,G_r of genus g graphs, along with elements v_i∈ M(G_i),
such that, for any genus g graph G, the natural map

    ⊕_i=1^r ⊕_φ:G→ G_i k· e_i,φ→ M(G)

taking e_i,φ to φ^* v_i
is surjective.  For each i, choose an arbitrary lift ṽ_i∈ M(G_i) of v_i.
Since surjectivity is an open condition, the nautral map

    ⊕_i=1^r ⊕_φ:G→ G_i k· e_i,φ→ M(G)

taking e_i,φ to φ^* ṽ_i
is also surjective, which means that M is finitely generated.



Let k be a field, and suppose that M∈_k() is d-smallish.
Then there exists a polynomial f_M(t)∈[t] of degree at most d such that, for all G,
_k M(G) ≤ f_M(|G|).




We may immediately reduce to the case where M is the principal projective P_G' for some genus g graph G' with d edges.
For any G, a contraction from G to G' is determined, up to automorphisms of G',
by a choice of |G|-d edges of G to contract.  The number of such choices is |G|d, so
_k P_G'(G) ≤ |Aut(G')||G|d.




 §.§ Subdivision

Fix a graph G of genus g, a natural number r, and an ordered r-tuple = (e_1,…,e_r) of distinct directed
non-loop edges of G.  For any ordered r-tuple = (m_1,…,m_r) of natural numbers, let G(,) be 
the tree obtained from G by subdividing each edge e_i into m_i edges.  
The number m_i is allowed to be zero, and we adopt the convention
that subdividing e_i into 0 edges means contracting e_i.  
For each i, the graph G(,) has a directed path of length m_i where the directed edge e_i used to be, 
and we label the vertices of that path v_i^0,…,v_i^m_i.

Let  be the category whose objects are linearly ordered finite sets and whose morphisms are ordered inclusions.
Every object of  is isomorphic via a unique isomorphism to the finite set [m] for some m∈.
For any ∈^r, let [] denote the corresponding object of the product category .

Our goal in this section is to define a subdivision functor Φ_G,:→ and prove that Φ_G, 
has property (F).  
We define our functor on objects by putting Φ_G,([]) := G(,).
Let = (f_1,…,f_r) be a morphism in  from [] to [].  
We define the corresponding contraction 
    Φ_G,():G(,)→ G(,)

by sending v_i^t to v_i^s, where s is the maximal element of the set {0}∪{j| f_i(j)≤ t}⊂{0,1,…,m_i}.


For any ∈^r, let || := ∑ n_i.
We say that a contraction φ:G(,)→ G' 
factors nontrivially if there exists a non-identity morphism :[]→[] in 
and a contraction ψ:G(,)→ G' such that φ = ψ∘Φ_G,().


The subdivision functor Φ_G,:→ has property (F).



Property (F) says exactly that, for any graph G' of genus g, the set of contractions 
from some G(,) to G' that do not factor nontrivially is finite.
Let φ:G(,)→ G' be given.
We have 
    |G(,)| = |G| + || - r,
 so φ must contract |G| + || - r - |G'| edges.
If || is sufficiently large, then at least one of those edges must be one of the subdivided edges.
We may then factor φ nontrivially by first contracting that edge.

This tells us that, if we are looking for contractions from some G(,) to G' that do not factor nontrivially,
we only need to consider finitely many r-tuples .  The proposition then
follows from the fact that all Hom sets in  are finite.


Proposition <ref> implies that the dimension of M(G(,)) is bounded by a polynomial in 
of degree at most d.  The following corollary to Proposition <ref> says that the dimension of M(G(,)) is in fact equal
to a polynomial in  when each coordinate is sufficiently large.


Let k be a field, and suppose that M∈_k() is d-smallish.  Then there exists a multivariate polynomial f_M,G,(t_1,…,t_r)
of total degree at most d such that, if  is sufficiently large in every coordinate, 

    _k M(G(,)) = f_M,G,(m_1,…,m_r).




Proposition <ref> tells us that M is finitely generated,
though we have no control over the degree of generation.
Theorem <ref> and Proposition <ref> combine to tell us that Φ^*_G,M is a finitely generated 
-module.  By <cit.>, 
this implies that there exists a multivariate polynomial f_M,G,(t_1,…,t_r)
such that, if ∈^r is sufficiently large in every coordinate, 

    _k M(G(,)) = _k Φ^*_G,M([]) = f_M,G,(m_1,…,m_r).

Proposition <ref> says that _k M(G(,)) is bounded above by a polynomial of degree d in 
the quantity |G(,)| = |G|-r+||, thus the total degree of f_M,G,(t_1,…,t_r) can be at most d.






 §.§ Sprouting


Fix a graph G of genus g, a natural number r, and an ordered r-tuple := (v_1,…,v_r) of distinct vertices of T.
For any ordered r-tuple = (m_1,…,m_r) of natural numbers, let G(,) be 
the tree obtained from G by attaching m_i new edges to the vertex v_i, each of which has a new leaf as its other endpoint.
We will label the new leaves connected to the vertex v_i by the symbols v_i^1,…,v_i^m_i.

Our goal in this section is to define a sprouting functor Ψ_G,:→ and prove that Ψ_G, 
has property (F).  We define our functor on objects by putting Ψ_G,([]) := G(,).
Let = (f_1,…,f_r) be a morphism in  from [] to [].  
We define the corresponding contraction 
    Ψ_G,():T(,)→ T(,)

by fixing all of the vertices of T, sending v_i^t to v_i^s if f_i(s) = t, and sending v_i^t to v_i of t is not in the image
of f_i.

As in Section <ref>,
we say that a contraction φ:G(,)→ G' 
factors nontrivially if there exists a non-identity morphism :[]→[] in 
and a contraction ψ:G(,)→ G' such that φ = ψ∘Ψ_T,().



The sprouting functor Φ_G,:→ has property (F).



The philosophy of the proof is nearly identical to that of Proposition <ref>.
Property (F) says exactly that, for any graph G' of genus g, the set of contractions 
from some G(,) to G' that do not factor nontrivially is finite.
Let ψ:G(,)→ G' be given.
We have 
    |G(,)| = |G| + ||,
 so ψ must contract |G| + || - |G'| edges.
If || is sufficiently large, then at least one of those edges must be one of the newly sprouted edges.
We may then factor ψ nontrivially by first contracting that edge.

This tells us that, if we are looking for contractions from some G(,) to G' that do not factor nontrivially,
we only need to consider finitely many r-tuples .  The proposition then
follows from the fact that all Hom sets in  are finite.


The proof of the following corollary is identical to the proof of Corollary <ref>, so we omit it.


Let k be a field, and suppose that M∈_k() is d-smallish.  
Then there exists a multivariate polynomial f_M,G,(t_1,…,t_r)
of total degree at most d such that, if  is sufficiently large in every coordinate, 

    _k M(G(,)) = f_M,G,(m_1,…,m_r).






 §.§ Combining small modules

This section is devoted to stating and proving a lemma that we will need in Section <ref>.

Let H be a graph of genus h with no loops.  For each vertex v∈‖(H), fix a natural number g_v
and a _g_v-module N_v.  Let g:= h + ∑_v g_v.
Consider the -module N defined by putting

    N(G) := ⊕_ψ:G→ H⊗_v∈‖(H) N_v(ψ^-1(v)),

where the sum is over all smooshings ψ:G→ H with the property that ψ^-1(v) has genus g_v
for all v. 
If φ:G→ G' is a contraction, the induced map N(G')→ N(G) kills the ψ summand
unless all of the edges contracted by φ are also contracted by ψ.  If this is the case, then there is an induced
smooshing ψ':G'→ H whose fibers are contractions of the fibers of ψ, and these contractions
induce a natural map from the ψ summand
of N(G) to the ψ' summand of N(G').


In the above situation, suppose that N_v is d_v-small for all v∈‖(H), and let d := |H| + ∑_v d_v.
Then the -module N is d-small.



We may immediately reduce to the case where each N_v is a principal projective.
That is, for all v∈‖(H), we have 
N_v = P_G_v for some fixed graph G_v of genus g_v
with d_v edges.  The k-module N(G) is spanned by classes indexed by tuples of maps
in which the set of edges that do not get contracted has cardinality d and includes all of the loops.  
Thus, if G has more than d edges, at least one edge is a non-loop that does not get contracted,
which means that our class may be pulled back from some nontrivial contraction of G.




§ HOMOLOGY OF CONFIGURATION SPACES

The purpose of this section is to prove Theorem <ref>.
Our main technical tool is the reduced Świątkowski complex of An, Drummond-Cole, and Knudsen <cit.>.
Sections <ref> and <ref> are reproduced
from <cit.> for the reader's convenience.



 §.§ The reduced Świątkowski complex

Let A_G be the integral polynomial ring generated by the edges of G. 
For any vertex v, let S(v) denote the free A_G-module generated by the symbol ∅
along with all half-edges of G with vertex v.
We equip S(v) with a bigrading by defining an edge to have degree (0,1), ∅ to have degree (0,0),
and a half-edge to have degree (1,1).  Let (v)⊂ S(v) be the submodule generated by the elements
∅ and h - h' for all half-edges h and h'.  We equip (v) with an A_G-linear differential ∂_v
of degree (-1,0) by putting 
    ∂ (h-h') := (e(h)-e(h')) ∅∂∅ = 0.

We then define the
reduced Świątkowski complex

    (G)   :=  ⊗_v ∈‖(G)S(v),

where the tensor product is taken over the ring A_G; this is a bigraded free A_G-module with a differential ∂.

For any graph G, let H_∙(_⋆(G)) denote the bigraded abelian group

    H_∙(_⋆(G)) := ⊕_(i,n) H_i(_n(G); ).


<cit.>
If G has no isolated vertices, then
there is an isomorphism of bigraded abelian groups

    H_∙(_⋆(G)) ≅ H_∙((G)).




If G is connected, then the only way that G can have isolated vertices
is if G is a single point.  In this case, H_∙((G)) = (G) =, concentrated in bidegree (0,0),
whereas H_∙(_⋆(G)) ≅⊕, concentrated in bidegrees (0,0) and (0,1).
Thus the reduced Świątkowski complex fails only to recognize that the degree zero homology of _1(G) is nontrivial.





 §.§ Functoriality

If φ:G → G' is contraction, then there is a natural map of differential bigraded modules

    φ^∗:(G') →(G),

which induces a map 
    φ^∗: H_i(_n(G'); )→ H_i(_n(G); )

by passing to homology <cit.>.
To describe φ^∗, we first consider the case where the number of edges of G is one greater than the number of edges of G';
we call such a contraction φ a simple contraction.
We identify the unique edge of G that is contracted by φ with the interval [0,1].
Let h_0 (respectively h_1) be the half-edge of G consisting of the vertex 0 (respectively 1) and the edge [0,1].
Let w'∈ G' be the image of the edge [0,1].
Each edge of G' is mapped to isomorphically by a unique edge of G, and similarly for half-edges.  
This gives us a canonical ring homomorphism A_G'→ A_G along with an A_G'-module homomorphism

    ⊗_v' ∈‖(G')∖{w'}S(v')    →⊗_v ∈‖(G)∖{0,1}S(v).

Given a half-edge h' of G' with v(h') = w', let h be the unique half-edge of G mapping to h'.
We then define an A_G'-module homomorphism 
    S(w')→S(0)⊗S(1)

by the formula 
    ∅↦∅⊗∅ h'↦
    (h-h_0) ⊗∅   if v(h)=0
    ∅⊗ (h-h_1)   if v(h)=1.

Tensoring these two maps together, we obtain the homomorphism φ^∗:(G') →(G),
and it is straightforward to check that this homomorphism respects the differential.
Arbitrary contractions may be obtained as compositions of simple contractions, and the induced homomorphism is independent of choice of factorization into simple contractions.
To summarize, we have the following result.

<cit.>
There is a bigraded differential -module that assigns to each graph G the reduced Świątkowski complex (G).
The homology of this bigraded differential -module is the bigraded -module that assigns to each graph G
the bigraded Abelian group H_∙(_⋆(G)).









 §.§ Smallness

We are now ready to prove Theorem <ref> and Corollary <ref>.


Given a graph G and a pair of natural numbers i and n, let (G)_i,n be the degree (i,n) summand of the 
reduced Świątkowski complex. 
We will show that the -module taking G to the abelian group (G)_i,n
is generated in degrees ≤ g+i+n.  Smallness will then follow from Theorem <ref>.

The group (G)_i,n is generated by elements of the form 

    σ := e_1⋯ e_n-i  ⊗_j=1^i  (h_j0 - h_j1)   ⊗⊗_v∉{v_1,…,v_i}∅,

where e_1,…,e_n-i are edges (not necessarily distinct), v_1,…,v_i are vertices (distinct), and, for each j,
h_j0 and h_j1 are half-edges at the vertex v_j.
For a particular σ of this form, we will call {v_1,…,v_i} the set of distinguished vertices.
Without loss of generality, we may assume that there is some integer r with 0≤ r≤ i such that v_j
is adjacent to some distinguished vertex (possibly itself) if and only if j≤ r.  We may also assume that, if j≤ r,
e(h_j1) connects v_j to some distinguished vertex (again, possibly v_j itself).  If not, then σ may be written as a difference
of classes of this form.

We call an edge e a distinguished edge if one of the following five conditions hold:


  * e is a loop

  * e connects two distinguished vertices

  * e = e_k for some k≤ n-i

  * e = e(h_j0) for some j≤ i

  * e = e(h_j1) for some j≤ i.

We will now argue that there are at most g+i+n distinguished edges.
Let t be the number of loops that are not at distinguished vertices.
Let H be the induced subgraph on {v_1,…,v_r}, which in particular contains all of the loops that are at distinguished vertices.
Since H is a subgraph of G, and is missing t loops, it has genus at most g-t, which means that it has at most
r + g - t edges.  (Equality is achieved if and only if r=0 and G is obtained by attaching g loops to a tree,
in which case H is empty and t=g.)
This means that the total number of distinguished edges is at most

    t + (r + g - t) + (n-i) + i + (i-r) = g+i+n.


Let G be given with |G| > g+i+n.  Since there are at most g+i+n distinguished edges, we may choose an edge e
which is not distinguished.
Let G' := G/e be the graph obtained from G by contracting e, and let φ:G→ G' be the canonical simple
contraction.  
Let e_k' be the image of e_k in G', v_j' the image of v_j in G', h_j0'
the image of h_j0 in G', and h_j1' the image of h_j1 in G'.  Let

    σ' := e'_1⋯ e'_n-i  ⊗_j=1^i  (h_j0' - h_j1')   ⊗⊗_v'∉{v'_1,…,v'_i}∅   ∈   (G')_i,n.

We claim that σ=φ^*σ'.

If e is not incident to any vertex v_j, this is obvious.
The interesting case occurs when e is incident to one of the distinguished
vertices.  Assume without loss of generality that it is incident to v_1, and let w be the other end point of e.

Let h be the half-edge of T with e(h) = e and v(h) = v_1 (this uniquely characterizes h because e is not a loop).
Applying the map φ^* replaces each e_k' with e_k.  When j>1, it replaces h_j0' with h_j0
and h_j1' with h_j1.  It replaces h_10' with h_10 - h and h_11' with h_11-h.
This means that it replaces h_j0' - h_j1' with h_j0 - h_j1, and therefore that 
φ^*σ' = σ.

We thus conclude that every element of (G)_i,n is a linear combination
of elements in the images of map associated with simple contractions; this completes the proof.



Let T_g,i,n∈_() be the module that assigns to each graph G the torsion subgroup of H_i(_n(G); ).
By Theorem <ref>, T_g,i,n is a submodule of a finitely generated module, and is therefore itself finitely generated.
We may then take d_g,i,n to be the least common multiple of the exponents of the generators.







§ KAZHDAN–LUSZTIG COEFFICIENTS

For each G, let R_G be the ℂ-subalgebra of rational functions in the variables {x_v| v∈‖(G)}
generated by the elements {1/x_v-x_wv≠ w adjacent}, and let X_G :=  R_G.
The ring R_G is called the Orlik-Terao algebra of G and the variety X_G is called the reciprocal plane of G.
We will be interested in the intersection homology group _2i(X_G) with coefficients in the complex numbers.

If φ:G→ G' is a contraction, we obtain a canonical map from 
_2i(X_G') to _2i(X_G), and these maps compose in the expected way
<cit.>.  The purpose of this section is to study the -module
_2i that takes G to _2i(X_G), and in particular to prove Theorem <ref>.  



 §.§ Orlik-Solomon algebras

For each G, let ^∙(G) be the Orlik-Solomon algebra <cit.>
of the matroid associated with G with coefficients in the complex numbers.
For any natural number i, we will denote the linear dual of ^i(G) by _i(G).
For the purposes of this paper, we will need to know four things about the Orlik-Solomon algebra:


  * ^1(G) is spanned by classes {x_e| e∈(G)}, with relations x_e = x_f if e and f are parallel
and x_e = 0 if e is a loop.

  * ^∙(G) is generated as a ℂ-algebra by ^1(G).

  * If G' is a contraction of G, we obtain a functorial map ^∙(G)→^∙(G') 
by killing the generators indexed by contracted edges.  This in turn induces a map _∙(G')→_∙(G).

  * If G is the disjoint union of G_1 and G_2, then ^∙(G) ≅^∙(G_1)⊗^∙(G_2).

By the third bullet point above, _i is a -module for any natural number i.


For any natural number i, _i is (g+i)-small.



Recall from Lemma <ref> the -module E that assigns to any graph the ℂ-vector space with basis given by the edges.
By the first two bullet points above, ^i(G) is a quotient of the  tensor power of E(G)^*, therefore _i is a submodule of 
E^⊗ i.  Lemma <ref> says that E^⊗ i is generated in degrees ≤ g+i, therefore _i is (g+i)-small.




 §.§ The spectral sequence

A subgraph F⊂ G with the same
vertex set is called a flat of G
if its edge set is the set of contracted edges of a smooshing to a graph with no loops, which is denoted G/F.
Thus the vertex set of G/F is identified with the set of connected components of F,
and the edge set is identified with (G)∖(F).
The rank of F is defined as the number of vertices
minus the number of connected components, and the corank of F, denoted F, is
the number of connected components minus 1.
The following theorem was proved in <cit.>; see also <cit.>.


For any graph G and natural number i, there is a first quadrant homological spectral sequence E(-,i)
in the category of -modules converging to _2i,
with 
    E(G,i)^1_p,q = ⊕_ F = p_2i-p-q(F) ⊗_2(i-q)(X_G/F).

If φ:G→ G' is a contraction, the induced map 
E(G',i)^1_p,q→ E(G,i)^1_p,q kills the F-summand unless F contains all of the edges contracted by φ.  
In this case, the image of F
in G' is a flat F' of G', and G'/F' is canonically isomorphic to G/F.  The map takes
the F-summand of E(G,i)^1_p,q to the F'-summand of E(G',i)^1_p,q by 
the canonical map _2i-p-q(F)→_2i-p-q(F') tensored with the identity map on _2(i-q)(X_G/F).










 §.§ Smallness



By Theorem <ref>, _2i admits a filtration whose associated graded is isomorphic to the infinity page of E(-,i),
therefore it is sufficient to show that, for all p and q, E(-,i)^1_p,q is
(2i-1+g)-small.


The set of flats of G is in bijection with equivalence classes of smooshings with source G
for which the target has no loops, where two such smooshings
are equivalent if they differ by an automorphism of the target.  We therefore have

    E(G,i)^1_p,q ≅⊕_|‖(H)| = p+1( ⊕_ψ:G→ H
    smooshing(⊗_v∈‖(H)_*(ψ^-1(v)))_2i-p-q⊗  _2(i-q)(X_H))^(H).

If we fix H and require that the graph ψ^-1(v) has genus g_v,
Lemmas <ref> and <ref> together imply that E(-,i)^1_p,q is d-small, where d = |H| + 2i-p-q + ∑_v g_v.
If h is the genus of H, then |H| = p + h and ∑_v g_v = g-h, so d = 2i + g - q.  Since this is independent of the choice
of H or of the numbers g_v, we can conclude that E(-,i)^1_p,q is (2i+g-q)-small.

Finally, we note that _2(i-q)(X_H) = 0 unless 2(i-q) < p or q=i and p=0 <cit.>, while _2i-p-q(F) = 0
unless p+q ≤ 2i.
In particular E(-,i)^1_p,0 = 0 for all p, which implies that each E(-,i)^1_p,q is
(2i-1+g)-small.



The module _0 = E(-,0)^1_0,0 is the constant module taking every graph to ℂ and every morphism to the identity.
This module is g-small rather than (g-1)-small, which is why we required that i be positive in the statement of Theorem <ref>.
Indeed, one can see that the last sentence of the proof fails when p=q=i=0.



When g=1, Theorem <ref> and Corollary <ref> combine to say that the 
 Kazhdan–Lusztig coefficient of the n-cycle should eventually agree with a polynomial in n
of degree at most 2i.  In fact, it is equal to <cit.>

    1/i+1n-i-2ini,
 so our result is sharp.



Let G_g(a_1,…,a_g+1) be the genus g>0 graph obtained by taking the graph with two vertices and g+1 edges between
them and subdividing the i^th edge into a_i pieces.  Theorem <ref> and Corollary <ref> say that the first Kazhdan–Lusztig
coefficient of G_g(a_1,…,a_g+1) should eventually agree with a multivariate polynomial of total degree at most g+1 in a_1,…,a_g+1.

The first Kazhdan–Lusztig
coefficient is equal to the number of corank 1 flats minus the number of rank 1 flats <cit.>.
If a_i > 1 for all i, this is equal to

    ∏_i=1^g+1 a_i + ∑_i=1^g+1a_i2 - ∑_i=1^g+1 a_i.

Thus our result is again sharp.




§ OUTER CATEGORY

The purpose of this section is to describe how one may use the category  to compute cohomology groups
of (F_g) with arbitrary coefficients.



 §.§ Nerves of categories

We begin by briefly reviewing some facts about small categories and their nerves. 

Let  be a small category. Then we define the nerve || of  to be the geometric realization
of the simplicial set defined as follows.  The 0-simplicies are in bijection with the objects of , while the i-simplicies 
for i>0 are in bijection with i-tuples of morphisms

    (f_1,…,f_i)

such that, for each 0 ≤ j ≤ i, the codomain of f_j+1 agrees with the domain of f_j. For each i > 0 and 1 ≤ j ≤ i+1 the face map ∂_j is defined by

    ∂_j(f_1,…,f_i) =  (f_2,…,f_i)     if j = 0
     (f_1,…,f_i-1)     if j = i+1
     (f_1,…,f_j-2,f_j-1∘ f_j, f_j+1,… ,f_i)  otherwise.

The degeneracy map σ_j is defined by

    σ_j(f_0,…,f_i) = (f_0,…, f_j-1,𝕀,f_j,…,f_i),

where 𝕀 is the identity map on the domain of f_j-1 (or the codomain of f_j). 


We immediately see that there is a canonical homeomorphism || ≅ |^|.
A functor between two categories induces a map between their nerves, and an equivalence of categories
induces a homotopy equivalence between the nerves.


Let k be a commutative ring, and let 



∈_k() be the module that takes every object to the 1-dimensional vector space k
and every morphism to the identity map.  The following standard result can be found, for example, in <cit.>.


There is a canonical graded k-algebra homomorphism __k()^*(,)≅ H^*(||; k).





 §.§ Outer category and the cohomology of (F_g)

We begin with the following result, which relies heavily on Culler and Vogtman's work on outer space <cit.>.


The nerves || and || are contractible. 



The categories  and  are equivalent, therefore Remark <ref> tells us that it is sufficient to prove
that || is contractible.  By Proposition <ref>,  is a poset category, which implies that || is homeomorphic
to the order complex of the poset structure on the set of objects.  This order complex is called the spine of outer space,
and it is known to be contractible <cit.>.


Recall that we have an action of the group (F_g) on the category , which induces an action on the nerve.
We also have a functor Φ:→^small given by forgetting the marking, 
and this functor induces a map
Φ_*:||→ |^small| of nerves.


The action of (F_g) on || is free and proper, and Φ_*:||→ |^small|
is the quotient map.



The fact that the action is free and proper follows from the fact that it is free on the set of objects (which correspond to 0-simplices)
and each group element acts by a simplicial map.  To see that Φ_* is the quotient map, we need to show that
it is surjective and its fibers coincide with the orbits of (F_g).  This follows from the fact that (F_g)
acts transitively on the set of markings of a reduced graph of genus g.



The nerve |^small| is a classifying space for the group (F_g).



Let us consider the very simple case where g=1, which we began discussing in Example <ref>.  
The category _1^tiny has only one object (an oriented loop)
and no nontrivial morphisms, so its nerve is a point.  The category _1^small has two objects, namely a loop
with two different orientations, and these two objects are uniquely isomorphic.  The nerve of _1^small is an 
infinite-dimensional sphere S^∞, and the group (F_1)≅ S_2 acts via the antipodal map with quotient P^∞.
The category _1,red^small has a single object with automorphism group S_2,
so its nerve is homeomorphic to P^∞, which is a classifying space for S_2.



For any commutative ring k, we have __k(^)^*(,)≅ H^*((F_g); k).



To compute __k(^)^*(,), we may replace  with the equivalent category
^small.  The result then follows from Remark <ref>, 
Theorem <ref>, and Corollary <ref>.



Given a pair of modules M∈_k() and N∈_k(^), we will write M
to denote the restriction of M to _k(^) and N^! to denote the extension of N by zero to _k().
The functors M↦M and N↦ N^! are exact and the former is left adjoint to the latter,
therefore ^*__k(^)(M, N)≅^*__k()(M,N^!).
If we apply this fact with M = ^! and N =,
we see that Theorem <ref> is equivalent to Corollary <ref>.




 §.§ A sample calculation

We now use Corollary <ref> to compute the first cohomology of (F_2)≅GL(2; )
with coefficients in an arbitrary field k.  

In particular, we illustrate the extent to which
the representation theory of finite groups (namely automorphism groups of graphs) can be used to aid our calculations.

As in Section <ref>, there are exactly two reduced graphs of genus 2 up to isomorphism, namely
the rose ∞ and the melon .  The automorphism group of the rose is D_4, while the automorphism
group of the melon is S_3× S_2.
Let φ_1, φ_2, and φ_3 be the three contractions from the melon to the rose obtained by cyclically
permuting the edges and then contracting the middle one.
Up to post-composition by an automorphism of the rose, every contraction is of this form.

Let P_∞∈_k((_2,red^small)^) be the principal projective module corresponding to the rose, 
and consider the surjection P_∞→ that sends every basis element to 1.
Let K be the kernel of this homomorphism.  Applying the functor (-,) gives us the long exact sequence

    0→(,)→(P_∞,)→(K,)→^1(,)→^1(P_∞,).

An element of (P_∞,) is determined by its value on the identity morphism of ∞, which implies that
the first map (,)→(P_∞,) is an isomorphism.  The fact that P_∞ is projective
implies that ^1(P_∞,) = 0, thus (K,)→^1(,) must also be an isomorphism.
We therefore want to compute (K,).

An element of (K,) is a pair[Here
we are using the symbol k to denote the 1-dimensional trivial representations of both D_4 and S_3× S_2.]

    (f,g)∈_D_4(K(∞),k)×_S_3× S_2(K(),k)

satisfying the condition that, if we pre-compose g with any of the three
inclusions K(∞)→ K() induced by φ_1, φ_2, and φ_3, we obtain f.

Let's start by computing _S_3× S_2(K(),k) and _D_4(K(∞),k).  The group S_3× S_2 acts freely on the set of contractions
from the melon to the rose with two orbits, which we will call the untwisted contractions and the twisted contractions.
The untwisted contractions consist of the orbit that includes the three maps φ_i, and the twisted contractions consist of untwisted
contractions followed by an automorphism of the rose that fixes one of the two loops and reverses the orientation of the other loop.
We therefore have P_∞()≅ k[S_3× S_2] ⊕ k[S_3× S_2] as representations of S_3× S_2.


The space of homomorphisms from P_∞() to k is 2-dimensional, with a basis given by the homomorphisms
that take the sum of the coefficients of the twisted or untwisted maps.
Applying _S_3× S_2(-,k) to 
the short exact sequence 0→ K()→ P_∞()→ k→ 0 and noting that P_∞() is a projective representation
of S_3× S_2, we obtain the long exact sequence

    0→_S_3× S_2(k,k)→_S_3× S_2(P_∞(),k)→_S_3× S_2(K(),k)→^1_S_3× S_2(k,k)→ 0.

Since the abelianization of S_3× S_2 is S_2× S_2, we have ^1_S_3× S_2(k,k) = 2 if k has characteristic 2 and 0 otherwise.
Hence _S_3× S_2(K(),k) = 3 if k has characteristic 2 and 1 otherwise.  A similar argument for the rose tells us
that _D_4(K(∞),k) = 2 if k has characteristic 2 and 0 otherwise.

Let's find explicit bases for our Hom spaces.  Let h_1:K()→ k be the homomorphism that
adds the coefficients of the untwisted maps in K()⊂ P_∞().  This homomorphism is well defined and nonzero for any field k.
Let h_2:K()→ k be the homomorphism that adds the coefficients of C_3× S_2⊂ S_3× S_2 for both the twisted
and untwisted maps and let 
h_3:K()→ k be the homomorphism that adds the coefficients of S_3×{𝕀}⊂ S_3× S_2 for both the twisted
and untwisted maps.  Each of these homomorphisms is well defined if and only if the characteristic of k is 2, in which case it is straightforward to check
that {h_1,h_2,h_3} is a basis for _S_3× S_2(K(),k).
Let f_1:K(∞)→ k add the coefficients of the untwisted automorphisms of the rose (those generated by horizontal and vertical reflections),
and let f_2:K(∞)→ k add the coefficients of the automorphisms that keep the left loop on the left and the right loop on the right.
Each of these homomorphisms is well defined if and only if the characteristic of k is 2, in which case it is straightforward to check
that {f_1,f_2} is a basis for _S_3× S_2(K(),k).

Finally, we observe that h_1 restricts to f_1 and h_2 restricts to f_2 under all three inclusions of K(∞) into K().
On the other hand, the restriction of h_3 to K(∞) fails to be D_4-equivariant and depends on the choice of inclusion of K(∞) into K().
We therefore conclude that

    H^1((F_2); k) =  2    if char(k) =2
     0    otherwise.



This result can also be obtained by working directly with a presentation for (F_2), such as the one in <cit.>.
This presentation can be used to compute the abelianization, and H^1((F_2); k) is isomorphic to the vector space of group homomorphisms
from the abelianization to k.






amsalpha

