Invariant principal order ideals under Foata's transformation

Teresa X.S. Li¹ ; Melissa Y.F. Miao²

¹School of Mathematics and Statistics, Southwest University, China
²Center for Combinatorics, Nankai University, China

The electronic journal of combinatorics, Tome 19 (2012) no. 4

Résumé

Let $\Phi$ denote Foata's second fundamental transformation on permutations. For a permutation $\sigma$ in the symmetric group $S_n$, let $\widetilde{\Lambda}_{\sigma}=\{\pi\in S_n\colon\pi\leq_{w} \sigma\}$ be the principal order ideal generated by $\sigma$ in the weak order $\leq_{w}$. Björner and Wachs have shown that $\widetilde{\Lambda}_{\sigma}$ is invariant under $\Phi$ if and only if $\sigma$ is a 132-avoiding permutation. In this paper, we consider the invariance property of $\Phi$ on the principal order ideals ${\Lambda}_{\sigma}=\{\pi\in S_n\colon \pi\leq \sigma\}$ with respect to the Bruhat order $\leq$. We obtain a characterization of permutations $\sigma$ such that ${\Lambda}_{\sigma}$ are invariant under $\Phi$. We also consider the invariant principal order ideals with respect to the Bruhat order under Han's bijection $H$. We find that ${\Lambda}_{\sigma}$ is invariant under the bijection $H$ if and only if it is invariant under the transformation $\Phi$.

Détail

DOI : 10.37236/2680

Classification : 05A05, 05A15, 05A19
Mots-clés : Foata's second fundamental transformation, Han's bijection, Bruhat order, principal order ideal