An equivalence relation on the symmetric group and multiplicity-free flag $h$-vectors

We consider the equivalence relation $\sim$ on the symmetric group $\sn$ generated by the interchange of any two adjacent elements $a_i$ and $a_{i+1}$ of $w=a_1 \cdots a_n\in\sn$ such that $|a_i-a_{i+1}|=1$. We count the number of equivalence classes and the sizes of the equivalence classes. The results are generalized to permutations of multisets. In the original problem, the equivalence class containing the identity permutation is the set of linear extensions of a certain poset. Further investigation yields a characterization of all finite graded posets whose flag $h$-vector takes on only the values $0,\pm 1$.

Keywords

symmetric group, linear extension, flag h-vector

2010 Mathematics Subject Classification

05A15, 06A07

Full Text (PDF format)

Published 19 February 2013