比利时vs摩洛哥足彩
,
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
****************************