Skip to Main Content

The Graph Minor Theorem Meets Algebra

Eric Ramos

Communicated by Notices Associate Editor Steven Sam

Article cover

1. The Graph Minor Theorem

The Graph Minor Theorem of Robertson and Seymour is one of the most celebrated results in the history of combinatorics, spanning decades (and hundreds of pages) of work. In this note we discuss recent work of Miyata, Proudfoot, and the author that proposes a framework that would allow one to apply the Graph Minor Theorem to algebra and topology, building on seminal contributions by Sam and Snowden. Though the capstone of this framework is still only conjectural (See Conjecture 2.3), a weaker version (See Theorem 2.4) of the capstone has been proven and already has far ranging consequences in topological combinatorics and algebra. Specifically, we will discuss applications of this framework to the study of matching complexes and configuration spaces of graphs.

To begin, let’s standardize terminology by defining a graph to be a (non-empty) finite, connected, at most one-dimensional CW-complex. If one prefers to think about graphs in terms of collections of edges, , and vertices, , then our provided definition essentially amounts to saying that our graphs will always be finite, connected, and may have multi-edges and loops. The theory of graphs, having essentially begun in work of Euler, has developed into one of the most foundational subjects in all of mathematics, being pivotal in numerous fields such as combinatorics, algebra, and many others. For the purposes of this note, we will focus specifically on the theory of graph minors.

Definition 1.1.

Let be a graph, and let be an edge that is not a loop. Then the contraction of is the (necessarily homotopy equivalent) graph obtained from by crushing to a point. If is an edge (that may be a loop) whose removal does not disconnect , then the deletion of is the graph obtained from by removing the edge without removing its end points.

Given two graphs , we say that is a minor of if is isomorphic to a graph that can be obtained from by a sequence of edge deletions and contractions. The minor relation imposes a partial order on the collection of graphs, and we write .

One of the early triumphs in the study of graph minors, which was also one of the great accomplishments of early topological graph theory, is the following theorem, independently discovered by Kuratowski and Wagner. By definition a graph is planar if it can be embedded in the plane.

Theorem 1.2 (Kuratowski and Wagner).

Let be a graph. Then is planar if and only if it admits neither the complete graph on 5 vertices , nor the complete bipartite graph , as a minor.

Important here is that not only does there exist a completely classifiable collection of so-called “forbidden” minors, but that this collection is finite. While one might expect that this finiteness is a consequence of the rigidity of the plane, in fact it is the result of something far more general.

Theorem 1.3 (Robertson and Seymour, RS04).

Let be any collection of graphs. Then there exists a finite collection of graphs in that are minimal with respect to the minor order (restricted to ). Equivalently, if is any collection of graphs which is closed under taking minors, then there exists some finite collection of graphs such that for any graph , is in if and only if does not admit any of the graphs as a minor.

The conclusion of the Graph Minor Theorem is often summarized as saying that the graph minor relation is a well-quasi-order. The Kuratowski–Wagner theorem tells us that if is the (minor closed) class of planar graphs, then the finite collection of forbidden minors is precisely . Obviously, however, the Graph Minor Theorem is far more powerful than Kuratowski–Wagner, as it guarantees such a finite forbidden minor classification must exist for any minor closed property. It should be noted however, that the neither Graph Minor Theorem nor its proof provide any way to actually determine the finite collection of forbidden minors for any given minor property! While there are some circumstances where such an explicit characterization has been accomplished, the vast majority remain out of our reach. Famously, there is a collection of 17,523 graphs which are known to be forbidden minors for toroidal graphs, i.e., graphs that can be embedded into the torus, though it is unknown whether this list is exhaustive!

We take the time here to also point out that the Graph Minor Theorem generalizes a long list of well known well-quasi-order theorems. These include (in increasing order of generality) Dickson’s Lemma – that the coordinate-wise poset on is a well-quasi-order, Higman’s Lemma – that the poset of words on a well-quasi-ordered poset is itself well-quasi-ordered, and Kruskal’s Tree Theorem – that the poset of rooted trees is well-quasi-ordered.

2. The Categorical Graph Minor Theorem

Moving on from the classical combinatorics of the Graph Minor Theorem, we would now like to move the reader in the direction of its categorification. Categorification is not something that has a completely rigorous definition, but rather something you just kind of “know” when you see it. It can oftentimes be summarized by the following statement: all non-negative integers, regardless of the counting problem that spawned them, are secretly the dimensions of some vector spaces, whose algebra encodes and expands upon the originating combinatorics. Of course, our ultimate goal is to apply a kind of Graph Minor Theorem to problems arising from algebra and topology, and so the most natural first step in this process is to take the combinatorial content of the Graph Minor Theorem and expand it into the realms of algebra.

Under this somewhat vague guidance one often finds that statements like the Graph Minor Theorem – that a given poset is a well-quasi-order – translate to a Noetherianity statement in the algebraic context of the categorification. Our next major goal will be to make all of this more precise by first introducing the graph minor category . Before we get into the most technical details of this construction, we present an example from topological combinatorics that will hopefully motivate why one would want a kind of “categorical” Graph Minor Theorem.

If is a graph, we define the matching complex to be the simplicial complex whose -simplicies are collections of edges of , , with no overlapping endpoints, i.e., matchings of size . The homology groups of these spaces have been of considerable interest in topological combinatorics for many years Wac03Jon10. This is especially true of the cases where is a complete graph or is a complete bipartite graph.

Now if one knows , as well as the data of which edges of were deleted or contracted to obtain , one can see that the edges of naturally include into those of in such a way that edges which were non-adjacent in must also be non-adjacent in . In particular, if is an -simplex of , then one has a naturally associated -simplex of . This association then induces a map between the abelian groups

We have therefore now found ourselves in a situation where for each graph we have a finitely generated abelian group , with the additional structure that whenever is a minor of another graph , there is a natural homomorphism,

In a situation such as this, one would hope that a categorical version of the Graph Minor Theorem would imply a kind of finite generation for the entirety of . In other words, it would imply the existence of a finite collection of graphs such that for any graph the group is spanned by the images of the groups , for all such that . In other words, the algebraic content of all possible -th homology groups is entirely determined by a finite amount of information. Such extreme finiteness would imply a kind of universality in the presentations of these groups, which in turn would imply, as one particular example, a uniformity in the kinds of torsion that can possible appear. We will return to the example of the matching complex in later sections.

We are now ready to give a few formal definitions.

Definition 2.1.

The Graph Minor Category is the category whose objects are graphs, and whose morphisms are minor morphisms. A minor morphism is a map of sets,

satisfying the following conditions:

and ;

if has endpoints , and , then either is a vertex of , or is an edge of with endpoints and ;

maps bijectively onto ;

for any vertex , the preimage , thought of as a subgraph of , is a tree.

The edges of that maps to the character are said to be deleted by , whereas the edges that maps to a vertex of are said to be contracted by .

Let us take a moment now to explain more thoroughly the four conditions of a minor morphism. The first condition states that the morphism only sends vertices to other vertices (i.e., not to edges), and that it does so surjectively. This condition also asserts that the “deletion character” must map to itself. The second condition asserts that for any given edge , with endpoints , one of three things must happen: either the edge is deleted (i.e., mapped to the deletion character), it is contracted to the vertex in which case and must also be mapped to , or it is mapped to a new edge whose endpoints must be the images of the endpoints of and . The third condition states that the edges of that are neither deleted nor contracted can be uniquely identified with edges of . Note that we will usually think about this condition in the opposite way, that if

is a minor morphism, then the edges of can be found living inside of . Finally, the last condition amounts to saying that minor morphisms are only allowed to contract trees within , i.e., cycles may not be contracted. The primary content one should takeaway from this description is that

One should also note that the category is not simply the opposite category of the graph minor poset. Indeed, the minor morphisms also encode information about which edges are being deleted and contracted, as well as possible movement of the vertices via graph automorphisms, i.e., permutations of the vertex set that preserve the adjacency relation.

Definition 2.2.

A -module is a covariant functor from to the category of finitely generated abelian groups. Concretely, a -module is a collection of abelian groups , one for each graph , such that for every minor morphism (equivalently for every realization of as a minor of ), there is a homomorphism , defined in such a way so-as to respect composition of minor morphisms. We say that a -module is finitely generated if there is a finite collection of graphs such that for any graph , is spanned by the images of the groups induced by all possible minor morphisms . We often refer to the graphs as generators of the module.

Note that we have changed from to precisely because we want our morphisms to go in the same direction as the minor relation. Let’s take a quick moment to look at some simple examples of -modules.

The Trivial Module: For each graph we set , whereas for every minor morphism we assign the identity map. This module is generated by the graph with a single vertex and no edges.

The Edge Module: For each graph we set , the free abelian group on the edges of . We have already discussed that any minor morphism induces an inclusion , and we use this inclusion to define the map . This module is generated by the line segment and the loop.

The Spanning Tree Module: For each graph we set to be the free abelian group on the spanning trees of . Any minor morphism can be used to map a spanning tree of to one of by including the edges of this tree into while also adding in the edges of that we contracted by the minor morphism. This module is once again generated by a single point, as a minor morphism to a point is equivalent to a choice of spanning tree.

The Homology of the Matching Complex: For any fixed , the collection of groups form a -module, as outlined above. It is conjectured that this module is finitely generated, though the justification for this is far from obvious! We will return to this example in later sections.

As the usage of “module” suggests in the name -module, virtually any intuition or construction that one has from the classical theory of rings and modules will carry over into this context. In particular, terms such as kernel, cokernel, and submodule continue to have meaning here using the most natural possible definitions. Moreover, the condition of being finitely generated has implications that go beyond the most obvious. For instance,

MPR20 Uniform Boundedness of Torsion: If is finitely generated, then there exists an integer such that for any graph , the exponent (i.e., largest non-trivial torsion) of the group divides .

MR20 Uniform Boundedness of Rank: If is finitely generated, then there exists a polynomial such that, for any graph , the rank of the group is at most , where is the number of spanning trees in .

Note that the Spanning Tree Module illustrates that the bound given in the second point is actually sharp.

As suggested earlier, a proper categorification of the Graph Minor Theorem should have something to say about Noetherianity of some algebra. This is indeed the case.

Conjecture 2.3 (The Categorical Graph Minor Theorem).

Let denote a finitely generated -module. Then all submodules of are finitely generated.

A proof of Conjecture 2.3 was originally claimed in MPR20, though a gap was discovered in the proof which, as of the writing of the present article, has not yet been filled. To see how this conjecture relates with the Graph Minor Theorem, let be any minor-closed set of graphs, and consider the following example. Let denote the -submodule of the trivial module for which

By definition is a submodule of the trivial module, and therefore must be finitely generated, provided that Conjecture 2.3 is true. That is, there is some finite collection of graphs , for which the groups contain all algebraic content appearing in . Thus, the containment problem for (i.e., whether or not is zero) is determined entirely by whether or not you have one of the as a minor. This is precisely the Graph Minor Theorem!

Just as the Graph Minor Theorem generalizes a wide variety of classical well-quasi-order theorems, one can see that the Categorical Graph Minor Theorem generalizes or implies many Noetherianity statements. See SS17 for an overview of such statements. Also see Sno13 for the Noetherianity statement associated to Higman’s Lemma, and Bar15 for the Noetherianity associated to Kruskal’s Tree Theorem. This last example is especially relevant for what we will now call the Weak Categorical Graph Minor Theorem, whose proof follows from the work of PR, which built on the work of Bar15.

For a given graph , its combinatorial genus is defined as the quantity . For instance, having combinatorial genus equal to 0 is equivalent to being a tree.

Theorem 2.4 (The Weak Categorical Graph Minor Theorem).

Let be an integer, and let be the full subcategory of whose objects are graphs with combinatorial genus at most . If is a finitely generated -module, all of its submodules are also finitely generated.

The theorems of the next section will all be stated in terms of the subcategory , however all of them could be extended the the whole of provided that Conjecture 2.3 were verified. One should also note that this combinatorial genus stratification of the graph minor category is not the only one that one might try to apply. It would be interesting to see whether the subcategories of bounded tree-width or other well known “minor-monotone” graph invariants have representations with similar Noetherianity statements.

3. Applications

In this section we detail some applications of the Categorical Graph Minor Theorem to problems arising from topology. To start, let’s return to the setup from last chapter related with the matching complex. Recall that for a graph , the matching complex is the simplicial complex whose -simplices are matchings of edges of . We showed last chapter that for any fixed the assignment is a well-defined -module, and therefore also a -module for all . We will now show that this module is also finitely generated as a -module.

To begin, let denote the -module for which is the free abelian group on collections of edges of . For instance, is precisely the restriction of the Edge Module to . We see that is finitely generated by, for instance, the set of all graphs with edges. Moreover, the simplicial -chains of are easily seen to be a submodule of , and therefore must also be finitely generated. Taking it one step further the -module is a subquotient of the simplicial -chains, and must also be finitely generated. This concludes the proof. Note this exact proof would also prove finitely generated for the full -module, provided Conjecture 2.3.

The above proof is an extremely common and effective means for proving that a given -module is finitely generated: find some -module that is easily shown to be finitely generated, and realize your module as an explicit subquotient. In some cases things don’t work out quite as directly, but often one can at least find a spectral sequence that converges to your module, and the ultimate conclusion remains the same. Once again we note that the feature of finite generation has a number of non-trivial consequences. For instance one has the following.

Theorem 3.1 (Miyata and Ramos, MR20).

There exists an integer such that for any graph of combinatorial genus at most , the exponent of divides .

Torsion in the matching complex is something that has received a fair amount of attention in recent years, where it is noted that all torsion thus far discovered have orders that are small primes Jon10.

It should also be noted that one limitation of this style of proof is that it gives you almost no control over what the generators are. Such control could be given if one were to develop a robust computational theory similar to the classical theory of Gröbner bases for the representation theories of Sam-Snowden Gröbner Categories, that we touch upon in the final section. This remains an interesting avenue for future research.

The reader may have noticed that the proof of finite generation is extremely generalizable. In particular, a large number of graph complexes will have similar finitely generated homologies, and therefore, for instance, bounded torsion. Examples of such complexes include the complex of bounded degree subgraphs, complexes of triangle-free subgraphs, complexes of -colorable subgraphs, and more. For more on these complexes, see the book Jon08, as well as the references therein.

Another class of interesting examples comes from the study of configuration spaces.

Definition 3.2.

For any topological space and any integer the configuration space on on -points is the quotient space

where the symmetric group acts by permuting coordinates.

Configuration spaces have been a topic of serious study for decades, although much of what is understood relates with cases wherein is a manifold. More recently, however, there have been considerable advances made in the theory of configuration spaces of graphs ADCK19AK20Ghr01. One question of considerable interest with regards to these spaces is whether or not their homology ever admits odd torsion. An affirmative answer to this question would have implications as far ranging as physics and robotics Ghr01.

Let be a graph and a fixed integer. It is an interesting fact that any minor morphism will induce a map ADCK19. Using these maps, we now find ourselves with new -modules . Using the Weak Categorical Graph Minor Theorem, the following is proven in PR.

Theorem 3.3 (Proudfoot, and Ramos, PR).

For any , the -module is finitely generated. In particular, there exists some integer such that the order of any torsion appearing in divides .

It was proven by Ko and Park KP12 that for any graph the first homology group has torsion if and only if is non-planar, and that any torsion which appears must be 2-torsion. The above theorem therefore shows that this kind of behavior is one instance of something more general.

As with the matching complex example, it is not currently known what the generators are for the modules for most choices of , , and . There are two notable cases where it is known or partially known, however. For and any , the generators are the loop as well as all star graphs (that is, trees with one vertex of degree and all other vertices of degree 1) with edges ADCK19. For , and , although the full generating set is not known, we do know what the planar generators are. These will be the dumbbell graph of a line segment with a loop on either end, the graph that looks like the letter Y with a loop attached to one of its leaves, and the banana graph of two vertices connected by 4 edges AK20. As a side note, this third generator is particularly special, as contains a class which is not toric (i.e., a product of two copies of ). In fact, it is represented by a surface of genus 3 CL18WG17! Further note that all of these cases show that the generators do not depend on when , a fact which supports the suggestion that Theorem 3.3 can be extended to the whole graph minor category. As with all theorems in this work, the proof of Theorem 3.3 for the whole of would be immediate provided the verification of 2.3.

It can be shown that the integer of the previous theorem does not actually depend on MR20. This strengthening comes from the topology and combinatorics of the situation, and in particular depends on more than just the (Weak) Categorical Graph Minor Theorem. Let’s consider this now.

One of the great early tools used in the study of configuration spaces of manifolds was the idea to “add a point at infinity.” Namely, to introduce a homotopy class of maps

and see the behavior of the induced directed system on homology. It therefore becomes natural to ask whether one is able to introduce points to , whenever is a graph. The answer to this question is yes! In fact, for every edge of one will have a map,

which one can think of as introducing a new point on the edge . These maps were first constructed, though only at the level of homology, by the author in the case of trees Ram18. Independently, the full construction at the level of topology described below was achieved by An, Drummond-Cole, and Knudsen ADCK19ADCK20a, who also expanded it to all graphs . To illustrate how this map is defined, imagine having placed points on , and consider those points appearing on an edge . Fix for now an identification of with the interval and list (in order from left to right) all points appearing on as well as the end points . The image of this configuration under leaves any points not on unchanged, whereas it replaces each of the original points on with the midpoint of itself and the next member of the list just constructed. Therefore, for instance, if had no points on it originally, the new configuration will have precisely one point at the center of . On the other hand, if the original configuration had one point on the interior of , then the new configuration will have two points on , one at the midpoint of and the original point and one at the midpoint of the original point and . We give an illustration of this map in Figure 1.

Figure 1.

An example of the map . In this picture the end points of the edge are colored in black, while the points coming from the configuration are in white.

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture} \tikzstyle{every node}=[draw,circle,fill=white,minimum size=4pt, inner sep=0pt] \draw(0,0) node (0) [fill = black, label=above:] {} --(.5,0) node (1) {} --(1,0) node (2) {} --(2,0) node (3) {} --(4,0) node (4) [fill = black, label=above:]{}; \draw[-stealth] (2,-1) -- (2,-3); \draw(0,-4) node (5) [fill = black, label=above:] {} --(.25,-4) node (6) {} --(.75,-4) node (7) {} --(1.5,-4) node (8) {} --(3,-4) node(9) {} --(4,-4) node (10) [fill = black, label=above:]{}; \end{tikzpicture}

Using this construction, the following theorem was proven.

Theorem 3.4 (An, Drummond-Cole, and Knudsen, ADCK19).

For and any graph , write for the graded abelian group

Then the edge stabilization maps 1 induce an action by the polynomial ring , endowing with the structure of a finitely generated graded module over this ring.

The above theorem now allows us to study configuration spaces of graphs from the perspective of commutative algebra. There are a variety of results in this vein, one of which we now spotlight. Recall that for a finitely generated graded module over a polynomial ring, the function

is in eventual agreement with a polynomial – the Hilbert polynomial of the module. Let be a graph not homeomorphic to a loop, and write for the largest number of connected components that can be broken into by the removal of exactly vertices of degree at least 3. By convention, if has less than vertices of degree at least 3. The following theorem was proven for trees by the author, and for all graphs by An, Drummond-Cole, and Knudsen ADCK20a.

Theorem 3.5 (An, Drummond-Cole, and Knudsen ADCK20a).

Let be a graph that is not homeomorphic to a loop. Then for all the degree of the Hilbert polynomial of is precisely .

Note that in followup work An, Drummond-Cole, and Knudsen also computed the leading coefficient of the Hilbert polynomial, once again in terms of invariants of ADCK20b. One consequence that immediately follows from this theorem is that if is biconnected, that is, if removal of any vertex does not disconnect the graph, then the degree of the Hilbert polynomial of is zero. In particular, the rank of is constant in . This fact was observed much earlier by Ko and Park KP12 using totally different means. We therefore see that these homology groups seem to encode an eclectic collection of properties of the graphs including planarity and connectivity. It is an active line of research to understand what other graph theoretic properties can be found inside these spaces.

Thinking about the homology groups as a family with two varying parameters, and , we have now seen that one obtains finite generation results by fixing one and varying the other. It is then natural to ask whether these two orthogonal results can be made compatible with one another. This is indeed the case!

Definition 3.6.

Let be a graph. The (free) edge algebra of is the polynomial ring on the edges of ,

We define the universal edge algebra to be the functor

defined on objects by

and on morphisms in the same way as the Edge Module. An -module is a -module such that is an -module for every , and for every minor morphism and element , the following diagram commutes,

An -module is said to be finitely generated if there exists a finite set of graphs such that for any graph , is spanned (note here that spanning is in reference to the -action) by the images of the . As with everything else in this section, we may also consider , defined by restricting to .

We saw above that for any , the assignment

defines an -module. As another example, consider the ideal of generated by products , whenever are not adjacent to one another. It is clear that the action of minor morphisms preserves this condition of being non-adjacent, and therefore is an -submodule of .

For any fixed graph , the edge algebra clearly satisfies a Noetherian property by virtue of it being a polynomial ring. What is much less clear is whether each of these individual Noetherian properties can be glued together, so to speak, to say something about modules over the universal algebra . While we once again must keep the full-strength statement in the realm of conjecture, one can say the following.

Theorem 3.7 (Miyata, Proudfoot, and Ramos, MPR20).

If is a finitely generated -module, then all -submodules of are also finitely generated.

To prove this version of this theorem for -modules, one would need the Categorical Graph Minor Theorem, as well as a kind of universal Gröbner basis approach MPR20. By consequence, we see that for any finitely generated -module , not only is determined by for some finite list of graphs , but the syzygies of , in the commutative algebra sense, are also all determined by some (possibly different) finite list of graphs. This is precisely why the universal exponent of Theorem 3.3 does not depend on .

4. An Outline of the Proof

In this section we provide an outline of the proof of the Weak Categorical Graph Minor Theorem 2.4. We do this not only to spotlight the beautiful underlying theory, due to Sam and Snowden SS17, but also because we believe it does a good job of illustrating how the combinatorics of the Graph Minor Theorem informs the algebra of the Weak Categorical Graph Minor Theorem. The content of this section is a bit more on the technical side, though we have omitted many details in an attempt to make it more readable. We also end the work by pointing out what exactly the difficulty is in lifting the weak result to the full strength of Conjecture 2.3, and how one would presumably aim to fix it.

We begin, as Sam and Snowden did in their seminal work SS17, by recalling the Hilbert Basis Theorem. For the purposes of this discussion write , where is a fixed commutative Noetherian Ring. The Hilbert Basis Theorem then states that all submodules of any finitely generated module must be finitely generated. That is, that finitely generated modules over must be Noetherian. The proof of the Hilbert Basis Theorem that we will concern ourselves with is the standard approach through Gröbner bases, and proceeds as follows: To begin, we apply standard reductions to show that we only need to prove that submodules (i.e., ideals) of itself must be finitely generated. Next, consider the lexicographical order on monomials in . This order not only imposes a well-order on all monomials, but also has the property of being preserved under multiplication. In particular, we may therefore define the leading term of any element to be the largest monomial among all those appearing in . Now given any ideal of , one defines the initial ideal to be the ideal generated by the leading terms of all elements in . A standard argument then shows that is finitely generated if and only if is, whence it suffices to prove that all monomial ideals are finitely generated. If we encode monomials of as elements in , then the standard coordinate-wise partial order on is seen to be equivalent to the divisibility partial order on monomials. Therefore, that monomial ideals are finitely generated is equivalent to the fact that the standard coordinate-wise order on does not permit infinite anti-chains. This latter fact is true according to Dickson’s Lemma, and we are done.

To summarize, the above proof of the Hilbert Basis Theorem proceeds in three major steps:

(1)

Reduce the problem from all finitely generated modules, to free (finitely generated) modules;

(2)

Define a well-order on the set of monomials that respects the action of the ring. Use this well-order to reduce the problem to monomial-generated submodules of the free module;

(3)

Encode divisibility of monomials into some poset that is known to not have infinite anti-chains. Use this to deduce that all monomial-generated submodules of the free module must be finitely generated, concluding the proof.

It is the great innovation of SS17 that the above three steps can be replicated in contexts similar to the -modules of the current note. They refer to this as the theory of Gröbner categories and their modules. We consider each of the above three steps in turn.

To begin, what are the “free” -modules? For any fixed graph of combinatorial genus at most we define,

the free abelian group on the -set . The maps induced by minor morphisms are then defined by precomposition. For instance, if is the graph with one vertex and no edges, then,

is the Spanning Tree module from above. For numerous homological reasons related with the vanishings of certain derived functors, it turns out that the modules are each appropriate to be called “free.” Note that this is analogous to the context of graded modules over the ring , where there is one free module for each natural number. The same style of argument which allowed one to reduce to submodules of free modules in the proof of the Hilbert Basis Theorem will continue to work here, allowing us to reduce the Weak Categorical Graph Minor Theorem to proving that the submodules of the are finitely generated.

Fixing now a graph of combinatorial genus at most for all time, Sam and Snowden SS17 define a monomial of to be any natural basis element . Our Step 2 insists that we should come up with some well-order on these monomials that respects the action of the maps induced by minor morphisms. Unfortunately, this is actually impossible! Indeed, because minor morphisms include graph automorphisms, if has any non-trivial automorphisms then we will not be able to well-order our monomials in a way consistent with this action. Sam and Snowden come up with a solution to this (fairly common) problem in the following way: Instead of thinking about our original category , consider modules over a different category which is more rigid than , in the sense that it has no automorphisms, while also not being “too different” from . It is proven that in this circumstance a Noetherian property for modules over implies the same for modules over .

In the original work SS17, Sam and Snowden make this idea of not being too different precise using what they call Property (F). Property (F) is a feature of a functor that generalizes the property of being a right adjoint. Instead of getting too deep in the technicalities here, we illustrate the spirit of Property (F) with an example. Consider the category whose objects are the finite ordinals and whose morphisms are injections. This category also clearly has automorphisms (namely, the permutations), so we instead consider the category of finite ordinals with order preserving injections. This category does not have non-trivial automorphisms, and is also very closely related with , in that for any and any injection of sets , there is always an ordered injection that agrees with the original injection up to precomposition by some permutation of . In other words, for any , there is a finite collection of morphisms (e.g., the permutations of ) such that every injection originating from agrees with an ordered injection originating from up to one of these morphisms. Sam and Snowden loosely describe this phenomenon as having a sort of finite index within SS17.

Coming back to our Graph Minor Category, the challenge now becomes to choose the correct category . It turns out the category we are looking for is the category whose objects are graphs of genus at most , that have been equipped with a choice of a rooted and planar spanning tree, as well as a direction and ordering of its extra (outside the given spanning tree) edges. The morphisms of this category will be contractions that preserve all of this structure. By demanding all of the extra structure that was added be preserved, we have eliminated all automorphisms. Moreover, essentially because any graph can only be given the extra data of a rooted spanning tree and directions on its extra edges in finitely many ways, as well as the fact that the restriction on disallows arbitrarily long chains of deletions, the forgetful functor can be seen to have Property (F). We can therefore assume that we have been working with the category this entire time, that our fixed graph has been given the data of both a planar rooted spanning tree, and directions and orderings of its extra edges, and re-examine our Step 2. In this case, the desired well-order is presented in PR.

Step 3 asks us to encode the divisibility relation of monomials into some poset that is known to not admit infinite anti-chains. So what exactly is the divisibility relation between monomials in our setting? Well, for traditional monomials over the polynomial ring, divisibility meant that there was some some element of the ring for which one monomial was times the other. Using our definition of monomials in free -modules we see that this naturally translates to say that is divisible by if and only if there is some morphism in such that . Translating the relationship between minor morphisms and the minor relation, this tells us that the divisibility relationship between monomials is the minor relation limited to the set of directed and edge-ordered graphs containing as a minor. While the Graph Minor Theorem as previously presented does not guarantee that this poset has no infinite anti-chains (because of the extra data we’ve imposed on each graph) there is a stronger labeled version of the Graph Minor Theorem RS10, as well as an order preserving version of Kruskal’s Tree Theorem Bar15, that does give us what we want.

Looking closely at everything discussed above, it is hopefully clear that the only thing preventing us from proving Conjecture 2.3 is choosing the right category . This trick of choosing a rooted spanning tree will no longer work here! In fact, to the knowledge of the author, there are no currently known “rigidifications” of the Graph Minor Theorem that are immediately applicable, just as we relied on the rigidified Tree Theorem for the bounded genus case. Presumably, proving such a rigidification would require one to have very deep intimate knowledge of how the original Graph Minor Theorem is proven.

Acknowledgment

The author would like to send his unending gratitude to Nicholas Proudfoot. He would also like to send his thanks to the anonymous referees whose suggestions greatly improved the exposition of the article. The author was supported by NSF grant DMS-2137628.

References

[ADCK19]
Byung Hee An, Gabriel C. Drummond-Cole, and Ben Knudsen, Subdivisional spaces and graph braid groups, Doc. Math. 24 (2019), 1513–1583. MR4033833Show rawAMSref\bib{ADK}{article}{ label={ADCK19}, author={An, Byung Hee}, author={Drummond-Cole, Gabriel C.}, author={Knudsen, Ben}, title={Subdivisional spaces and graph braid groups}, journal={Doc. Math.}, volume={24}, date={2019}, pages={1513--1583}, issn={1431-0635}, review={\MR {4033833}}, } Close amsref.
[ADCK20a]
Byung Hee An, Gabriel C. Drummond-Cole, and Ben Knudsen, Edge stabilization in the homology of graph braid groups, Geom. Topol. 24 (2020), no. 1, 421–469, DOI 10.2140/gt.2020.24.421. MR4080487Show rawAMSref\bib{ADK-stabilization}{article}{ label={ADCK20a}, author={An, Byung Hee}, author={Drummond-Cole, Gabriel C.}, author={Knudsen, Ben}, title={Edge stabilization in the homology of graph braid groups}, journal={Geom. Topol.}, volume={24}, date={2020}, number={1}, pages={421--469}, issn={1465-3060}, review={\MR {4080487}}, doi={10.2140/gt.2020.24.421}, } Close amsref.
[ADCK20b]
Byung Hee An, Gabriel C. Drummond-Cole, and Ben Knudsen, Subdivisional spaces and graph braid groups, Doc. Math. 24 (2019), 1513–1583. MR4033833Show rawAMSref\bib{ADK3}{article}{ label={ADCK20b}, author={An, Byung Hee}, author={Drummond-Cole, Gabriel C.}, author={Knudsen, Ben}, title={Subdivisional spaces and graph braid groups}, journal={Doc. Math.}, volume={24}, date={2019}, pages={1513--1583}, issn={1431-0635}, review={\MR {4033833}}, } Close amsref.
[AK20]
Byung Hee An and Ben Knudsen, On the second homology of planar graph braid groups, arXiv preprint arXiv:2008.10371 (2020).
[Bar15]
Daniel Barter, Noetherianity and rooted trees, arXiv preprint arXiv:1509.04228 (2015).
[CL18]
Safia Chettih and Daniel Lütgehetmann, The homology of configuration spaces of trees with loops, Algebr. Geom. Topol. 18 (2018), no. 4, 2443–2469, DOI 10.2140/agt.2018.18.2443. MR3797072Show rawAMSref\bib{CL}{article}{ label={CL18}, author={Chettih, Safia}, author={L\"{u}tgehetmann, Daniel}, title={The homology of configuration spaces of trees with loops}, journal={Algebr. Geom. Topol.}, volume={18}, date={2018}, number={4}, pages={2443--2469}, issn={1472-2747}, review={\MR {3797072}}, doi={10.2140/agt.2018.18.2443}, } Close amsref.
[Ghr01]
Robert Ghrist, Configuration spaces and braid groups on graphs in robotics, Knots, braids, and mapping class groups—papers dedicated to Joan S. Birman (New York, 1998), AMS/IP Stud. Adv. Math., vol. 24, Amer. Math. Soc., Providence, RI, 2001, pp. 29–40, DOI 10.1016/s0167-2789(01)00343-8. MR1873106Show rawAMSref\bib{Gh-robotics}{article}{ label={Ghr01}, author={Ghrist, Robert}, title={Configuration spaces and braid groups on graphs in robotics}, conference={ title={Knots, braids, and mapping class groups---papers dedicated to Joan S. Birman}, address={New York}, date={1998}, }, book={ series={AMS/IP Stud. Adv. Math.}, volume={24}, publisher={Amer. Math. Soc., Providence, RI}, }, date={2001}, pages={29--40}, review={\MR {1873106}}, doi={10.1016/s0167-2789(01)00343-8}, } Close amsref.
[Jon08]
Jakob Jonsson, Simplicial complexes of graphs, Lecture Notes in Mathematics, vol. 1928, Springer-Verlag, Berlin, 2008, DOI 10.1007/978-3-540-75859-4. MR2368284Show rawAMSref\bib{jonbook}{book}{ author={Jonsson, Jakob}, title={Simplicial complexes of graphs}, series={Lecture Notes in Mathematics}, volume={1928}, publisher={Springer-Verlag, Berlin}, date={2008}, pages={xiv+378}, isbn={978-3-540-75858-7}, review={\MR {2368284}}, doi={10.1007/978-3-540-75859-4}, } Close amsref.
[Jon10]
Jakob Jonsson, More torsion in the homology of the matching complex, Experiment. Math. 19 (2010), no. 3, 363–383, DOI 10.1080/10586458.2010.10390629. MR2731551Show rawAMSref\bib{jon}{article}{ label={Jon10}, author={Jonsson, Jakob}, title={More torsion in the homology of the matching complex}, journal={Experiment. Math.}, volume={19}, date={2010}, number={3}, pages={363--383}, issn={1058-6458}, review={\MR {2731551}}, doi={10.1080/10586458.2010.10390629}, } Close amsref.
[KP12]
Ki Hyoung Ko and Hyo Won Park, Characteristics of graph braid groups, Discrete Comput. Geom. 48 (2012), no. 4, 915–963, DOI 10.1007/s00454-012-9459-8. MR3000570Show rawAMSref\bib{KP}{article}{ label={KP12}, author={Ko, Ki Hyoung}, author={Park, Hyo Won}, title={Characteristics of graph braid groups}, journal={Discrete Comput. Geom.}, volume={48}, date={2012}, number={4}, pages={915--963}, issn={0179-5376}, review={\MR {3000570}}, doi={10.1007/s00454-012-9459-8}, } Close amsref.
[MPR20]
Dane Miyata, Nicholas Proudfoot, and Eric Ramos, The categorical graph minor theorem, arXiv preprint arXiv:2004.05544 (2020).
[MR20]
Dane Miyata and Eric Ramos, The graph minor theorem in topological combinatorics, arXiv preprint arXiv:2012.01679 (2020).
[PR]
Nicholas Proudfoot and Eric Ramos, The contraction category of graphs, arXiv:1907.11234.
[Ram18]
Eric Ramos, Stability phenomena in the homology of tree braid groups, Algebr. Geom. Topol. 18 (2018), no. 4, 2305–2337, DOI 10.2140/agt.2018.18.2305. MR3797068Show rawAMSref\bib{TreeStab}{article}{ label={Ram18}, author={Ramos, Eric}, title={Stability phenomena in the homology of tree braid groups}, journal={Algebr. Geom. Topol.}, volume={18}, date={2018}, number={4}, pages={2305--2337}, issn={1472-2747}, review={\MR {3797068}}, doi={10.2140/agt.2018.18.2305}, } Close amsref.
[RS04]
Neil Robertson and P. D. Seymour, Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004), no. 2, 325–357, DOI 10.1016/j.jctb.2004.08.001. MR2099147Show rawAMSref\bib{RSXX}{article}{ label={RS04}, author={Robertson, Neil}, author={Seymour, P. D.}, title={Graph minors. XX. Wagner's conjecture}, journal={J. Combin. Theory Ser. B}, volume={92}, date={2004}, number={2}, pages={325--357}, issn={0095-8956}, review={\MR {2099147}}, doi={10.1016/j.jctb.2004.08.001}, } Close amsref.
[RS10]
Neil Robertson and Paul Seymour, Graph minors XXIII. Nash-Williams’ immersion conjecture, J. Combin. Theory Ser. B 100 (2010), no. 2, 181–205, DOI 10.1016/j.jctb.2009.07.003. MR2595703Show rawAMSref\bib{RSXXIII}{article}{ label={RS10}, author={Robertson, Neil}, author={Seymour, Paul}, title={Graph minors XXIII. Nash-Williams' immersion conjecture}, journal={J. Combin. Theory Ser. B}, volume={100}, date={2010}, number={2}, pages={181--205}, issn={0095-8956}, review={\MR {2595703}}, doi={10.1016/j.jctb.2009.07.003}, } Close amsref.
[Sno13]
Andrew Snowden, Syzygies of Segre embeddings and -modules, Duke Math. J. 162 (2013), no. 2, 225–277, DOI 10.1215/00127094-1962767. MR3018955Show rawAMSref\bib{Snowden-Syzygies}{article}{ label={Sno13}, author={Snowden, Andrew}, title={Syzygies of Segre embeddings and $\Delta $-modules}, journal={Duke Math. J.}, volume={162}, date={2013}, number={2}, pages={225--277}, issn={0012-7094}, review={\MR {3018955}}, doi={10.1215/00127094-1962767}, } Close amsref.
[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, DOI 10.1090/jams/859. MR3556290Show rawAMSref\bib{sam}{article}{ label={SS17}, author={Sam, Steven V.}, author={Snowden, Andrew}, title={Gr\"{o}bner methods for representations of combinatorial categories}, journal={J. Amer. Math. Soc.}, volume={30}, date={2017}, number={1}, pages={159--203}, issn={0894-0347}, review={\MR {3556290}}, doi={10.1090/jams/859}, } Close amsref.
[Wac03]
Michelle L. Wachs, Topology of matching, chessboard, and general bounded degree graph complexes, Algebra Universalis 49 (2003), no. 4, 345–385, DOI 10.1007/s00012-003-1825-1. Dedicated to the memory of Gian-Carlo Rota. MR2022345Show rawAMSref\bib{wach}{article}{ label={Wac03}, author={Wachs, Michelle L.}, title={Topology of matching, chessboard, and general bounded degree graph complexes}, note={Dedicated to the memory of Gian-Carlo Rota}, journal={Algebra Universalis}, volume={49}, date={2003}, number={4}, pages={345--385}, issn={0002-5240}, review={\MR {2022345}}, doi={10.1007/s00012-003-1825-1}, } Close amsref.
[WG17]
John D. Wiltshire-Gordon, Models for configuration space in a simplicial complex, Colloq. Math. 155 (2019), no. 1, 127–139, DOI 10.4064/cm7331-5-2018. MR3887191Show rawAMSref\bib{WG}{article}{ label={WG17}, author={Wiltshire-Gordon, John D.}, title={Models for configuration space in a simplicial complex}, journal={Colloq. Math.}, volume={155}, date={2019}, number={1}, pages={127--139}, issn={0010-1354}, review={\MR {3887191}}, doi={10.4064/cm7331-5-2018}, } Close amsref.

Credits

The opening image is courtesy of enot-poloskun via Getty.

Figure 1 and photo of the author are courtesy of the author.