UNI-MB - logo
UMNIK - logo
 
E-resources
Peer reviewed Open access
  • The Bruhat order on conjuga...
    Hansson, Mikael

    Discrete Mathematics and Theoretical Computer Science, 01/2015, Volume: DMTCS Proceedings, 27th..., Issue: Proceedings
    Journal Article, Conference Proceeding

    12 pages, 3 figures 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. Soit $I_n$ l’ensemble d’involutions dans le groupe symétrique $S_n$, et pour $A \subseteq \{0,1,\ldots,n\}$, soit\ F_n^A=\{\sigma \in I_n \mid \text{$\sigma$ a $a$ points fixes pour quelque $a \in A$}\}. \ Nous caractérisons tous les ensembles $A$ dont les $F_n^A$ , avec l’ordre induit par l’ordre de Bruhat sur $S_n$, est un posetgradué. En particulier, nous démontrons que $F_n^{\{1\}}$ (c’est-à-dire, l’ensemble d’involutions avec précis en point fixe)est gradué, ce qui résout une conjecture d’Hultman à l’affirmative. Lorsque $F_n^A$ est gradué, nous donnons sa fonctionde rang. En plus, nous donnons une nouvelle démonstration courte l’EL-shellability de $F_n^{\{0\}}$ (c’est-à-dire, l’ensembled’involutions sans points fixes), établie récemment par Can, Cherniavsky et Twelbeck.