Tags: #definition

poset associated to a permutation

Let $w\in S_n$ be a permutation. Define its associated poset as $P_w$ poset on $[n]$ such that

• $w_i{<}_P{w}_j⟺i{<}_{\mathbb{Z}}j$ and $w_i{<}_{\mathbb{Z}}{w}_j$.

Properties

This gives the following bijections:

• chains of $P(w)$ and increasing subsequences in $w$
• antichains of $P(w)$ and decreasing subsequences in $w$

lambda(P(w)) is schensted shape