Journal of Combinatorics

Volume 5 (2014)

Number 4

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

Pages: 499 – 519

DOI: http://dx.doi.org/10.4310/JOC.2014.v5.n4.a6

Author

Masaya Tomie (Morioka University, Takizawa-shi, Iwate, Japan)

Abstract

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)