CAAC 2015 Talk - Why the Fuss?
Thank you for the opportunity to present at my third CAAC. This project is joint work with Christian Stump and Hugh Thomas. In the course of this work, Christian and I have each had a child; to preserve symmetry among authors, we're waiting to publish.
The starting point for this project comes from the Tamari lattice. The Tamari lattice first appeared in the 1951 thesis of Dov Tamari---Tamari was born Bernhard Teitler, but changed his name in 1942. If you haven't seen the Tamari Festschift book, I recommend you pick it up---it begins with a fascinating account of Tamari's life, which contained a surprising quantity of explosives for a mathematician. It's almost as fun as reading some of the threads on Sage-dev.
We'll think of the Tamari lattice in its cluster form as a poset on triangulations of a regular (n+2)-gon for now. Here (n+2) is five, and the cover relations in the poset come from fixing a quadrilateral in a given triangulation and then exchanging the diagonal in the triangulation for the diagonal not in the triangulation. As you can see from the picture of Tamari's thesis, the cover relations were originally described using parenthesizations of n factors. It is perhaps somewhat surprising that this is a lattice, since flips don't indicate how to produce a meet or join.
The number of such triangulations (or parenthesizations) is given by the Catalan numbers, so named because they were discovered in 1751 by Euler---which predated Eugene Catalan's work by nearly 90 years. Igor Pak has a very nice summary of the history of Catalan numbers available on his webpage, in which he attributes the name to Riordan.
In 1795, Nicolas Fuss---the assistant of an elderly Euler, who also predated Catalan, and whose name appears in the title of this talk---counted the number of subdivisions of an (mn+2)-gon into (m+2)-gons. The numbers of such subdivisions are called the Fuss-Catalan numbers, and the Catalan numbers are the special case when m=1. Here we have the 12 quadrangulations of an octogon, so m=2 and n=3.
That the Tamari lattice is a lattice suggests that there should also be a (generalizing) lattice structure on such Fuss-Catalan subdivisions (I don't mean the noncrossing partition lattice). There are actually two distinct problems here:
(1) the first problem is to explicitly describe the of an m-Tamari poset (which we did for m=1 via flips on triangulations);
(2) the second problem is to show that the m-Tamari poset is actually a lattice. (by constructing a meet and join)
Although this might sound strange, from my point of view these are actually two problems (that happen to coincide).
To briefly illustrate the difficulty of the first problem (which I won't address in detail today): what is a "flip" for quadrangulations of an octogon? There is no longer a unique diagonal to choose--so do I choose them both? sometimes one, sometimes the other?
-in type A, where there is a abundance of combinatorial models, one answer is given by Francois Bergeron, using Dyck paths. This does not immediately extend to other finite Coxeter groups, but it does give a lattice. Vivien Pons has been exploring this type A combinatorics recently, including an arxiv posting on Wednesday of this week.
-in general, one might consider the exchange graph of Fomin and Reading's m-cluster complex. This graph has the drawback of not immediately coming with an orientation (which would give a poset structure), and it gives undue special treatment to bipartite Coxeter elements.
-In our work, we give several (equivalent) very explicit answers to this first problem (for any finite Coxeter group and any Coxeter element)---we are able to describe the edge structure on an interpretation of Drew Armstrong's Fuss-analogue of noncrossing partitions, and on our own Fuss construction of subword complexes (which generalize Fomin and Reading's m-cluster complex). Actually, for type A and linear Coxeter element, we get a different structure from Bergeron's m-Tamari lattice!
But knowing the local structure--that is, the edges---is not very helpful for checking if the global structure is a lattice. Being able to flip triangulations doesn't help much for finding a meet or join!
So today I want to focus on the second problem: Why should Fuss objects have a lattice structure?
One nice way to obtain a lattice structure on a set is to expand your view to a set of objects that are already a lattice, and then to embed the small set as a subset of the large set so that the lattice operations preserve your small set.
So the plan for the remainder of this talk is to walk through this rather successful philosophy three times, each time increasing the generality: once for Bjorner and Wach's work on the Tamari lattice, once for Reading's work on Cambrian lattices, and then once for our work on Fuss-Cambrian lattices.
Let's start with why the Tamari lattice is a lattice.
In 1996, Bjorner and Wachs gave an elegant---and from the point of view of problem (2), I would say the "right"---interpretation of the Tamari lattice in terms of the symmetric group. The reason they gave for the Tamari lattice being a lattice came from the weak order. Recall that permutations of [n] form a lattice under weak order, and that 312-avoiding permutations are traditional Catalan objects (we'll see this in more detail in a second). Bjorner and Wachs showed that the intersection of the inversion sets of two 312-avoiding permutations is again the inversion set of a 312-avoiding permutation. In fact, for us, this is the they form a lattice: since the longest element is 312-avoiding and there are finitely many permutations, the join can be constructed in a rather general way---and we can conclude that we have a lattice.
To make this a little precise, let me define the the weak order---the "ambient lattice" in which we will find our Catalan objects.
The symmetric group has the following presentation (which I prefer to symmetrize as a hint of what is to come), an inversion of a permutation (written in one-line notation) is an out-of-order pair, and the inversion set of a permutation is the set of all its inversions. The weak order on the symmetric group is the poset given by u is less than v iff the inversion set of u is contained in the inversion set of v; the meet of two elements u and v is the largest inversion set contained in the intersection of their inversion sets. The weak order is a lattice. Here I've drawn the six permutations of S_3.
Now that we have the "ambient lattice", we'll identify the Catalan component.
A 312-avoiding permutation is just a permutation that doesn't have a triple in one-line notation in the relative order 3-1-2; these are the (inverses of the) stack-sortable permutations, or the sequence of adjacent transpositions you would have to apply to bubble sort the permutation. There are Catalan many 312-avoiding permutations, and here are the five 312-avoiding permutations of S_3 with their corresponding triangulations (I didn't describe the correspondence, but you'll believe me).
Bjorner and Wachs call the inversion sets of 312-avoiding permutations "compressed" inversion sets. The key point to their argument is that the intersection of two compressed inversion sets is again a compressed inversion set. Note that it is true in general that the intersection of two inversion sets is an inversion set. For example, the intersection of 231 and 312 is the inversion (1,3)---which isn't an inversion set.
Then, since the longest element is 312-avoiding, the 312-avoiding permutations ordered by containment of inversion sets form a lattice---and the is that we can explicitly describe the meet using the weak order.
In 1997, Vic Reiner began trying to extend Catalan objects (in particular, noncrossing partitions) from type A to other finite Coxeter groups. The idea of extending the Tamari lattice to other Coxeter groups was then in the air; Hugh Thomas described a type B analogue in 2003, and around the same time, working independently, Nathan Reading found general definitions.
We're going to use the same idea as before: we want to identify a subset of elements of weak order that are closed under the lattice operations of the weak order.
The game is to replace the presentation of the symmetric group by the presentation of a general Coxeter group, we identify the elements of the Coxeter group with the connected regions of the complement of its hyperplane arrangement, and we replace the notion of inversion by which hyperplanes sit below a particular region. Again: elements of a finite Coxeter group form a lattice under the weak order: the meet of two elements u and w is the largest inversion set contained in the intersection of the inversion sets of u and w. Here I've drawn the hyperplane arrangement for S_3, along with their reduced words.
The generalization of 312-avoiding permutations is Nathan Reading's notion of c-sortable elements (these elements may also be specified as ``aligned elements'' using a condition on inversion sets, which is a natural generalization of Bjorner and Wach's "compressed" inversion sets). Briefly, we see that s_2s_1 is not c-sortable for S_3 when c=s_1s_2 because s_1 doesn't occur in the first copy of c, but does in the second.
The important thing to take away from this definition is that an element is ``c-sortable'' if it can be written as a product of simple reflections in some special way.
The number of c-sortable elements is given by the W-Catalan number, which is written in terms of the Coxeter number h and degrees d_i of the group. Here are the five c-sortable elements of S_3 when c=s_1s_2.
Again, the key point is that the intersection of the inversion sets of two c-sortable elements is again the inversion set of a c-sortable element, and so the that the c-sortable elements form a lattice is that we can explicitly describe the meet.
Of course, some people will tell you that the reason the c-sortable elements form a lattice is that c-sortable elements are really torsion-free classes in the category of finite dimensional representations of a Dynkin quiver (and that torsion-free classes are closed under subobjects).
Let's look at the Fuss-Catalan numbers for S_3 for a moment: 5 (that's good, five is less than 6 so we have a chance to find them inside S_3), 12 (12 is bigger than 6)...so now what? Well, we could pass to a higher S_n, but what do we do when we're trying to define these objects for E_8? E_9 isn't finite, so that isn't a good answer. So what takes the place of the weak order? What should be the ambient lattice?
The idea is simplicity itself: Replace the presentation of the Coxeter group by the presentation of the corresponding positive Artin monoid. This just means that we lose the condition that s_i^2=e.
This is a little disorienting for those of you who play with Coxeter groups, because we've now lost the geometry of the hyperplane arrangement and so don't have inversion sets. But this monoid still gives a lattice using gcd and lcm.
We call the interval [e,w_0^m] the m-weak order--as far as I know, this interval was originally considered by Dehornoy, although it is very natural even in the work of Garside (since it represents exactly those elements with at most m Garside factors).
For example, you can see in this picture the interval [e,w_0^2]---we can see inside of it the interval [e,w_0], and in general, the Coxeter group embeds as that interval. But now we have more elements around, which is exactly what we wanted. The hardest part of drawing this picture is writing s_i^2 and not reducing it to the identity.
With this setup, the generalization of c-sortable elements is deceptively easy: take Nathan Reading's condition on reduced words , but now interpret it as a condition on words in the positive monoid. Then (Theorem) the number of such elements in the interval [e,w_0^m] is the Fuss-Catalan number.
Finally, the point is that the join of two c-sortable elements for a particular interval is again a c-sortable element in the same interval, so that (Theorem) our Fussified c-sortable elements form a lattice.
And, of course, some people would give this a representation-theoretic interpretation: the Fuss-Cambrian lattices are the certain (fully addititve) torsion-free classes in the finite dimensional representations of the derived category of a Dynkin quiver ordered by inclusion.
For W a finite Weyl group, the most general Catalan number is the rational Catalan number. The story I've just told fits into the following progression of generality. Now we can look at the corresponding "longest elements", such that the number of c-sortable elements below those elements gives the correct enumeration. This suggests that the most general formula should be some "fractional" power of w_0. In fact, this isn't so crazy, since we have the formula w_0^2=c^h. And---for special c---we can use this to give conjectural answers (without leaving the Coxeter group, using the monoid) in the classical types, F_4, H_3, and I_2(m).