Contents Online

# Journal of Combinatorics

## Volume 3 (2012)

### Number 3

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

Pages: 277 – 298

DOI: http://dx.doi.org/10.4310/JOC.2012.v3.n3.a2

#### Author

#### Abstract

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