## Hansson, Mikael - The Bruhat order on conjugation-invariant sets of involutions in the symmetric group

dmtcs:2472 - Discrete Mathematics & Theoretical Computer Science, January 1, 2015, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
The Bruhat order on conjugation-invariant sets of involutions in the symmetric group

Authors: Hansson, Mikael

Let $I_n$ be the set of involutions in the symmetric group $S_n$, and for $A \subseteq \{0,1,\ldots,n\}$, let $F_n^A=\{\sigma \in I_n \mid \text{\sigma has a fixed points for some a \in A}\}.$ We give a complete characterisation of the sets $A$ for which $F_n^A$, with the order induced by the Bruhat order on $S_n$, is a graded poset. In particular, we prove that $F_n^{\{1\}}$ (i.e., the set of involutions with exactly one fixed point) is graded, which settles a conjecture of Hultman in the affirmative. When $F_n^A$ is graded, we give its rank function. We also give a short new proof of the EL-shellability of $F_n^{\{0\}}$ (i.e., the set of fixed point-free involutions), which was recently proved by Can, Cherniavsky, and Twelbeck.

Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Section: Proceedings
Published on: January 1, 2015
Submitted on: November 21, 2016
Keywords: Bruhat order,symmetric group,involution,conjugacy class,graded poset,EL-shellability,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]