 |
Abstract: Let ``Fred" be a finite partially ordered set, labelled by the numbers 1, 2, 3, up to $n$ so that, whenever an element $p$ is below an element $q$ in the poset, the {\sl label\/} of $p$ (a natural number) is less than the {\sl label\/} of $q$. (In posetese, the permutation $123\dots n$ is a ``linear extension" of the poset Fred.) For example, consider the zig-zag-shaped poset with four elements $1,2,3,4$, whose partial ordering is given by $1<3>2<4$.
Look at the linear extensions, that is, the permutations in $S_n$ that respect the partial ordering of Fred, by which we mean the following: If the element labelled $i$ in Fred is below the element labelled $j$ in Fred, then the number $i$ must come before the number $j$ in the permutation. In our example, there are $5$ linear extensions: $1234$, $2134$, $1243$, $2143$, and $2413$. (If Fred were a totally unordered poset, every permutation in $S_n$ would be a linear extension.)
Now take your favourite linear extension and count the number of ``descents," that is, the places where a bigger number {\sl immediately\/} precedes a smaller number. In our example, the number of descents in the linear extensions is given by 0, 1, 1, 2, and 1, respectively. Let $h_{42}$ be the number of linear extensions with $42$ descents. The zig-zag has $h_0=1$, $h_1=3$, and $h_2=1$.
According to a theorem of Richard P. Stanley of MIT, if Fred is ranked (that is, if every maximal chain has the same number of elements, $r$), then the sequence $h_0,h_1,\dots,h_{n-r}$ will be symmetric. In our example, we have the sequence $1,3,1$ ($n=4$ and $r=2$). If Fred is the $5$-element totally unordered poset, we get the ``eulerian" numbers $1,26,66,26,1$ ($n=5$ and $r=1$).
At the 1981 Banff Conference on Ordered Sets, Stanley asked for a direct, combinatorial, bijective proof of this theorem. That is, if $H_{42}$ is the {\sl set\/} of linear extensions with $42$ descents, Stanley asked for a bijection between $H_0$ and $H_{n-r}$, $H_1$ and $H_{n-r-1}$, etc. --- in general, between $H_k$ and $H_{n-r-k}$.
We present a partial solution to the problem, for the cases $k=0$, $1$, and $2$. We leave the cases $k=3$ through $\infty$ to the reader.
(This talk has nothing to do with the 1975 conjecture of Richard Stanley that the speaker settled in 1999.)
This talk will be accessible to graduate students.
|