## Colloquium Talk: October 20

Thursday, October 20, 2011

**Dr. Jonathan Farley**, *UMaine Dept. of Computer Science. *

**“The Most Embarrassing Inequality of My Life”**

Matchings in the Permutation Lattice

3:30 pm – 4:30 pm, 421 Neville Hall.

“Can you do it?”

In the spring of 1997, Anders Björner, a visitor at Berkeley’s Mathematical Sciences Research Institute, sent me a handwritten note in response to a question I had asked him. He wanted to know if I could prove, combinatorially, for an n-element poset of height r, that h_{k}≥h_{n-1-k} when k < (n-1)/2. I had been hunting this inequality for perhaps the previous four or five years. I believed that any fact about ordered sets, except artificially-rigged statements, must be provable by order-theoretic means. To my embarrassment, however, I could not deduce this inequality combinatorially. Nor could I concede defeat.

Perhaps I should explain.

Let S_{n} be the symmetric group on n letters with the weak Bruhat order, which means the following: Write each σ in S_{n} in the one-line notation σ = σ_{1}…σ_{n}. We call (σ_{i},σ_{j}) an *inversion* if i<j but σ_{i}>σ_{j}. The relation σ≤τ holds if and only if every inversion of σ is an inversion of τ; it turns out this makes S_{n} into a lattice ― in fact, a very special kind of lattice, one which is “bounded” in the sense of McKenzie.

We say a number i is a *descent* of σ if σ_{i} > σ_{i+1}; *ascents* are defined similarly. For fixed n, let J_{k} be the set of all permutations with exactly k descents, and let M_{k} be the set of all permutations with exactly k ascents. The covering relation in S_{n} with the weak order is given by: σ is a lower cover of τ if you can obtain τ from σ by taking exactly one ascent and reversing the corresponding two letters, turning them into a descent.

Label an n-element poset P with the numbers 1 through n so that 123…n is a linear extension, that is, label P with the numbers 1, 2, 3, up to n so that, whenever an element p is below an element q in the poset, the label of p (a natural number) is less than the label of q. This is called a *natural labeling*. Let h_{j} be the number of linear extensions of P ― that is, the permutations such that, if p is less than q in the poset, then the label for p appears to the left of the label for q in the permutation―with j descents.

For instance, if P is the four-element zig-zag or fence, one gets (1,3,1) for the h-vector; if P is a five-element antichain, one gets the famous eulerian numbers (1,26,66,26,1).

I could answer Björner’s question if, for n≥3 and 2 ≤ k< n/2-1, I could find an explicit bijection G from J_{k} to M_{k} such that for all σ in J_{k}, σ≤G(σ). Edelman and Reiner found an argument for k=1 and general n in response to a question of mine.

After I gave a talk on this topic at the University of Maine, while flying back to Austria I had an idea.