Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 295 - Mathematics Colloquium

Jonathan David Farley

Harvard University

Linear extensions of ranked posets, enumerated by descents: A problem of Richard P. Stanley from 1981

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 label of $p$ (a natural number) is less than the label of $q$. (The permutation $123...n$ is a ``linear extension" of the poset Fred.) \vskip .1 in \noindent 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$. \vskip .1 in \noindent 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$. \vskip .1 in \noindent Now take your favourite linear extension and count the number of descents, the number of places where a bigger number comes immediately before 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_k$ be the set of linear extensions with $k$ descents and let $h_k$ be the number of such extensions. The zig-zag has $h_0=1$, $h_1=3$, and $h_2=1$. \vskip .1 in \noindent The $h$-vector in this case---(1,3,1)---is symmetric. Around 1971 Stanley proved that the $h$-vector of a ranked poset is always symmetric. At the 1981 Banff Conference on Ordered Sets, Stanley asked for a bijective proof of this fact. To wit, if a naturally-labelled poset of size $n$ is ranked (all maximal chains have the same number of elements $r+1$), Stanley wanted to find a bijection between the set of linear extensions with $k$ descents and the set of linear extensions with $n-1-r-k$ descents. \vskip .1 in \noindent We establish such a bijection, thus solving Stanley's problem from 1981.

Host: Kate Okikiolu

February 3, 2005

3:00 PM

AP&M 6438

****************************