Classified problem

Today at tea, some grad students were discussing the following enumeration problem:

How many elements of have zeroes in all diagonal entries?

I think they [Redacted]. The answer is apparently known but classified. It’s a sort of q-analog of derangements (i.e., permutations without fixed points), but if you take the derangement formula and add q-numbers in the naive way, the formula doesn’t seem to work for n > 2.

Rhombus tilings and an over-constrained recurrence

I recently visited Robin Pemantle and his student Peter Du at UPenn. We talked about tilings of planar regions, generating functions and asymptotics. Towards the end, we talked about a bit about a very classical example, which is what I want to tell you about today.

In most planar tiling problems, the goal is an asymptotic analysis for tilings of large regions, because there isn’t enough structure to do better. This is the approach taken in the beautiful work of Kenyon, Okounkov, and collaborators.^{1, 2, 3} Sometimes, there is enough structure to give exact solutions with explicit generating functions. This is the situation with Aztec Diamonds, fortresses, and other several other examples.^4,5 The central name here is Jim Propp 6, 7, who has developed this theory together with many undergraduate and graduate students (including me).

And then there is one case: rhombus tilings of a hexagon. These have almost too much structure; more structures than one would expect to be compatibly possible. In this post, I want to talk about this example. In particular, I want to ask you a question which I thought about a bit on the train ride back and see whether any of you have some thoughts.

A hunka hunka burnin’ knot homology

One of the conundra of mathematics in the age of the internet is when to start talking about your results. Do you wait until a convenient chance to talk at a conference? Wait until the paper is ready to be submitted to the arXiv (not to mention the question of when things are ready for the arXiv)? Until your paper is accepted? Or just until you’re confident you’ve disposed of any major errors in your proofs?

This line is particularly hard to walk when you think the result in question is very exciting. On one hand, obviously you are excited yourself, and want to tell people your exciting results (not to mention any worries you might have about being scooped); on the other, the embarrassment of making a mistake is roughly proportional to the attention that a result will grab.

At the moment, as you may have guessed, this is not just theoretical musing on my part. Rather, I’ve been working on-and-off for the last year, but most intensely over the last couple of months, on a paper which I think will be rather exciting (of course, I could be wrong).

A question for the combinatorialists

One of the points of combinatorics I never really learned is how to play correctly with Mobius functions. I mean, I can state Mobius inversion for an arbitrary poset if you give me a moment, but it all ends up a bit hard to manipulate.

This is particularly frustrating since I know that there are a certain number of people out there in the world who know all these tricks by heart. One of them should make a cheat sheet for all these identities.

So, here’s a question that might be easy to answer, but that I can’t quite muddle my way through. Let be a ranked poset (in my example, it’s flats of a matroid) with unique minimal element 0 and maximal 1 and Mobius function . Is there any better expression for the sum

?

Combinatorial Question

Here’s something I can prove, but I don’t understand.

Let be the number of trees whose leaves are labeled by , and whose internal vertices all have degree . So counts objects like the tree on the right.

Let . Let be the number of pairings of . So counts objects like the pairing on the left.

Theorem: .

Proof: We have the recursive relations and . (Exercise!)

Of course, it is easy to solve these recursions and compute that . This is sequence A001147 in Sloane’s encyclopedia, the so-called double factorial sequence.

Now, let be the number of trivalent trees with vertices which can be embedded in a disc, with the leaves occurring in circular order on the boundary. And let be the number of pairings of which can be embedded in a disc, with the points occurring in circular order around the boundary. The figures below show that .

Theorem:

Proof: We have the recurrences and . (Exercise!)

These are, of course, the Catalan numbers (Sloane A000108). There is a closed formula, .

So the question is: Why? Is there some bijection between trees and matchings under which the condition of having a planar embedding behaves nicely? Are there other examples where we can go between double-factorial objects, with a symmetric group symmetry and Catalan objects with a dihedral symmetry?

Gale and Koszul duality, together at last

So, in past posts, I’ve attempted to explain a bit about Gale duality and about Koszul duality, so now I feel like I should try to explain what they have to do with each other, since I (and some other people) just posted a preprint called “Gale duality and Koszul duality” to the arXiv.

The short version is this: we describe a way of getting a category  (or equivalently, an algebra) from a linear program (or as we call it, a polarized hyperplane arrangement).

Before describing the construction of this category, let me tell you some of the properties that make it appealing.

Theorem. is Koszul (that is, it can be given a grading for which the induced grading on the Ext-algebra of the simples matches the homological grading).

In fact, this category satisfies a somewhat stronger property: it is standard Koszul (as defined by Ágoston, Dlab and Lukács.  Those of you with Springer access can get the paper here).  In short, the category has a special set of objects called “standard modules” (which you should think of as analogous to Verma modules) which make it a “highest weight category,”  such that these modules are sent by Koszul duality to a set of standards for the Koszul dual.

Of course, whenever confronted with a Koszul category, we immediately ask ourselves what its Koszul dual is.  In our case, there is a rather nice answer.

Theorem. The Koszul dual to is , the category associated to the Gale dual of .

Now, part of the data of a linear program is an “objective function” (which we’ll denote by ) and of bounds for the contraints (which will be encoded by a vector ).  Stripping these way, we end up with a vector arrangement, simply a choice of a set of vectors in a vector space, which will specify the constraints.

Theorem. If two linear programs have same underlying vector arrangment, the categories may not be equivalent, but they will be derived equivalent, that is, their bounded derived categories will be equivalent.

Interestingly, these equivalences are far from being canonical. In the course of their construction, one actually obtains a large group of auto-equivalences acting on the derived category of , which we conjecture to include the fundamental group of the space of generic choices of objective function.

Hypertoric varieties and Koszul duality

So, on Wednesday, I gave a talk with the above title at IAS, about work in progress with Tom Braden, Tony Licata, and Nick Proudfoot.  I was hoping to get David Nadler to blog it for me, but he was *ahem* indisposed.  Failing that, I’ll direct you all to David Ben-Zvi’s notes (warning: freaking huge PDF).  Hopefully, that will whet your appetite for the forthcoming paper.

Interpreting the Hecke Algebra

Let denote the finite field with elements. Let denote the set of complete flags in . Such a flag is a chain of subspaces of , with and . For example, if , an element of is a quadruple , where is a plane through the origin and is a line through the origin, with contained in . Of course, including and is redundant, as is always zero and is always , but we will see that it is convenient to have them around. Now consider the following operation: forget and replace it by one of the other possible -planes lying between and . There are such choices, and we pick uniformly at random. Note that we are forbidden to just put back where it was. We will denote this operation by .

Let’s do an example: starting with a given flag, in the case , what is the effect of ? Note that we draw our pictures projectively, so we visualize as a pair (point, line through the point) in the projective plane. Let’s call this pair . The first step moves the point along the line to a new point . The second step pivots the line about the point to a new line . And the final step slides the point along the pivoted line to its final resting place at .

(Click the image for a larger version.) Now, if we are given and , what is the probability that takes us from to ?

Exercise: This probability is zero if , or if any two of the points , and coincide. If none of these unfortunate events occur, then the probability is . (Hint: note that we must take to have any chance of success.

Now, here is the interesting thing. Run through the same analysis for . The intermediate stages of the process will look completely different, but the end effect is precisely the same: probability zero in the degenerate cases mentioned above, and probability the rest of the time.

So we can write the equation and, more generally, . If you are uncomfortable talking about an equality of “processes”, you may interpret as a linear operator on the space of probability distributions on . There are also two other relations between the . The first, which is completely obvious, is that when . The second, which takes only a moment’s more thought, says that . In other words, if we do twice, there is a chance that we will get back the -plane we stared with and a chance that we won’t. Noah Snyder and John Baez can talk for hours about how this shows up in the tensor category of representations of a quantum group, so I won’t. Instead, I’ll explain some of the consequences of this for combinatorialists. At the end, I’ll bring up a very natural question that Jim Propp asked me, to which I don’t have a good answer yet. If no one writes in with a good solution, then I’ll pull together a sequel explaining my failed attempts.

Stable marriages

So, one of my odd mathematical fixations (totally unrelated to my research) is the stable marriage algorithm. Don’t ask me why, I just find it a remarkably appealing piece of math.

The stable marriage algorithm is, unfortunately, not a fool-proof way of keeping one’s marriage stable, but rather a way of taking two sets of parties (the obvious example being a group of men and a group of women, though the real life applications tend to involve much more boring things like matching medical students to residency programs), who would like to be paired up with each other. But rather than decide who marries who in the normal way, they want to give a mathematician a preference list, and have him sort out things in a sensible way.

Being a mathematician, this chap first has to come up with definition of a rigorous “sensible.” Certainly things won’t work very well if after the matching, there are any couples who would prefer to give the mathematician the middle finger and elope with each other to Vegas rather than stick with their assigned mates. A matching with no such couples is called “stable.” Now, this doesn’t uniquely specify the matching, and could leave many people still unhappy (if one gender all has similar preference lists, somebody still has to take the duds), but anybody they prefer to their spouse will not want to leave their own spouse for our unlucky lover. But at least no couple can complain the mathematician that he should have matched them instead.

Embedded TQFT?

So, a subject rather near and dear to the hearts of many of my fellow co-bloggers is that of 1+1-dimensional TQFT: that is, of monoidal functors from the category of 1-manifolds with morphisms given by smooth cobordisms to the category of vector spaces over your favorite field .

There’s a rather remarkable theorem about such functors, which really deserves a post of its own for proper explanation, but I’ll spoil the surprise here.

Any such functor associates a vector space to a single circle, and to the “pair of pants” cobordism, it assigns a map , which one can check is a commutative multiplication.

Furthermore, the cap, thought of as a cobordism from the empty set to a circle gives a map , which gives a unit of this algebra. Thought of as a cobordism from the circle to the empty set, it gives us a map which we call the counit or Frobenius trace.

Theorem. A commutative algebra with counit arises from a TQFT if and only if kills no left ideal of .