**NB:** A
PDF
version of this announcement (suitable for posting) is also available.
# Harry Potter and the Linear Extensions of a Naturally Labelled Poset, Enumerated by Descents

### Jonathan David Farley

Vanderbilt University

###
Thursday, October 5, 2000

102 Bradley Hall, 4 pm

Tea 3:30 pm, Math Lounge

**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.