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 hk≥hn-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 Sn be the symmetric group on n letters with the weak Bruhat order, which means the following: Write each σ in Sn 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 Sn 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 Jk be the set of all permutations with exactly k descents, and let Mk be the set of all permutations with exactly k ascents. The covering relation in Sn 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 hj 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 Jk to Mk such that for all σ in Jk, σ≤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.