Two characterizations of the shape of the base poset derived from the Lehmer code of a permutation using permutation patterns

The Lehmer code is a classical and fundamental permutation code which encodes information about the inversions of a permutation. Denoncourt constructed a poset $M_{\omega}$ which is the subposet of join-irreducible elements of the Lehmer codes of the permutations in $[e_n, \omega]$ in the left weak Bruhat order, i.e., the inversion order, on $S_n$ for $\omega \in S_n$. In this paper, we investigate the poset structure of $M_{\omega}$ in terms of pattern avoidance. First we show that $M_{\omega}$ is a $B_2$-free poset if and only if $\omega$ is a $3412 \textrm{-} 3421 \,$-avoiding permutation. Next we prove that $M_{\omega}$ is poset isomorphic to the corresponding root poset if and only if $\omega$ is a $321 \,$-avoiding permutation.

Keywords

permutation patterns, Lehmer codes, root posets

2010 Mathematics Subject Classification

05A05, 06A07

Full Text (PDF format)

Published 11 March 2015