paper

Pattern Avoidance in Poset Permutations

arXiv:1208.5718 · doi:10.1007/s11083-015-9367-7

Abstract

We extend the concept of pattern avoidance in permutations on a totally ordered set to pattern avoidance in permutations on partially ordered sets. The number of permutations on $P$ that avoid the pattern $I ¨ $ is denoted $A v_{P} (I ¨ )$ . We extend a proof of Simion and Schmidt to show that $A v_{P} (132) \leq A v_{P} (123)$ for any poset $P$ , and we exactly classify the posets for which equality holds.

13 pages, 1 figure; v2: corrected typos; v3: corrected typos and improved formatting; v4: to appear in Order; v5: corrected typos; v6: updated author email addresses