Coloring graphs with polynomials

More chromatic hoonja-doonja!

Suppose you have a bunch of tokens of different colors and weights.  X_1 colors of weight 1 tokens, X_2 colors of weight 2 tokens, etc.

Let Γ be a graph.  A (weighted) b-coloring of Γ is an assignment to each vertex of a set of tokens with total weight b, such that adjacent vertices have no tokens in common.  Let χ_Γ(X_1, … X_b) be the number of b-colorings of Γ.  I made up this definition but I assume it’s in the literature somewhere.

 

First of all, χ_Γ(X_1, … X_b) is a polynomial.

Is this multivariable “chromatic polynomial” of any interest?  Well, here’s one place it comes up.  By a degree-b polynomial coloring of Γ we mean an assignment of a monic squarefree degree d polynomial in R[x] to each vertex of Γ, so that adjacent vertices are labeled with coprime polynomials.   Now let U_b(Γ) be the manifold parametrizing degree-b colorings of Γ.

Then the Euler characteristic of U_b(Γ) is χ_Γ(-1,1,0,…0).

I worked this out via the same kind of Lefschetz computation as in the previous post, but once you get the answer, you can actually derive this as a corollary of Stanley’s theorem.  And it was presumably already known.

By the way:  let V_n be the free vector space spanned by the b-colorings of Γ where all the tokens have weight 1; these are called fractional colorings sometimes.  Then S_n acts on V_n by permutation of colors.  The character of this action is a class function on S_n.  More precisely, it is

χ_Γ(X_1, … X_b)

where X_i is now interpreted as a class function on S_n, sending a permutation to the number of i-cycles in its cycle decomposition.  Of course the real thing going on behind the scenes is that the V_n form a finitely generated FI-module.

Configuration spaces of manifolds with flows (with John Wiltshire-Gordon)

New preprint up on the arXiv:  “Algebraic structures on cohomology of configuration spaces of manifolds with flows,” a short paper joint with John Wiltshire-Gordon.

John is a student at Michigan, finishing his Ph.D. this year under David Speyer, and he’s been thinking about stuff related to FI-modules ever since his undergrad days at Chicago hanging out with Benson Farb.

But this paper isn’t actually about FI-modules!  Let me explain.  Here’s the motivating question.  When M is a manifold, and S a finite set, we denote by PConf^S M the pure configuration space of M, i.e. the space of injections from S to M.  If S is the set 1,…,n we write PConf^n M for short.

Question:  Let M be a manifold.  What natural algebraic structure is carried by the cohomology groups H^i(PConf^n M,Z)?

Here’s one structure.  If is an injection, composition yields a map from PConf^T M to PConf^S M, which i turn yields a map from H^i(PConf^S M, Z) to  H^i(PConf^T M, Z).  In other words,

is a functor from the category of finite sets with injections to the category of k-vector spaces.  Such a functor is called an FI-module over k.  A big chunk of my paper with Benson Farb and Tom Church is devoted to figuring out what consequences this structure has for the Betti numbers, and it was by these means that Tom first proved that the unordered configuration spaces have stable cohomology with rational coefficients.  (This is actually false with integral coefficients, or when the coefficient field has characteristic p, but see the beautiful theorem of Rohit Nagpal for the story about what happens in the latter case.  How have I not blogged about that already?)

So it turns out that H_i(PConf M) is a finitely generated FI-module (the definition is what you expect) and this implies that the Betti number h^i(PConf^n M) agrees with some polynomial P_i(n) for all sufficiently large n.  For example, H_1(PConf^n S^2) has dimension

(1/2)n(n-3)

for n >= 3, but not for n=0,1,2.

If you know a little more about the manifold, you can do better.  For instance, if M has a boundary component, the Betti number agrees with P_i(n) for all n.  Why?  Because there’s more algebraic structure.  You can map from PConf^T to PConf^S, above, by “forgetting” points, but you can also add points in some predetermined contractible neighborhood of the boundary.  The operation of sticking on a point * gives you a map from PConf^S to PConf^{S union *}.  (Careful, though — if you want these maps to compose nicely, you have to say all this a little more carefully, and you really only want to think of these maps as defined up to homotopy; perfectly safe as long as we’re only keeping track of the induced maps on H^i.)

We thought we had a pretty nice story:  closed manifolds have configuration spaces with eventually polynomial Betti numbers, manifolds with boundary have configuration spaces with polynomial Betti numbers on the nose.  But in practice, it seems that configuration spaces sometimes have more stability than our results guaranteed!  For instance, H_1(PConf^n S^3) has dimension

(1/2)(n-1)(n-2)

for all n>0.  And in fact EVERY Betti number of the pure configuration space of S^3 agrees with a polynomial P_i(n) for all n > 0; the results of CEF guarantee only that h^i agrees with a polynomial once n > i.

What’s going on?

In the new paper, John and I write about a different way to get “point-adding maps” on configuration space.  If your M has the good taste to have an everywhere non-vanishing vector field, you can take any one of your marked points x in M and “split it” into two points y and y’, each very near x along the flowline of the vector field, one on either side of x.  Now once again we can both add and subtract points, as in the case of open manifolds, and again this supplies the configuration spaces with a richer structure.  In fact (exercise!) H_i(PConf^n M) now carries an action of the category of noncommutative finite sets:  objects are finite sets, morphisms are set maps endowed with an ordering of each fiber.

And fortunately, John already knew a lot about the representation theory of this category and categories like it!  In particular, it follows almost immediately that, when M is a closed manifold with a vector field (like S^3) the Betti number h^i(PConf^n M) agrees with some polynomial P_i(n) for all n > 0.  (For fans of character polynomials, the character polynomial version of this holds too, for cohomology with rational coefficients.)

That’s the main idea, but there’s more stuff in the paper, including a very beautiful picture that John made which explains how to answer the question “what structure is carried by the cohomology of pure configuration space of M when M has k nonvanishing vector fields?”  The answer is FI for k=0, the category of noncommutative finite sets for k=1, and the usual category of finite sets for k > 1.

Jenny Wilson on FI-modules beyond type A

When I talk about FI-modules and their relation with representations of the symmetric group, people often ask me, what about the other classical Weyl groups? The answer is that Jennifer Wilson, a student of Benson Farb’s at Chicago, has worked it all out, in her paper “FI_W–modules and stability criteria for representations of the classical Weyl groups,” available at her webpage.  Lots of nice stuff in here — she revisits a theorem she already proved about stabilization of the cohomology of the string motion group, providing a much simpler proof, she gives a version of Murnaghan’s theorem for the hyperoctahedral group, she gets results on the cohomology of the complement of the hyperplane arrangement corresponding to the relevant Weyl group, etc.

It seems that type D is the hardest, and direct analogues of the approach that Benson, Tom and I used don’t work — in order to get there, she has to develop a notion of induction between these categories; just as one induces from representations of a smaller group to representations of a bigger one, she needs to induce from her category of FI_D-modules up to the more restrictive category of FI_B-modules.  To accomplish this uses the (exotic, to me) theory of Kan extensions, and this ends up allowing her to use the theorems she proves in type B, which is closer to classical representation theory, to prove the desired theorems in type D.  Cool!

I had sort of feared that there would be terrifying complications for types B and D in characteristic 2, but apparently not!  That’s handsome.

 

FI-modules over Noetherian rings

New paper on the arXiv, joint with Tom Church, Benson Farb, and UW grad student Rohit Nagpal.  In our first paper on FI-modules (which I blogged about earlier this year) a crucial tool was the fact that the category of FI-modules over a field of characteristic 0 is Noetherian; that is, a submodule of a finitely generated FI-module is again finitely generated.  But we didn’t know how to prove this over a more general ring, which limited the application of some of our results.

In the new paper, we show that the category of FI-modules is Noetherian over an arbitrary Noetherian ring.  Sample consequence:  if M is a manifold and Conf^n M is the configuration space of ordered n-tuples of distinct points on M, then we show that

dim_k H_i(Conf^n M, k)

is a polynomial function of n, for all n greater than some threshold.  In our previous paper, we could prove this only when k had characteristic 0; now it works for mod p cohomology as well.  We also discuss some of the results of Andy Putman’s paper on stable cohomology of congruence subgroups — it is a bad thing that I somehow haven’t blogged about this awesome paper! — showing how, at the expense of losing stable ranges, you can remove from his results some of the restrictions on the characteristic of the coefficient field.

Philosophically, this paper makes me happy because it brings me closer to what I wanted to do in the first place — talk about the representation theory of symmetric groups “for general n” without giving names to representations.  In characteristic 0, this desire might seem a bit perverse, given the rich and beautiful story of the bijection between irreducible representations and partitions.  But in characteristic p, the representation theory of S_n is much harder to describe.  So it is pleasing to be able to talk, in a principled way, about what one might call “representation stability” in this context; I think that when V is a finitely generated FI-module over a finite field k it makes sense to say that the representations V_n of k[S_n] are “the same” for n large enough, even though I don’t have as nice a description of the isomorphism classes of such representations.

 

 

 

 

FI-modules and representation stability, III

So how does this paper work?  The main idea is quite simple.  Let’s come back to the example of V_n = H^i(Conf^n M,Q), with i fixed and n ranging over nonnegative integers.  Then we have a sequence of vector spaces

V_0, V_1, V_2, …

But more than a sequence.  You have a map Conf^{n+1} -> Conf^n which is “forget the n+1 st point” — which functorially hands you a map V_n -> V_{n+1}.  So you have a diagram

V_0 -> V_1 -> V_2 -> …..

But in fact you have even more than this!  There’s no reason you have to forget just the n+1 st point.  You have tons of maps from Conf^n to Conf^m for all m <= n; one for each m-element subset of 1..n.  And there are lots of natural identifications between the compositions of these maps.  When you keep track of all the maps at your disposal, what you find is that the vector spaces V_n have a very rigid structure.

Definition:  FI is the category of finite sets with injections.  An FI-module over a ring R is a functor from FI to R-modules.

So V is an FI-module over Q!  (The vector space V_n is revealed as the image of the finite set [1..n] under the functor V.) And the main work of our paper is the study of the category of FI-modules, which sheds a great deal of light on representation stability.  For instance, we show that an FI-module over Q yields a representation-stable sequence in Church-Farb’s original sense if and only if it is finitely generated in the natural sense.  Moreover, the category of FI-modules over Q is Noetherian, in the sense that subobjects of finitely generated FI-modules are again finitely generation.  (The Noetherianness was proven independently by Snowden in a different form.)  Theorems like this very easy to show that tons of examples in nature (like the ones in the previous post) yield representation-stable sequences.  The work is all in the definitions and basic properties; once you have that, proving stability in particular examples is often a matter of a few lines.  For instance, you get a fairly instant proof of Murnaghan’s theorem on stability of Kronecker products; from this point of view, this becomes a theorem about the finite generation of a single object in an abelian category, rather than a theorem about a list of coefficients eventually setting down to constancy.

Sometimes there is more structure still.  Suppose, for example, that the manifold M above has nonempty boundary.  Then there are not only maps from Conf^{n+1} to Conf^n, but maps going the other way; you can add a new point in a little neighborhood of a boundary component.  (This is familiar from the configuration space of the complex plane, where you add new points at “the west pole” in the infinite negative real direction.)  These maps don’t quite compose on the nose, but they’re OK up to homotopy, and so the cohomology groups acquire a system of maps going both up and down.  It turns out that the right structure to describe such systems is given by the category of finite sets with partial injections; i.e. a map from A to B is an isomorphism from a subset of A to a subset of B.  We call this category FI#, and we call a functor from FI# to R-modules an FI#-module over R.

When your vector spaces carry an FI#-module structure you can really go to town.  It turns out that all the “eventuallies” disappear; when M is an open manifold, the dimension of H^i(Conf^n M) is a polynomial in n on the nose, for all n.  What’s more, if you want to show finite generation for FI#-modules, it suffices to show that dim V_n is bounded by some polynomial in n.  Once it’s less than a polynomial, it is a polynomial!  This stuff, unlike some other results in our paper, works in any characteristic and in fact is even fine with integral coefficients.

FI-modules and representation stability, II

Here are some sequences of vector spaces.  In each case, the sequence is indexed by n, and all other variables are understood to be constant.  So suppose V_n is the space

• H^i(Conf^n M, Q) for M a connected oriented manifold of dimension at least 2.
• The (j_1, .. j_r)-multidegree piece of the diagonal coinvariant algebra on r sets of n variables.
• H^i(M_{g,n},Q), the cohomology of the moduli space of curves of genus g with n marked points.
• The tautological subring of the above.
• The space of degree-d polynomials on the rank variety parametrizing nxn matrices of rank at most r.

By a character polynomial we mean a polynomial with integral coefficients in variables X_1, X_2, X_3, … .  We interpret these symbols (and thus character polynomials) as class functions on the symmetric group by S_n by taking

X_i(s) = number of i-cycles in s

for each permutation s.

Then we show that, in each of the examples above, there’s a character polynomial P such that the character of the action of S_n on V_n is given by P, for all sufficiently large n.  This is one way in which one can say that a sequence of representations of larger and larger symmetric groups are “all the same.”  In particular, by plugging in the identity we find that dim V_n is a polynomial in n, for n large enough.

For many of these examples, almost nothing is known about dimensions of individual spaces!  So a strong regularity theorem like this is perhaps surprising.  Even more surprising (to us at any rate) is that theorems like this require only very meager input from whatever context generate the vector spaces.  You get this stability (and many others) almost for free.

More about how it all works tomorrow!

FI-modules and representation stability, I

Tom Church, Benson Farb and I have just posted a new paper, “FI-modules:  a new approach to representation stability,” on the arXiv.  This paper has occupied a big chunk of our attention for about a year, so I’m very pleased to be able to release it!

Here is the gist.  Sometimes life hands you a sequence of vector spaces.  Sometimes these vector spaces even come with maps from one to the next.  And when you are very lucky, those maps become isomorphisms far enough along in the sequence; because at that point you can describe the entire picture with a finite amount of information, all the vector spaces after a certain point being canonically the same.  In this case we typically say we have found a stability result for the sequence.

But sometimes life is not so nice.  Say for instance we study the cohomology groups of configuration spaces of points of n distinct ordered points on some nice manifold M.  As one does.  In fact, let’s fix an index i and a coefficient field k and let V_n be the vector space H^i(Conf^n M, k.)

(In the imaginary world where there are people who memorize every word posted on this blog, those people would remember that I also sometimes use Conf^n M to refer to the space parametrizing unordered n-tuples of distinct points.  But now we are ordered.  This is important.)

For instance, you can let M be the complex plane, in which case we’re just computing the cohomology of the pure braid group.  Or, to put it another way, the cohomology of the hyperplane complement you get by deleting the hyperplanes (x_i-x_j) from C^n.

This cohomology was worked out in full by my emeritus colleagues Peter Orlik and Louis Solomon.  But let’s stick to something much easier; what about the H^1?  That’s just generated by the classes of the hyperplanes we cut out, which form a basis for the cohomology group.  And now you see a problem.  If V_n is H^1(Conf^n C, k), then the sequence {V_n} can’t be stable, because the dimensions of the spaces grow with n; to be precise,

dim V_n = (1/2)n(n-1).

But all isn’t lost.  As Tom and Benson explained last year in their much-discussed 2010 paper, “Representation stability and homological stability,” the right way to proceed is to think of V_n not as a mere vector space but as a representation of the symmetric group on n letters, which acts on Conf^n by permuting the n points.  And as representations, the V_n are in a very real sense all the same!  Each one is

“the representation of the symmetric group given by the action on unordered pairs of distinct letters.”

Of course one has to make precise what one means when one says “V_m and V_n are the same symmetric group representation”, when they are after all representations of different groups.  Church and Farb do exactly this, and show that in many examples (including the pure braid group) some naturally occuring sequences do satisfy their condition, which they call “representation stability.”

So what’s in the new paper?  In a sense, we start from the beginning, defining representation stability in a new way (or rather, defining a new thing and showing that it agrees with the Church-Farb definition in cases of interest.)  And this new definition makes everything much cleaner and dramatically expands the range of examples where we can prove stability.  This post is already a little long, so I think I’ll start a new one with a list of examples at the top.